3.6 튜링 기계의 상태 전이 테이블 표기법

1. 상태 전이 테이블의 정의

상태 전이 테이블(State Transition Table)은 튜링 기계의 전이 함수 $\delta$ 를 2차원 표 형태로 체계적으로 표현하는 방법이다. 테이블의 행(Row)은 기계의 상태를 나타내고, 열(Column)은 테이프 알파벳의 기호를 나타내며, 각 셀(Cell)에는 해당 상태-기호 쌍에 대한 전이 결과가 기록된다.

상태 전이 테이블은 전이 함수의 가장 명시적이고 체계적인 표현 형식이며, 소규모 튜링 기계의 동작을 완전하게 명세한다.

2. 테이블의 구조

상태 집합 $Q = \{q_0, q_1, \ldots, q_k, q_{\text{accept}}, q_{\text{reject}}\}$ 이고 테이프 알파벳 $\Gamma = \{a_1, a_2, \ldots, a_m, \sqcup\}$ 인 튜링 기계의 상태 전이 테이블은 다음과 같이 구성된다:

행: $Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}$ 의 각 상태에 대해 하나의 행이 할당된다. 수락 상태와 거부 상태는 정지 상태이므로 전이가 정의되지 않아 행에 포함되지 않는다.
열: $\Gamma$ 의 각 기호에 대해 하나의 열이 할당된다.
셀: 행 $q_i$ 와 열 $a_j$ 의 교차 셀에는 $\delta(q_i, a_j) = (q', b, D)$ 의 값이 기록된다.

3. 구체적 예시: 이진수 증가 기계

이진수를 1만큼 증가시키는 튜링 기계를 상태 전이 테이블로 설계한다. 이 기계는 테이프에 기록된 이진수의 최하위 비트(Least Significant Bit)가 오른쪽에 위치한다고 가정하며, 헤드는 최하위 비트에서 시작한다.

상태 집합: $Q = \{q_0, q_1, q_{\text{accept}}\}$

$q_0$ : 올림 전파 상태 (현재 자리에 1을 더하는 중)
$q_1$ : 왼쪽으로 복귀 상태 (증가 완료 후 시작 위치로 복귀)

입력 알파벳: $\Sigma = \{0, 1\}$
테이프 알파벳: $\Gamma = \{0, 1, \sqcup\}$

현재 상태	기호 $0$	기호 $1$	기호 $\sqcup$
$q_0$	$(q_1, 1, L)$	$(q_0, 0, L)$	$(q_1, 1, R)$
$q_1$	$(q_1, 0, L)$	$(q_1, 1, L)$	$(q_{\text{accept}}, \sqcup, R)$

3.1 동작 추적

입력 $110_2$ (십진수 6)에 대한 동작 추적:

초기 배치: 테이프에 $1\,1\,0$ 이 기록되고 헤드가 $0$ 위에 위치한다.

상태 $q_0$ , 읽은 기호 $0$ → 쓰기 $1$ , 상태 $q_1$ 로 전이, 왼쪽 이동.
테이프: $1\,1\,\mathbf{1}$ , 헤드가 두 번째 $1$ 위.
상태 $q_1$ , 읽은 기호 $1$ → 쓰기 $1$ , 상태 $q_1$ 유지, 왼쪽 이동.
테이프: $1\,\mathbf{1}\,1$ , 헤드가 첫 번째 $1$ 위.
상태 $q_1$ , 읽은 기호 $1$ → 쓰기 $1$ , 상태 $q_1$ 유지, 왼쪽 이동.
테이프: $\mathbf{1}\,1\,1$ , 헤드가 공백 위.
상태 $q_1$ , 읽은 기호 $\sqcup$ → 상태 $q_{\text{accept}}$ 로 전이. 정지.

결과: 테이프에 $111_2$ (십진수 7)이 기록된다. $6 + 1 = 7$ 이므로 올바른 결과이다.

4. 올림 발생의 예시

입력 $11_2$ (십진수 3):

$q_0$ , 기호 $1$ → 쓰기 $0$ , $q_0$ 유지, 왼쪽. 테이프: $1\,\mathbf{0}$ .
$q_0$ , 기호 $1$ → 쓰기 $0$ , $q_0$ 유지, 왼쪽. 테이프: $\mathbf{0}\,0$ .
$q_0$ , 기호 $\sqcup$ → 쓰기 $1$ , $q_1$ 로 전이, 오른쪽. 테이프: $1\,0\,\mathbf{0}$ .
$q_1$ , 기호 $0$ → 쓰기 $0$ , $q_1$ 유지, 왼쪽.
(계속 왼쪽 이동 후 공백에 도달하면 $q_{\text{accept}}$ .)

결과: $100_2$ (십진수 4). $3 + 1 = 4$ 이므로 올바르다.

5. -튜플 표기법과의 관계

상태 전이 테이블은 5-튜플 표기법의 표 형태 변환이다. 위의 이진수 증가 기계의 전이 테이블은 다음의 5-튜플 집합과 동치이다:

$\{(q_0, 0, q_1, 1, L), \, (q_0, 1, q_0, 0, L), \, (q_0, \sqcup, q_1, 1, R),$
$(q_1, 0, q_1, 0, L), \, (q_1, 1, q_1, 1, L), \, (q_1, \sqcup, q_{\text{accept}}, \sqcup, R)\}$

5-튜플 표기법은 전이를 개별적으로 열거하는 반면, 전이 테이블은 전체 전이 함수를 한눈에 파악할 수 있도록 시각화한다.

6. 상태 전이 다이어그램과의 비교

상태 전이 다이어그램(State Transition Diagram)은 전이 함수를 방향 그래프(Directed Graph)로 표현한다. 노드(Node)는 상태를, 방향 간선(Edge)은 전이를 나타내며, 간선에 “ $a \rightarrow b, D$ ”(기호 $a$ 를 읽으면 $b$ 를 쓰고 방향 $D$ 로 이동) 형태의 레이블이 부착된다.

전이 테이블과 전이 다이어그램은 동일한 정보를 담고 있으나, 표현 방식에서 다음의 차이가 있다:

측면	상태 전이 테이블	상태 전이 다이어그램
표현 형태	2차원 표	방향 그래프
완전성 확인	빈 셀로 미정의 전이 확인 용이	누락된 간선 확인이 상대적으로 어려움
흐름 파악	전체 규칙의 일괄 파악에 유리	상태 간 전이 경로의 시각적 추적에 유리
적합한 규모	소규모~중규모 기계	소규모 기계

7. 상태 전이 테이블의 복잡도

상태 전이 테이블의 크기는 $\vert Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\} \vert \times \vert \Gamma \vert$ 이다. $n$ 개의 비정지 상태와 $m$ 개의 테이프 기호가 있을 때, 테이블은 $n \times m$ 개의 셀을 갖는다.

