3.11 결정적 튜링 기계(DTM)의 정의와 동작 원리

1. 결정론의 의미

결정론(Determinism)은 체계의 동작이 현재 상태에 의해 유일하게(Uniquely) 결정된다는 원리이다. 결정적 튜링 기계(Deterministic Turing Machine, DTM)에서 결정론은 전이 함수 $\delta$ 가 단일값 함수(Single-Valued Function)임을 의미한다. 현재 상태 $q$ 와 헤드가 읽은 기호 $a$ 의 쌍 $(q, a)$ 가 주어지면, 다음 상태, 쓸 기호, 이동 방향이 정확히 하나로 결정된다.

$\delta: (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$

이 정의에서 $\delta$ 는 전함수(Total Function)이므로, 정의역의 모든 쌍 $(q, a)$ 에 대해 정확히 하나의 출력 $(q', b, D)$ 가 존재한다. 동일한 $(q, a)$ 에 대해 두 개 이상의 가능한 전이가 존재하는 것은 허용되지 않는다.

DTM의 결정론적 실행

실행 경로의 유일성

DTM의 결정론적 성격에 의해, 임의의 입력 $w$ 에 대한 실행 경로(Execution Path)는 유일하다. 초기 배치 $C_0 = q_0 w$ 에서 출발하여, 각 단계에서 전이 함수가 유일한 후속 배치를 결정하므로, 배치열 $C_0, C_1, C_2, \ldots$ 는 유일하게 결정된 선형 열(Linear Sequence)이다.

이는 비결정적 튜링 기계(Nondeterministic Turing Machine, NTM)와의 핵심적 차이이다. NTM에서는 동일한 $(q, a)$ 에 대해 여러 가능한 전이가 존재하여 실행 경로가 분기하며, 분기하는 계산 트리(Computation Tree)를 형성한다.

재현 가능성(Reproducibility)

DTM의 결정론은 동일한 입력에 대해 동일한 계산 과정이 항상 재현됨을 보장한다. 기계를 동일한 입력 $w$ 에 대해 반복 실행하면 항상 동일한 배치열을 거치고 동일한 결과에 도달한다. 이 재현 가능성은 DTM의 동작을 예측하고 분석하는 데 핵심적 성질이다.

DTM의 동작 원리 상세

명시적 절차

DTM의 계산 과정은 다음의 명시적 절차로 기술된다:

절차 DTM-EXECUTE( $M$ , $w$ ):

테이프에 입력 $w$ 를 기록하고 나머지 셀을 $\sqcup$ 으로 초기화한다.
헤드를 테이프의 첫 셀에 위치시킨다.
기계를 시작 상태 $q_0$ 으로 설정한다.
반복: 현재 상태가 $q_{\text{accept}}$ 도 $q_{\text{reject}}$ 도 아닌 동안:
a. 현재 상태 $q$ 와 헤드가 읽은 기호 $a$ 를 확인한다.
b. $\delta(q, a) = (q', b, D)$ 를 조회한다.
c. 기계의 상태를 $q'$ 로 갱신한다.
d. 현재 셀에 $b$ 를 기록한다.
e. 헤드를 방향 $D$ 로 한 셀 이동한다.
현재 상태가 $q_{\text{accept}}$ 이면 “수락“을 출력한다.
현재 상태가 $q_{\text{reject}}$ 이면 “거부“를 출력한다.

비정지(Non-Halting)의 가능성

위 절차의 4번 반복 루프가 종료되지 않을 가능성이 있다. 기계가 수락 상태나 거부 상태에 도달하지 않고 무한히 계산을 계속하는 경우, 기계는 해당 입력에 대해 정지하지 않는다(Does Not Halt). 이 경우 기계는 입력을 수락하지도 거부하지도 않으며, 이는 기계가 해당 입력을 인식(Recognize)하지 않는 것으로 간주된다.

언어의 인식과 결정

튜링 인식 가능(Turing-Recognizable)

DTM $M$ 이 인식하는 언어 $L(M)$ 은 $M$ 이 수락하는 모든 문자열의 집합이다:

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

$w \notin L(M)$ 인 경우, $M$ 은 $w$ 를 거부하거나 $w$ 에 대해 정지하지 않는다. 두 경우가 모두 가능하다.

1.1 튜링 결정 가능(Turing-Decidable)

DTM $M$ 이 결정기(Decider)라 함은 모든 입력 $w \in \Sigma^*$ 에 대해 $M$ 이 정지함을 의미한다. 즉, $M$ 은 모든 입력을 수락 또는 거부하며, 무한 루프에 빠지지 않는다.

$M$ 이 결정기일 때, $M$ 이 결정하는 언어는:

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

이며, 모든 $w \notin L(M)$ 에 대해 $M$ 은 $w$ 를 거부한다.

결정 가능과 인식 가능의 관계

$\text{결정 가능 언어} \subset \text{인식 가능 언어} \subset \text{모든 언어}$

모든 결정 가능 언어는 인식 가능하지만, 역은 성립하지 않는다. 인식 가능하지만 결정 불가능한 언어가 존재하며, 정지 문제의 언어 $\text{HALT} = \{\langle M, w \rangle \mid M \text{이 } w \text{에 대해 정지}\}$ 가 그 대표적 예이다.

2. DTM의 시간 복잡도와 공간 복잡도

2.1 시간 복잡도(Time Complexity)

DTM $M$ 의 시간 복잡도 함수 $t: \mathbb{N} \rightarrow \mathbb{N}$ 에서 $t(n)$ 은 길이 $n$ 의 모든 입력에 대해 $M$ 이 정지할 때까지 수행하는 최대 단계 수이다:

$t(n) = \max\{k \mid \exists w \in \Sigma^n, \, M \text{이 } w \text{에 대해 } k \text{ 단계 만에 정지}\}$

$M$ 이 결정기일 때만 $t(n)$ 이 모든 $n$ 에 대해 정의된다.

공간 복잡도(Space Complexity)

DTM $M$ 의 공간 복잡도 함수 $s: \mathbb{N} \rightarrow \mathbb{N}$ 에서 $s(n)$ 은 길이 $n$ 의 모든 입력에 대해 $M$ 의 헤드가 방문하는 최대 셀 수이다.

복잡도 클래스

시간 복잡도와 공간 복잡도에 의해 다음의 표준적 복잡도 클래스(Complexity Class)가 정의된다:

$\text{TIME}(f(n))$ : 시간 복잡도가 $O(f(n))$ 인 DTM에 의해 결정되는 언어의 클래스
$\text{SPACE}(f(n))$ : 공간 복잡도가 $O(f(n))$ 인 DTM에 의해 결정되는 언어의 클래스
$\text{P} = \bigcup_{k \geq 0} \text{TIME}(n^k)$ : 다항 시간(Polynomial Time) 결정 가능 언어의 클래스
$\text{PSPACE} = \bigcup_{k \geq 0} \text{SPACE}(n^k)$ : 다항 공간 결정 가능 언어의 클래스

DTM과 현대 컴퓨터의 관계

DTM은 현대 결정론적 디지털 컴퓨터(Deterministic Digital Computer)의 이론적 모델이다. 현대 컴퓨터의 CPU는 결정론적으로 동작하며, 동일한 입력과 동일한 초기 상태에 대해 항상 동일한 결과를 산출한다. DTM의 전이 함수는 CPU의 명령어 실행 규칙에, DTM의 테이프는 메모리에, DTM의 상태는 CPU 레지스터의 상태에 대응한다.

DTM은 현대 컴퓨터가 수행할 수 있는 모든 계산을 이론적으로 포착하는 모델이며, DTM에서 증명된 계산 가능성/불가능성 결과는 현대 컴퓨터의 능력과 한계에 대한 원리적 보장이다.