3.16 보편 튜링 기계의 입력 인코딩과 시뮬레이션 원리

1. 입력 인코딩의 필요성

보편 튜링 기계(Universal Turing Machine, UTM) $U$ 가 임의의 튜링 기계 $M$ 을 시뮬레이션하기 위해서는 $M$ 의 완전한 명세를 $U$ 의 입력 알파벳으로 부호화하는 체계적이고 효과적인 인코딩(Encoding) 방법이 필수적이다. 인코딩은 다음의 조건을 만족해야 한다:

완전성(Completeness): $M$ 의 동작을 결정하는 모든 정보가 인코딩에 포함되어야 한다.
유일성(Uniqueness): 각 튜링 기계에 대해 (관례적 표준화를 적용한 후) 유일한 인코딩이 대응되어야 한다.
해독 가능성(Decodability): $U$ 가 인코딩으로부터 $M$ 의 구성 요소를 기계적으로 복원할 수 있어야 한다.

2. 표준 이진 인코딩

2.1 기본 부호화 규칙

상태, 기호, 이동 방향을 이진 문자열로 부호화하는 표준적 방법을 기술한다.

상태의 부호화: $Q = \{q_1, q_2, \ldots, q_n\}$ 에서 상태 $q_i$ 를 $0^i$ (0의 $i$ 번 반복)로 부호화한다. 관례적으로 $q_1 = q_0$ (시작 상태), $q_2 = q_{\text{accept}}$ , $q_3 = q_{\text{reject}}$ 로 지정한다.

기호의 부호화: $\Gamma = \{a_1, a_2, \ldots, a_m\}$ 에서 기호 $a_j$ 를 $0^j$ 로 부호화한다. 관례적으로 $a_1 = 0$ , $a_2 = 1$ , $a_3 = \sqcup$ (공백)으로 지정한다.

이동 방향의 부호화: $L$ 을 $0$ 으로, $R$ 을 $00$ 으로 부호화한다.

2.2 전이 규칙의 부호화

전이 $\delta(q_i, a_j) = (q_k, a_l, D)$ 는 5-튜플로 부호화된다:

$\langle \delta(q_i, a_j) \rangle = 0^i 1 0^j 1 0^k 1 0^l 1 \langle D \rangle$

여기서 $1$ 은 각 구성 요소 사이의 구분자(Separator)이다.

기계 전체의 부호화

전이 함수의 모든 규칙을 나열하고, 규칙 사이를 $11$ (이중 구분자)로 구분한다:

$\langle M \rangle = \langle \delta_1 \rangle \; 11 \; \langle \delta_2 \rangle \; 11 \; \cdots \; 11 \; \langle \delta_p \rangle$

여기서 $\langle \delta_i \rangle$ 는 $i$ 번째 전이 규칙의 부호화이다.

2.3 완전한 입력의 구성

보편 튜링 기계 $U$ 에 제공되는 완전한 입력은:

$\langle M \rangle \; 111 \; w$

여기서 $111$ (삼중 구분자)은 기계 부호화와 입력 문자열 $w$ 를 분리한다.

대안적 인코딩: 괴델 수 인코딩

소수 지수 부호화

괴델의 방법에 따라 전이 규칙의 열을 소수의 지수(Exponent)로 부호화할 수 있다. 5-튜플 $(i, j, k, l, d)$ 에 대해:

$\text{code}(\delta) = 2^i \cdot 3^j \cdot 5^k \cdot 7^l \cdot 11^d$

전이 규칙의 열 $(\delta_1, \delta_2, \ldots, \delta_p)$ 에 대해:

$\langle M \rangle = 2^{\text{code}(\delta_1)} \cdot 3^{\text{code}(\delta_2)} \cdot \cdots \cdot p_n^{\text{code}(\delta_p)}$

여기서 $p_n$ 은 $n$ 번째 소수이다. 이 부호화는 소인수분해의 유일성(산술의 기본 정리)에 의해 부호화의 유일성이 보장된다.

실용적 고려

괴델 수 인코딩은 이론적으로 명쾌하지만, 수의 크기가 폭발적으로 증가하여 실용적이지 않다. 이진 문자열 인코딩이 실용적 관점에서 선호된다.

시뮬레이션의 상세 원리

$U$ 의 내부 구조

3-테이프 보편 튜링 기계 $U$ 의 내부 구조:

