3.13 DTM과 NTM의 동치성 증명

1. 동치성 정리의 진술

정리: 비결정적 튜링 기계(NTM) N이 인식하는 언어 L(N)에 대해, L(N)을 인식하는 결정적 튜링 기계(DTM) D가 존재한다.

이 정리의 함의: NTM과 DTM은 인식 가능한 언어의 클래스에서 동등한 계산 능력을 갖는다. 비결정론은 “무엇을 계산할 수 있는가“를 확장하지 않으며, 오직 “얼마나 빠르게 계산할 수 있는가“에만 영향을 미칠 수 있다.

2. 증명의 구성

2.1 시뮬레이션 전략

증명은 DTM D가 NTM N의 모든 가능한 계산 경로를 체계적으로 탐색하는 시뮬레이션을 구성하는 것이다. NTM의 계산 트리(Computation Tree)를 DTM이 너비 우선 탐색(Breadth-First Search, BFS)으로 순회한다.

2.2 -테이프 DTM의 구성

NTM N을 시뮬레이션하는 DTM D를 3개의 테이프를 가진 다중 테이프 튜링 기계로 구성한다:

• 테이프 1 (입력 테이프): 입력 w의 원본을 저장한다. 계산 과정에서 변경되지 않으며, 각 시뮬레이션 경로의 시작 시 참조된다.
• 테이프 2 (작업 테이프): NTM의 현재 시뮬레이션 경로에서의 테이프 내용을 복제하여 시뮬레이션을 수행한다.
• 테이프 3 (경로 테이프): 현재 시뮬레이션 중인 비결정적 선택의 열을 저장한다. 이 열은 계산 트리에서의 현재 경로를 지정한다.

2.3 경로의 부호화

NTM의 분기 인수(Branching Factor)를 b라 하면, 각 비결정적 선택은 \{1, 2, \ldots, b\} 중 하나의 값으로 부호화된다. 길이 k의 경로는 b진수열 d_1 d_2 \cdots d_k로 표현되며, d_i는 i번째 단계에서의 비결정적 선택을 나타낸다.

2.4 DTM D의 동작

D는 다음의 절차를 수행한다:

1. 테이프 3을 빈 문자열 \epsilon으로 초기화한다.
2. 다음을 반복한다:
   a. 테이프 1의 내용을 테이프 2에 복사한다.
   b. 테이프 3에 기록된 경로 d_1 d_2 \cdots d_k를 사용하여, NTM N을 테이프 2 위에서 시뮬레이션한다. i번째 단계에서 \delta(q, a)가 여러 전이를 허용할 때, d_i번째 전이를 선택한다.
   c. 시뮬레이션 결과를 확인한다:

• NTM이 수락 상태에 도달하면: D는 수락한다.
• NTM이 거부하거나, 경로 길이를 초과하거나, d_i에 해당하는 전이가 존재하지 않으면: 다음 경로로 진행한다.
  d. 테이프 3의 내용을 사전식 순서(Lexicographic Order)에서 다음 문자열로 갱신한다.

2.5 경로 열거의 순서

경로의 열거는 너비 우선 순서를 따른다:

\epsilon, 1, 2, \ldots, b, 11, 12, \ldots, 1b, 21, 22, \ldots, bb, 111, \ldots

먼저 길이 0의 경로(초기 배치 자체), 다음에 길이 1의 모든 경로, 다음에 길이 2의 모든 경로, … 순서로 열거한다. 이 너비 우선 열거가 핵심적인데, 깊이 우선 탐색(Depth-First Search)을 사용하면 NTM의 무한 비수락 경로에서 DTM이 빠져나오지 못할 수 있기 때문이다.

증명의 정당성

완전성(Completeness)

w \in L(N)이면, NTM N의 계산 트리에서 수락 배치에 도달하는 경로가 존재한다. 이 경로의 길이를 k라 하면, DTM D는 길이 k 이하의 모든 경로를 열거하는 과정에서 반드시 이 수락 경로에 도달한다. 따라서 D는 w를 수락한다.

건전성(Soundness)

D가 w를 수락하면, 이는 DTM이 NTM의 어떤 계산 경로를 시뮬레이션하는 과정에서 수락 배치에 도달하였음을 의미한다. DTM의 시뮬레이션은 NTM의 전이 함수를 정확히 재현하므로, 이 경로는 NTM의 유효한 수락 경로이다. 따라서 w \in L(N)이다.

비정지 입력의 처리

w \notin L(N)이면, NTM의 계산 트리에서 어떤 경로도 수락 배치에 도달하지 않는다. 이 경우 DTM D도 수락하지 않는다. 그러나 DTM이 모든 경로를 열거하는 과정이 종료되지 않을 수 있으므로(NTM의 일부 경로가 무한할 때), DTM도 정지하지 않을 수 있다. 따라서 이 시뮬레이션은 L(N)의 인식(Recognition)만을 보장하며, 결정(Decision)은 보장하지 않을 수 있다.

보조 정리: NTM N이 결정기(Decider)이면, DTM D도 결정기로 수정할 수 있다. NTM이 모든 입력에 대해 모든 경로에서 정지하면, 계산 트리의 깊이가 유한하며, DTM은 유한 깊이까지의 모든 경로를 열거한 후 정지할 수 있다.

시간 복잡도 분석

NTM N이 입력 길이 n에 대해 시간 t(n)에 정지한다고 하자(모든 경로의 최대 깊이가 t(n)). 분기 인수가 b이면:

• 계산 트리의 잎 노드 수: 최대 b^{t(n)}
• 각 경로의 시뮬레이션에 O(t(n)) 단계 소요
• DTM의 총 시간: O(t(n) \cdot b^{t(n)})

NTM이 다항 시간 t(n) = n^k에 동작하면, DTM의 시뮬레이션 시간은 O(n^k \cdot b^{n^k})으로 지수적(Exponential)이다.

다중 테이프에서 단일 테이프로의 환원

위 증명에서 사용한 3-테이프 DTM은 표준 결과에 의해 단일 테이프 DTM으로 시뮬레이션 가능하다. k-테이프 튜링 기계의 t 단계 계산은 단일 테이프 튜링 기계로 O(t^2) 단계에 시뮬레이션할 수 있다(테이프 내용을 인터리브하여 단일 테이프에 저장하는 기법 사용).

따라서 NTM은 단일 테이프 DTM에 의해서도 시뮬레이션 가능하며, 동치성 정리가 단일 테이프 튜링 기계의 범위에서도 성립한다.

동치성의 이론적 의의

DTM과 NTM의 동치성은 처치-튜링 논제의 강건성(Robustness)을 입증하는 핵심 결과 중 하나이다. 비결정론이라는 강력한 추가적 능력을 기계에 부여하더라도 계산 가능한 함수의 클래스가 확장되지 않는다는 사실은, 튜링 기계에 의한 계산 가능성의 정의가 계산 모델의 세부 사항에 민감하지 않은 강건한 개념임을 보여준다.