[1주1장 CS] 컴퓨터의 이론적, 설계적 토대: 튜링 머신과 폰 노이만 구조

서론

우리가 매일 쓰는 컴퓨터는 수많은 이론과 기술을 토대로 만들어졌습니다. 그 중에서도 가장 대표적인 것을 꼽자면 단연컨대 튜링 머신[Turing machine]과 폰 노이만 구조[Von Neumann architecture]를 들 수 있습니다. 이 두 가지는 각각 현대의 이론 컴퓨터 과학과 컴퓨터 설계의 기초가 됩니다.

이 글에서는 각각의 구체적인 설명 대신, 컴퓨터과학에서의 의미를 중심으로 다룰 것입니다. 왜 이 두 가지가 컴퓨터과학에서 중요한지, 어떤 의미를 갖는지 알아볼까요?

튜링 머신

튜링 머신이란 앨런 튜링[Alan Turing(1912-1954). 영국의 수학자. 컴퓨터과학의 아버지로 불린다.]이 1936년에 제안한 이론적 계산 장치로, 모든 계산 장치의 구조를 필수 요소로 줄인 수학적 모델입니다. 이러한 튜링 머신은 입출력과 메모리, 정보 처리의 구성을 모두 갖고 있어 모든 디지털 컴퓨터의 기초가 되었습니다[1].

구성 요소

튜링 머신은 다음과 같은 구성 요소로 이루어져 있습니다[2]:

• 테이프: 메모리 역할을 하는 무한한 길이의 테이프로, 각 셀에 기호를 저장할 수 있습니다.
• 헤드: 테이프 위를 이동하며 기호를 읽고 쓸 수 있는 장치입니다. 한 번에 하나의 셀을 읽은 후 수정하거나 이동할 수 있습니다.
• 전이 함수: 튜링 머신의 행동을 결정하는 규칙 집합입니다.
• 상태 집합: 튜링 머신의 현재 상태를 나타내는 집합입니다. 시작 상태, 수락 상태, 거부 상태 등이 있습니다.
• 알파벳 집합: 테이프에 저장할 수 있는 기호의 집합입니다. 주로 0과 1이 사용되지만, 다른 기호도 가능합니다.

작동 방식

튜링 머신은 처음 초기화 단계에서 시작해, 현재 상태와 헤드가 읽은 기호에 따라 전이 함수를 참조, 다음 상태와 헤드의 이동 방향을 결정합니다. 이 과정은 수락 상태 또는 거부 상태에 도달할 때까지 반복되고, 종료된 상태에 따라 입력이 받아들여졌는지, 거부되었는지를 판단합니다[2]. 이런 과정은 결정론적으로 이루어집니다.

의의

튜링 머신은 계산 가능성이라는 이론을 정립했습니다. 튜링은 기계적으로 계산하는, 기본 연산자만으로 이루어진 계산들은 튜링 머신으로 모사할 수 있음을 보였습니다. 즉 계산 가능한 함수는 튜링 머신으로 계산할 수 있는 함수와 동치라는 것입니다[3]. 어떤 문제를 해결하는 방법, 알고리즘에 대한 기초도 제시했습니다. 이러한 의미에서 튜링 머신은 이론 컴퓨터 과학의 기초가 되고, 튜링이 컴퓨터과학의 아버지로 불리는 이유입니다.

한편, 이러한 튜링 머신과 같은 동작을 할 수 있는 모델은 튜링 완전하다고 합니다. 우리가 사용하는 컴퓨터 또한 튜링 완전하죠^[*1]. 이러한 개념은 프로그래밍 언어에서도 사용됩니다. HTML과 같은 언어는 튜링 완전하지 않지만, C++나 Java와 같은 언어는 튜링 완전하다고 합니다. 튜링 머신이 할 수 있는 모든 계산을 할 수 있는 거죠.

폰 노이만 구조

