Chapter 3. 튜링 기계의 수학적 모델링과 동작 원리

Chapter 3. 튜링 기계의 수학적 모델링과 동작 원리

1. 튜링 기계의 역사적 맥락

앨런 매시슨 튜링(Alan Mathison Turing, 1912–1954)은 1936년 발표한 논문 “On Computable Numbers, with an Application to the Entscheidungsproblem“에서 튜링 기계(Turing Machine)라는 추상적 계산 모델을 제안하였다. 이 모델은 힐베르트(David Hilbert)가 제기한 판정 문제(Entscheidungsproblem)—일차 술어 논리의 임의의 문장이 논리적으로 타당한지를 기계적으로 판정하는 일반적 절차가 존재하는가—에 대한 부정적 해답을 제공하기 위해 고안되었다.

튜링 기계의 학문사적 의의는 이중적이다. 첫째, “기계적으로 계산 가능하다“는 직관적 개념을 최초로 엄밀한 수학적 정의로 형식화하였다. 둘째, 이 정의를 통해 기계적 계산의 근본적 한계를 증명하였다. 이 두 가지 기여는 계산 이론(Theory of Computation)의 기초를 확립하였으며, 현대 컴퓨터 과학과 인공지능의 이론적 토대를 구성한다.

2. 튜링 기계의 수학적 정의

튜링 기계 M은 다음의 7-튜플(7-Tuple)로 형식적으로 정의된다:

M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})

각 구성 요소의 정의:

  • Q: 유한 상태 집합(Finite Set of States)이다.
  • \Sigma: 입력 알파벳(Input Alphabet)이다. 공백 기호(Blank Symbol) \sqcup를 포함하지 않는다.
  • \Gamma: 테이프 알파벳(Tape Alphabet)이다. \Sigma \subseteq \Gamma이며 \sqcup \in \Gamma이다.
  • \delta: 전이 함수(Transition Function)이다. \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}로 정의된다.
  • q_0 \in Q: 시작 상태(Start State)이다.
  • q_{\text{accept}} \in Q: 수락 상태(Accept State)이다.
  • q_{\text{reject}} \in Q: 거부 상태(Reject State)이다. q_{\text{accept}} \neq q_{\text{reject}}이다.

튜링 기계의 물리적 구성 요소

무한 테이프(Infinite Tape)

테이프는 양방향으로 무한히 확장되는(또는 한 방향으로 무한한) 1차원 셀(Cell)의 배열이다. 각 셀은 테이프 알파벳 \Gamma의 정확히 하나의 기호를 저장한다. 입력 문자열은 테이프의 연속된 셀에 기록되며, 나머지 셀은 공백 기호 \sqcup로 채워져 있다. 테이프는 데이터의 저장 매체이자 작업 공간(Working Memory)으로 기능한다.

읽기/쓰기 헤드(Read/Write Head)

헤드는 테이프의 특정 셀 위에 위치하며, 해당 셀의 기호를 읽고 새로운 기호를 쓸 수 있다. 각 계산 단계에서 헤드는 왼쪽(L) 또는 오른쪽(R)으로 정확히 한 셀 이동한다.

유한 상태 제어 장치(Finite State Control)

유한 상태 제어 장치는 기계의 현재 상태를 저장하는 내부 기억 장치이다. 유한 개의 상태 중 하나를 취하며, 현재 상태와 헤드가 읽은 기호에 따라 전이 함수 \delta가 다음 동작을 결정한다.

튜링 기계의 동작 원리

튜링 기계의 계산 과정은 다음의 반복적 단계로 이루어진다.

단일 계산 단계