테이프 1 (기계 기술 테이프): $\langle M \rangle$ 을 저장한다. 계산 과정에서 변경되지 않는다.
테이프 2 (시뮬레이션 테이프): $M$ 의 테이프를 시뮬레이션한다. 초기에 $w$ 가 기록되고, 계산 과정에서 $M$ 의 테이프와 동일하게 변경된다.
테이프 3 (상태 테이프): $M$ 의 현재 상태의 부호화를 저장한다.

시뮬레이션의 한 단계

$U$ 가 $M$ 의 한 계산 단계를 시뮬레이션하는 과정:

상태 읽기: 테이프 3에서 $M$ 의 현재 상태의 부호화 $0^i$ 를 읽는다.
기호 읽기: 테이프 2의 헤드가 위치한 셀에서 $M$ 의 현재 기호의 부호화를 읽는다.
전이 조회: 테이프 1을 순회하며, 현재 상태-기호 쌍 $(0^i, 0^j)$ 에 대응하는 전이 규칙을 검색한다. 이 검색은 테이프 1의 각 전이 규칙을 순차적으로 비교하여 수행된다.
전이 실행:
a. 테이프 3에 새로운 상태의 부호화 $0^k$ 를 기록한다.
b. 테이프 2의 현재 셀에 새로운 기호의 부호화를 기록한다.
c. 테이프 2의 헤드를 지정된 방향으로 이동한다.
종료 확인: 테이프 3의 상태가 수락 상태( $0^2$ )이면 $U$ 가 수락하고, 거부 상태( $0^3$ )이면 $U$ 가 거부한다.

시뮬레이션의 오버헤드

$M$ 이 시간 $t$ 에 정지한다고 할 때, $U$ 의 시뮬레이션 시간은 다음과 같다:

$M$ 의 한 단계 시뮬레이션에서 테이프 1의 전이 조회에 $O(\vert \langle M \rangle \vert)$ 단계가 소요된다.
$M$ 의 $t$ 단계 전체 시뮬레이션에 $O(t \cdot \vert \langle M \rangle \vert)$ 단계가 소요된다.
$\vert \langle M \rangle \vert$ 은 $M$ 의 크기(상태 수 × 기호 수에 비례)에 의존하며, 특정 $M$ 에 대해 상수이다.

시뮬레이션의 정확성 증명

귀납적 증명

$U$ 의 시뮬레이션이 $M$ 의 계산을 정확히 재현함을 수학적 귀납법(Mathematical Induction)으로 증명한다.

기저 단계(Base Case): 시뮬레이션 시작 시, 테이프 2에 $w$ 가 기록되고, 테이프 3에 $M$ 의 시작 상태 $q_0$ 의 부호화가 기록된다. 이는 $M$ 의 초기 배치와 일치한다.

귀납 단계(Inductive Step): $M$ 의 $i$ 번째 배치 $C_i$ 에 대한 시뮬레이션이 정확하다고 가정한다. $U$ 가 위 절차에 따라 전이를 수행하면, 테이프 2와 테이프 3의 상태가 $M$ 의 $(i+1)$ 번째 배치 $C_{i+1}$ 에 정확히 대응함을 보인다.

전이 조회의 정확성— $\langle M \rangle$ 에서 $(0^i, 0^j)$ 쌍에 대응하는 규칙을 올바르게 검색—이 귀납 단계의 핵심이며, 이는 인코딩의 해독 가능성 조건에 의해 보장된다.

인코딩의 이론적 의의

튜링 기계의 인코딩은 “프로그램을 데이터로 취급한다“는 원리의 형식적 실현이다. 이 원리는 다음의 결과를 가능하게 한다:

자기 참조(Self-Reference): 튜링 기계가 자기 자신의 부호화를 입력으로 처리할 수 있다.
대각선 논법(Diagonalization): 튜링 기계의 열거 가능성을 이용하여 결정 불가능성을 증명할 수 있다.
범용 계산(Universal Computation): 단일 기계가 임의의 계산을 수행할 수 있다.
저장 프로그램(Stored Program): 프로그램과 데이터가 동일한 매체에 동일한 형태로 저장된다.

인코딩은 추상적 기계를 구체적 기호열로 변환하는 다리이며, 이 다리를 통해 기계에 관한 물음이 기호열에 관한 물음으로 변환되어 형식적으로 분석 가능해진다.