가능한 서로 다른 전이 테이블의 수, 즉 가능한 튜링 기계의 수는:

$\vert Q \times \Gamma \times \{L, R\} \vert^{n \times m} = (2 \cdot (n+2) \cdot m)^{n \times m}$

이 수는 $n$ 과 $m$ 에 대해 초지수적(Super-Exponential)으로 증가하며, 비교적 소수의 상태와 기호만으로도 방대한 수의 서로 다른 튜링 기계가 가능함을 보여준다.

상태 전이 테이블의 실용적 의의

상태 전이 테이블은 튜링 기계의 설계, 분석, 시뮬레이션에서 표준적으로 사용되는 표기법이다.

설계: 문제를 해결하는 튜링 기계를 설계할 때, 상태와 기호의 조합에 대한 동작을 체계적으로 정의하는 데 전이 테이블이 사용된다.

검증: 전이 테이블의 각 셀을 점검하여 기계가 의도된 동작을 수행하는지 검증할 수 있다. 빈 셀(미정의 전이)의 존재 여부도 쉽게 확인된다.

시뮬레이션: 전이 테이블은 프로그램적으로 직접 구현 가능하며, 조회 테이블(Lookup Table)로서 $O(1)$ 시간에 각 전이를 결정할 수 있다.

상태 전이 테이블 표기법은 튜링 기계의 전이 함수를 가장 명시적이고 체계적으로 표현하는 방법이며, 계산 이론의 교육과 연구에서 기본적 도구로 활용된다.