튜링 머신은 이론적 모델이기에 실제 기계로 구성하기에는 어려움이 따릅니다. 폰 노이만 구조는 많은 일반적인 컴퓨터가 기반을 두고 있는 구조로, fetch-decode-execute의 주기를 따릅니다. 명령과 데이터는 모두 주기억장치에 이진수로 저장되고, 명령을 읽어서(fetch), 해석하고(decode), 실행하는(execute) 명령 주기를 따릅니다. 이는 모든 명령이 끝날 때까지 반복됩니다[4]. 이런 폰 노이만 구조는 (느슨하게) 튜링 완전합니다. 즉 범용적인 컴퓨터로서 모든 계산을 수행할 수 있는 거죠.

장점

폰 노이만 구조는 간단함과 유연함이 장점입니다. 프로그램과 데이터가 모두 같이 저장되므로, 프로그램을 수정하기 쉽고, 다양한 프로그램을 실행할 수 있습니다. 또한 구성도 간단해 설계와 구현이 용이합니다. 이러한 장점 덕분에 현대 컴퓨터의 대부분이 폰 노이만 구조를 따릅니다.

단점

폰 노이만 구조의 성능에 발목을 잡는 단점은 폰 노이만 병목 현상입니다. 프로세서와 메모리는 시스템 버스를 통해 데이터를 주고받는데, 프로세서가 정보를 처리하는 속도가 빠르면 데이터를 주고받는 시간이 전체 성능을 제한합니다. 이런 한계를 극복하고자 캐싱과 프리페칭 등이 등장하고 적용되어 성능을 향상시키고 있지만, 근본적인 병목 현상은 극복할 수 없습니다[5].

결론

튜링과 그의 이론적인 계산 장치인인 튜링 머신은 이론 컴퓨터 과학, 그 중에서도 계산 가능성 이론과 알고리즘의 기틀을 닦았습니다. 폰 노이만 구조는 이러한 이론에 더해 실제로 구현하기 좋은, 단순하고 유연한 구조를 제시해 대부분의 현대 컴퓨터가 따르는 구조가 되었습니다. 이러한 부분에서 두 구조는 현대 컴퓨터의 이론적, 설계적 토대가 됩니다.

정리

• 튜링 머신: 튜링이 고안한 이론적 계산 장치
  • 결정론적: 같은 입력에 대해 항상 출력이 같음
  • 튜링 완전: 튜링 머신을 모사할 수 있는 모델
  • → 계산 가능성 이론, 알고리즘 등 이론 컴퓨터 과학의 기초
• 폰 노이만 구조: 일반적인 컴퓨터의 구조. 메모리에 명령과 데이터를 같이 저장
  • 장점: 단순함, 유연함
  • 단점: 폰 노이만 병목
    • 메모리 접근 속도 때문에 전체 성능 제한
  • → 대부분의 현대 컴퓨터에 적용된 구조, 현대 컴퓨터의 설계적 기초

용어

label

튜링 머신

Turing machine

label

폰 노이만 구조

Von Neumann architecture

label

앨런 튜링

Alan Turing(1912-1954). 영국의 수학자. 컴퓨터과학의 아버지로 불린다.

@misc{devngho202520250503weeklycsturingmachine,
  author       = {Yu, Dongho},
  title        = {컴퓨터의 이론적, 설계적 토대: 튜링 머신과 폰 노이만 구조},
  howpublished = {\url{https://ngho.dev/posts/20250503-weekly-cs-turing-machine}},
  year         = {2025},
  month        = {may},
  note         = {Accessed: 2025-05-04}
}

@misc{devngho202520250503weeklycsturingmachine,
  author       = {Yu, Dongho},
  title        = {컴퓨터의 이론적, 설계적 토대: 튜링 머신과 폰 노이만 구조},
  howpublished = {\url{https://ngho.dev/posts/20250503-weekly-cs-turing-machine}},
  year         = {2025},
  month        = {may},
  note         = {Accessed: 2025-05-04}
}