Turing Machine — 계산의 극한

DFA에 스택을 추가하면 DPDA, 스택을 2개로 늘리면 튜링 머신과 동등해진다. 그렇다면 튜링 머신 자체는 어떤 구조를 가지며, 얼마나 강력할까?

DTM(Deterministic Turing Machine)은 현재 컴퓨터의 이론적 모델이다. 1936년 앨런 튜링이 제안했다.

Church-Turing 논제는 이 모델의 위치를 정한다. 내용은 “기계적인 절차로 계산 가능한 함수는 모두 튜링 머신으로 계산할 수 있다”이다. 등식의 한쪽은 수학적으로 정의된 개념이지만 다른 쪽(“기계적인 절차”)은 직관에 기댄 말이라, 이것은 증명된 정리가 아니라 논제다. 근거는 서로 다른 동기에서 제안된 계산 모델들 — 람다 계산, 귀납적 함수, 레지스터 기계 — 이 하나같이 같은 함수 집합을 계산한다는 사실이다.

여기서 흔한 오해 하나를 짚어 두자. 이 논제는 “튜링 머신보다 강한 계산 모델은 존재하지 않는다”는 주장이 아니다. 신탁 기계(oracle machine)처럼 튜링 머신이 흉내 낼 수 없는 모델을 수학적으로 정의하는 것은 얼마든지 가능하다. 논제가 말하는 것은 그런 모델이 기계적 절차에 해당하지 않는다는 쪽이다.

---

튜링 머신의 구조

튜링 머신은 다음 여섯 가지 요소의 튜플로 정의한다.

$$M = (Q,\ \Sigma,\ \Gamma,\ q_0,\ F,\ \delta)$$

• $Q$: State들의 집합
• $\Sigma$: 입력 알파벳 (Input alphabet). 입력으로 들어올 수 있는 심볼들의 집합
• $\Gamma$: 테이프 알파벳 (Tape alphabet). 테이프에 쓸 수 있는 심볼들의 집합. $\Sigma \subseteq \Gamma$이며, 공백(blank) 심볼 $\sqcup$도 포함한다
• $q_0$: 초기 상태 (Initial state)
• $F$: 최종 상태들의 집합 (Final/Accepting states)
• $\delta$: 전이 함수 (Transition function)

전이 함수는 다음과 같이 표현한다.

$$(q,\ a) \to (r,\ b,\ R)$$

현재 상태가 $q$이고 헤드가 $a$를 읽으면, $b$를 쓰고 헤드를 오른쪽($R$)으로 이동한 뒤 상태를 $r$로 전환한다. 헤드의 이동 방향은 Left($L$), Right($R$), Stay($S$), 세 가지다.

---

L13: 튜링 머신으로 문제 풀기

$$L_{13} = \{x \mid x = y \mathtt{2} y,\ y \in \{0, 1\}^*\}$$

구분자 $\mathtt{2}$를 기준으로 앞뒤의 문자열 $y$가 동일한지 검사하는 문제다.

동작 방식 (왕복 스캔):

마킹 기호는 $3$(처리된 $0$)과 $4$(처리된 $1$)다. 아래를 반복한다.

1. 왼쪽에서 첫 미처리 심볼 찾기. 테이프 왼쪽 끝에서 오른쪽으로 이동하며 $3$과 $4$를 건너뛴다.
   • 처음 만나는 심볼이 $0$이면 $3$으로, $1$이면 $4$로 덮어쓰고, 그 값을 상태에 기억한다. 이 목적으로 상태를 둘 둔다. $q_{\text{찾음-}0}$과 $q_{\text{찾음-}1}$이다. 테이프에는 마커만 남고 원래 값은 상태가 들고 간다.
   • $3, 4$만 건너뛰다 곧바로 $\mathtt{2}$를 만나면 왼쪽 절반을 다 처리한 것이므로 5번으로 간다.
2. 구분자까지 이동. 오른쪽으로 이동해 남은 $0, 1$을 지나 $\mathtt{2}$에 닿는다. 상태는 그대로 유지한다.
3. 오른쪽에서 대응 위치 찾기. $\mathtt{2}$를 지난 뒤에도 계속 오른쪽으로 가며 $3$과 $4$를 건너뛴다. 처음 만나는 미처리 심볼이 곧 대응 위치다.
   • 왜 그 자리가 같은 인덱스인가. 양쪽 모두 왼쪽부터 순서대로 마킹되므로, 이번 반복이 왼쪽의 $k$번째를 방금 마킹했다면 오른쪽에는 정확히 $k-1$개가 마킹돼 있다. 그것들을 건너뛰고 처음 만나는 것이 오른쪽의 $k$번째다.
   • 상태가 기억한 값과 같으면 대응하는 마커로 덮어쓴다. 다르면 reject.
   • 미처리 심볼을 만나기 전에 공백 $\sqcup$에 닿으면 오른쪽이 더 짧은 것이므로 reject.
4. 왼쪽 끝으로 복귀. 왼쪽으로 이동해 테이프의 왼쪽 끝에 닿으면 1번으로 돌아간다.
5. 종료 검사. 왼쪽이 모두 마킹된 상태에서 $\mathtt{2}$ 오른쪽을 훑는다. 남은 것이 전부 $3, 4$이면 accept, $0$이나 $1$이 하나라도 남아 있으면 오른쪽이 더 긴 것이므로 reject.