시각 t에서 기계의 현재 상태가 q이고, 헤드가 위치한 셀의 기호가 a일 때, 전이 함수 \delta(q, a) = (q', b, D)에 따라:

  1. 기계의 상태가 q에서 q'로 전이한다.
  2. 현재 셀의 기호 a를 b로 덮어쓴다.
  3. 헤드가 방향 D \in \{L, R\}로 한 셀 이동한다.

계산의 시작

입력 문자열 w = w_1 w_2 \cdots w_n이 테이프의 처음 n개 셀에 기록되고, 헤드는 첫 번째 셀 위에 위치하며, 기계는 시작 상태 q_0에 있다.

계산의 종료

기계가 수락 상태 q_{\text{accept}}에 도달하면 계산이 종료되고 입력이 수락(Accept)된다. 거부 상태 q_{\text{reject}}에 도달하면 계산이 종료되고 입력이 거부(Reject)된다. 기계가 두 상태 중 어느 것에도 도달하지 않으면 계산이 영원히 계속되며, 이 경우 기계는 해당 입력에 대해 정지하지 않는다(Does Not Halt).

배치(Configuration)와 계산 이력

배치의 정의

튜링 기계의 순간적 상태는 배치(Configuration) 또는 순간 기술(Instantaneous Description)로 표현된다. 배치는 현재 상태 q, 테이프의 내용, 헤드의 위치를 포함하는 완전한 상태 기술이다. 형식적으로, 배치는 문자열 \alpha q \beta로 표기되며, \alpha는 헤드 왼쪽의 테이프 내용, q는 현재 상태, \beta는 헤드 위치의 기호부터 오른쪽의 테이프 내용이다.

계산 이력(Computation History)

입력 w에 대한 튜링 기계 M의 계산 이력은 배치의 유한 또는 무한 열이다:

C_0 \vdash C_1 \vdash C_2 \vdash \cdots

여기서 C_0는 초기 배치이고, C_i \vdash C_{i+1}은 한 단계의 전이를 나타낸다.

3. 튜링 기계로 인식되는 언어

튜링 기계 M이 인식(Recognize)하는 언어 L(M)은 M이 수락하는 모든 문자열의 집합이다:

L(M) = \{w \in \Sigma^* \mid M \text{ accepts } w\}

튜링 인식 가능(Turing-Recognizable) 언어는 재귀적으로 열거 가능한(Recursively Enumerable, RE) 언어라고도 불린다.

튜링 기계 M이 모든 입력에 대해 정지(Halt)하면, M을 결정기(Decider)라 하며, M이 결정(Decide)하는 언어를 재귀 언어(Recursive Language) 또는 튜링 결정 가능(Turing-Decidable) 언어라 한다.

범용 튜링 기계(Universal Turing Machine)

튜링의 핵심적 결과 중 하나는 범용 튜링 기계(Universal Turing Machine, UTM)의 존재 증명이다. 범용 튜링 기계 U는 임의의 튜링 기계 M의 부호화 \langle M \rangle과 입력 w를 입력으로 받아, M이 w에 대해 수행하는 계산을 시뮬레이션한다:

U(\langle M \rangle, w) = M(w)

범용 튜링 기계의 존재는 단일한 기계가 적절한 “프로그램”(\langle M \rangle)을 제공받으면 임의의 계산을 수행할 수 있음을 의미한다. 이 원리는 현대 범용 컴퓨터(General-Purpose Computer)와 저장 프로그램 개념(Stored-Program Concept)의 이론적 기원이다.

4. 정지 문제(Halting Problem)

튜링은 범용 튜링 기계의 존재를 이용하여 정지 문제(Halting Problem)의 결정 불가능성(Undecidability)을 증명하였다. 정지 문제는 다음과 같이 정의된다:

임의의 튜링 기계 M과 입력 w가 주어졌을 때, M이 w에 대해 정지하는지 여부를 판정하는 튜링 기계가 존재하는가?

튜링은 대각선 논법(Diagonalization Argument)을 사용하여 이 문제를 결정하는 튜링 기계가 존재하지 않음을 증명하였다. 이 결과는 기계적 계산의 근본적 한계를 확정한 것이며, 힐베르트의 판정 문제에 대한 부정적 해답을 제공한다.

5. 튜링 기계의 변형과 동치성

튜링 기계에는 다양한 변형이 존재하며, 이들은 모두 표준 튜링 기계와 계산적으로 동치이다.

  • 다중 테이프 튜링 기계(Multi-Tape Turing Machine): 여러 개의 테이프와 헤드를 가진다. 단일 테이프 튜링 기계로 시뮬레이션 가능하다.
  • 비결정론적 튜링 기계(Nondeterministic Turing Machine, NTM): 전이 함수가 다수의 가능한 전이를 허용한다. 결정론적 튜링 기계로 시뮬레이션 가능하다(지수적 시간 증가 가능).
  • 다차원 테이프 튜링 기계: 2차원 이상의 테이프를 사용한다.

이 변형들이 모두 표준 튜링 기계와 동등한 계산 능력을 갖는다는 사실은 처치-튜링 논제(Church-Turing Thesis)의 경험적 근거가 된다.

6. 튜링 기계와 현대 컴퓨터 과학

튜링 기계는 현대 컴퓨터 과학의 다음 분야에서 핵심적 역할을 한다.

계산 복잡도 이론(Computational Complexity Theory): P, NP, PSPACE 등의 복잡도 클래스는 튜링 기계에서의 시간 및 공간 자원 소모에 의해 정의된다.

형식 언어 이론(Formal Language Theory): 촘스키 위계(Chomsky Hierarchy)의 최상위에 위치하는 제한 없는 문법(Unrestricted Grammar)이 생성하는 언어 클래스가 정확히 튜링 인식 가능 언어와 일치한다.

알고리즘 분석: 알고리즘의 정확성(Correctness)과 효율성(Efficiency)의 분석이 튜링 기계 모델에 기반한다.

튜링 기계는 인류가 “계산“이라는 개념을 정밀하게 포착한 최초의 수학적 모델이며, 현대 컴퓨터 과학과 인공지능의 전 체계가 이 모델 위에 구축되어 있다.