3.12 비결정적 튜링 기계(NTM)의 정의와 분기 구조

1. 비결��론의 의미

비결정론(Nondeterminism)은 체계의 동작이 현재 상태에 의해 유일하게 결정되지 않고, 여러 가능한 동작 중 하나가 선택되는 원리이다. 비결정적 튜링 기계(Nondeterministic Turing Machine, NTM)에서 전이 함수는 동일한 상태-기호 쌍 $(q, a)$ 에 대해 여러 가능한 전이를 허용한다.

비결정론은 물리적으로 구현 가능한 메커니즘이 아니라 이론적 개념이다. 비결정적 기계는 매 분기점에서 “올바른” 선택을 “추측“하는 것으로 해석되며, 이 추측 능력이 비결정�� 기계에 추가적인 계산 능력(계산 가능성이 아닌 효율성의 관점에서)을 부여할 수 있다.

2. NTM의 형식적 정의

비결정적 튜링 기계 $N$ 은 결정적 튜링 기계와 동일한 7-튜플 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ 로 정의되되, 전이 함수 $\delta$ 의 정의가 다르다:

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

여기서 $\mathcal{P}(\cdot)$ 는 멱집합(Power Set)을 나타낸다. 즉, $\delta(q, a)$ 는 $Q \times \Gamma \times \{L, R\}$ 의 부분집합이며, 하나 이상의 가능한 전이를 포함할 수 있다.

예를 들어, $\delta(q_3, 0) = \{(q_5, 1, R), (q_7, 0, L)\}$ 은 상태 $q_3$ 에서 기호 $0$ 을 읽을 때, 기계가 두 가지 전이 중 하나를 비결정적으로 선택할 수 있음을 의미한다.

계산 트리(Computation Tree)

분기 구조

NTM의 계산은 선형 배치열이 아닌 분기하�� 트리 구조를 형성한다. 이를 계산 트리(Computation Tree)라 한다.

루트(Root): 초기 배치 $C_0 = q_0 w$ .
분기(Branching): ��결정적 전이가 가능한 배치에서 여러 ��식 노드로 분기한다. $\delta(q, a)$ 가 $k$ 개의 가능한 전이를 포함��면, 해당 ��드에서 $k$ 개의 자식 노드가 생성된다.
잎(Leaf): 수락 배치, 거부 배치, 또는 비정지 경로의 종점이다.

NTM의 수락 조건

NTM $N$ 이 입력 $w$ 를 수락한다 함은, 계산 트리에서 적어도 하나의 경로(Branch)가 수락 상태에 도달함을 의미한다. 모든 경로가 거부하거나 정지하지 않더라도, 하나의 경로라도 수락하면 ��력은 수락된다.

형식적으로:

$N \text{ accepts } w \iff \exists \text{ 경로 } C_0, C_1, \ldots, C_k \text{ s.t. } C_k \text{는 수락 배치}$

이 정의는 NTM을 “존재적(Existential)” 기계로 해석하는 것이다: 수락 경로가 존재하면 수락한다.

3. 분기 인수(Branching Factor)

NTM의 �� 배치에�� 가능한 후속 배치의 최대 수를 분기 인수(Branching Factor) $b$ 라 한다:

$b = \max_{(q, a) \in (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma} \vert \delta(q, a) \vert$

깊이 $t$ 의 계산 트리에서 잎 노드의 최�� 수는 $b^t$ 이다. 이 지수적 분기가 NTM의 “추측 능력“의 원천이다.

NTM과 DTM의 동치성

인식 동치성

NTM과 DTM은 인식 가능한(Recognizable) 언어의 클래스에서 동치이다. 즉, NTM이 인식하는 모든 언어는 DTM에 의해서도 인식 가능하다.

정리: 언어 $L$ 이 NTM에 의해 인식 가능하면, $L$ 은 DTM에 의해서도 인식 가능하다.

증명의 핵심 아이디어: DTM이 NTM의 계산 트리를 너비 우선 탐색(Breadth-First Search)으로 시뮬레이션한다. DTM은 NTM의 모든 가능한 분기를 체계적으로 열거하며, 어떤 분기가 수락 상태에 도달하면 DTM도 수락한다.

구체적으로, 3-테이프 DTM을 사용한다:

테이프 1: 입력 $w$ 의 원본 (변경 없이 보존)
테이프 2: NTM의 현�� 시뮬레이션 경로에서의 테이프 내용
테이프 3: 현재 시뮬레이션 중인 경로를 지정하는 비결정적 선택의 열

시간 복잡도의 차이

NTM이 시간 $t(n)$ 에 입력을 처리한다면, DTM의 시뮬레이션은 최대 $O(b^{t(n)})$ 시간이 소요된다(너비 우선 탐색의 경우). 이는 지수적 시간 증가를 의미한다.

따라서 NTM과 DTM은 “무엇을 계산할 수 있는가”(계산 가능성)에서 동등하지만, “얼마나 빨리 계산할 수 있는가”(시간 복잡도)에서는 차이가 존재할 수 있다.

P 대 NP 문제

NTM과 DTM의 시간 복잡도 차이의 본질에 관한 물음이 P 대 NP 문제이다.

$\text{P} = \bigcup_{k \geq 0} \text{DTIME}(n^k) \quad \text{(결정적 다항 시간)}$

$\text{NP} = \bigcup_{k \geq 0} \text{NTIME}(n^k) \quad \text{(비결정적 다항 시간)}$

$\text{P} \subseteq \text{NP}$ 는 자명하다(DTM은 분기 ��수 1인 NTM이다). $\text{P} = \text{NP}$ 인지, 즉 비결정적 다항 시간에 해결 가능한 모든 문제가 결정적 다항 시간에도 해결 가능한지는 미해결 문제(Open Problem)이며, 클레이 수학 연구소(Clay Mathematics Institute)가 지정한 밀레니엄 문제(Millennium Prize Problems) 중 하나이다.

NTM의 대안적 해석

검증자(Verifier)로서의 해석

NP 클래스의 대안적 정의는 검증자(Verifier)에 기반한다. 언어 $L \in \text{NP}$ 는 ��항 시간 DTM 검증자 $V$ 가 존재하여, $w \in L$ 이면 $V$ 가 다항 길이의 증명서(Certificate) $c$ 를 사용하여 $w \in L$ 을 확인할 수 있는 언어이다.

이 해석에서 NTM의 비결��적 선택 ��로는 증명서에, NTM의 결정적 후속 계산은 검증에 대응한다.

병렬 계산으로서의 해석

NTM은 각 분기점에서 모든 가능한 전이를 동시에 (병렬로) 수행하는 ��계로 해석할 수도 있다. 이 해석에서 NTM은 무한한 병렬 계산 능력을 가진 기계이다.

NTM의 학문사적 의의

비결정적 튜링 기계는 계산 복잡도 이론(Computational Complexity Theory)의 핵심 개념이다. NTM은 물리적으로 구현 가능한 기계 모��이 아니지만, 문제의 난이도를 분류하고 알고리즘적 효율의 근본적 한계를 탐구하는 데 필수적인 이론적 도구이다. DTM과 NTM의 관계에 대한 물음은 컴퓨터 과학에서 가장 중요한 미해결 문제(P vs NP)로 남아 있으며, 이 문제의 해결은 최적화, 암호학, 인공지능 등 광범위한 분야에 심대한 영향을 미칠 것이다.