왜 반드시 멈추는가. 1번을 한 번 돌 때마다 미처리 심볼이 최소 하나 줄어든다. 심볼 수가 유한하므로 반복은 입력 길이를 넘지 못하고, 각 반복의 왕복 스캔도 테이프를 한 번씩 훑을 뿐이라 유한하다.

왜 맞는 답을 내는가. 반복 시작 시점마다 다음 불변식이 유지된다. 양쪽 절반의 앞 $k-1$개가 마킹돼 있고, 그 자리들은 서로 같았다. 3번의 인덱스 논증이 이 불변식을 한 칸 늘리고, 어긋난 자리를 만나면 그 자리에서 reject한다. 끝까지 어긋나지 않으면서 5번의 길이 검사까지 통과할 때만 accept하므로, accept되는 입력은 정확히 $y\mathtt{2}y$ 꼴이다.

이 예시를 통해 알 수 있는 핵심은, 튜링 머신의 좌/우 이동 전이 함수만으로도 복잡한 문제를 해결할 수 있다 는 점이다. 인덱스를 세는 카운터가 없어도, 마커와 상태 몇 개로 “같은 자리끼리 비교하기”가 구현된다.

---

2-Tape DTM

테이프를 2개로 늘리면 계산 능력이 향상될까?

DPDA에 스택을 1개 더 추가했을 때는 튜링 머신과 동등해질 만큼 계산 능력이 크게 늘었다. 그러나 튜링 머신의 테이프를 2개로 늘려도 계산 능력 자체는 변하지 않는다.

이유는 튜링 머신의 테이프가 한 방향으로 무한하기 때문이다. 1개의 무한한 테이프를 두 구역으로 나누어 사용하면 2개의 테이프 역할을 충분히 대신할 수 있다. 다만 두 테이프를 번갈아 읽어야 하므로 시간이 더 걸릴 수 있다.

이 성질은 차원으로도 확장된다. 2차원 테이프 역시 마찬가지 인코딩으로 1개의 1차원 테이프로 표현할 수 있다.

---

Universal Turing Machine (UTM)

2-Tape DTM을 활용한 특별한 모델이다. 임의의 튜링 머신 M을 시뮬레이션 하는 튜링 머신이다.

동작 방식:

• 테이프 1: 시뮬레이션할 튜링 머신 M의 rule set(전이 함수 목록)을 기록한다. 모든 규칙은 이진수로 인코딩할 수 있다.
• 테이프 2: M의 초기 상태 $q_0$를 맨 앞에 기록하고, 이어서 M의 테이프 내용을 기록한다. 헤드의 현재 위치도 마킹한다.

실행 시, 테이프 2에서 현재 상태와 심볼을 읽어 테이프 1의 rule set과 비교한다. 매치되는 규칙이 있으면 해당 전이를 실행한다.

테이프 1의 내용을 M’의 rule set으로 교체하면 M’을 시뮬레이션할 수 있다. 즉, UTM은 어떤 튜링 머신이든 시뮬레이션할 수 있는 튜링 머신 이다.

이것이 현재 컴퓨터의 이론적 기반이다. 폰 노이만(John von Neumann)은 UTM의 개념을 실제 컴퓨터 설계에 적용하여, 프로그램을 메모리에 저장하고 순차적으로 실행하는 폰 노이만 아키텍처(Von Neumann Architecture) 를 고안했다. 이는 EDVAC 설계 보고서(1945)에서 처음 제시되었으며, 오늘날 거의 모든 컴퓨터의 구조적 기반이다.

---

DTM vs NTM: 계산 능력은 같다

지금까지의 결과를 정리하면 다음과 같다.

• DFA = NFA
• DPDA ≠ NPDA
• DTM = NTM

DPDA와 NPDA는 계산 능력이 달랐지만, DTM과 NTM은 동일하다. UTM을 이용해 이를 증명할 수 있다.

NTM이란?

NTM(Non-deterministic Turing Machine)은 동일한 상태와 심볼에 대해 여러 전이 규칙을 가질 수 있는 튜링 머신이다.

예를 들어 $(q, a) \to (r, b, R)$과 $(q, a) \to (r, c, R)$이 동시에 존재할 수 있다.

증명: UTM으로 NTM 시뮬레이션

UTM은 DTM이다. UTM으로 NTM을 시뮬레이션할 수 있다면, DTM = NTM이 된다.

NTM의 실행은 선택 지점마다 가지가 갈라지는 계산 트리(computation tree) 로 나타낼 수 있다. UTM은 이 트리를 BFS(너비 우선 탐색)로 순회하며 모든 가능한 경로를 탐색한다.

그림은 계산 트리만 나타내며, 실제 시뮬레이션에서 필요한 별도 테이프 복사 과정은 본문 설명에 포함된다.

1. 현재 상태와 심볼을 읽고, 대응되는 모든 전이 규칙을 찾는다.
2. 각 규칙을 적용한 결과를 별도의 테이프에 복사하고, 각각을 독립적으로 시뮬레이션한다.
3. 시뮬레이션된 경로 중 하나라도 accept 상태에 도달하면 전체를 accept한다.

NTM이 accept한다면 UTM도 그 경로를 탐색하여 accept하므로, DTM = NTM이 성립한다.

$$\text{Class DTM} = \text{Class NTM}$$

---

결론

모델	결정론 vs 비결정론	계산 능력
DFA vs NFA	동일	Regular Languages
DPDA vs NPDA	다름	DCFL ⊊ CFL
DTM vs NTM	동일	Recursively Enumerable