3.8 튜링 기계의 연산 과정: 단계별 실행 추적

1. 실행 추적의 개념

실행 추적(Execution Trace)은 튜링 기계가 특정 입력에 대해 수행하는 계산 과정을 단계별로 기록한 것이다. 각 단계에서의 기계의 배치(Configuration)—현재 상태, 테이프 내용, 헤드 위치—를 순서대로 나열함으로써, 기계의 동작을 완전하게 재현할 수 있다.

실행 추적은 형식적으로 배치의 유한 또는 무한 열(Sequence)이다:

C_0 \vdash C_1 \vdash C_2 \vdash \cdots \vdash C_n

여기서 C_0는 초기 배치, C_i \vdash C_{i+1}은 한 단계의 전이, C_n은 정지 배치(수락 또는 거부)이다. 기계가 정지하지 않으면 열은 무한하다.

배치의 표기법

배치는 uq_iv 형태의 문자열로 표기한다:

• u \in \Gamma^*: 헤드 왼쪽의 테이프 내용
• q_i \in Q: 현재 상태
• v \in \Gamma^+: 헤드가 읽고 있는 기호부터 오른쪽의 테이프 내용(v의 첫 기호가 현재 헤드 위치의 기호)

예를 들어, 배치 01q_3110은 다음을 의미한다:

• 테이프 내용: ...01110...
• 헤드가 읽고 있는 기호: 1 (v = 110의 첫 기호)
• 현재 상태: q_3
• 헤드 왼쪽 테이프: 01

예시 1: 이진수 보수 기계

테이프에 기록된 이진 문자열의 모든 비트를 반전(0→1, 1→0)하는 튜링 기계를 설계하고 실행을 추적한다.

기계 설계

M = (\{q_0, q_{\text{accept}}\}, \{0, 1\}, \{0, 1, \sqcup\}, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})

전이 함수:

• \delta(q_0, 0) = (q_0, 1, R): 0을 1로 바꾸고 오른쪽 이동
• \delta(q_0, 1) = (q_0, 0, R): 1을 0으로 바꾸고 오른쪽 이동
• \delta(q_0, \sqcup) = (q_{\text{accept}}, \sqcup, L): 공백 도달 시 수락

1.1 입력 w = 1010에 대한 실행 추적

최종 테이프 내용: 0101. 원래 입력 1010의 비트별 보수이다.

배치 열:
q_0 1010 \vdash 0q_0 010 \vdash 01q_0 10 \vdash 010q_0 0 \vdash 0101q_0 \sqcup \vdash 010q_{\text{accept}} 1\sqcup

예시 2: 문자열 0^n1^n 인식기

L = \{0^n1^n \mid n \geq 1\}, 즉 0이 n개 연속하고 그 뒤에 1이 n개 연속하는 문자열을 인식하는 튜링 기계이다. 이 언어는 문맥 자유 언어(Context-Free Language)이나, 튜링 기계의 동작 원리를 설명하기 위한 교육적 예시로 적합하다.

기계 설계

전략: 테이프의 왼쪽 끝에서 가장 첫 번째 0을 X로 표시하고, 오른쪽으로 이동하여 가장 첫 번째 1을 Y로 표시한다. 왼쪽으로 돌아가서 다음 0을 찾아 반복한다. 모든 0과 1이 짝지어지면 수락한다.

상태:

• q_0: 시작, 왼쪽 끝에서 0을 찾는 상태
• q_1: 0을 X로 표시한 후 대응하는 1을 찾아 오른쪽으로 이동하는 상태
• q_2: 1을 Y로 표시한 후 왼쪽으로 돌아가는 상태
• q_3: 모든 짝 맞추기 완료 후 나머지 기호를 확인하는 상태

전이 함수:

• \delta(q_0, 0) = (q_1, X, R): 0을 X로 바꾸고 오른쪽으로
• \delta(q_0, Y) = (q_3, Y, R): 0이 없고 Y만 있으면 완료 확인
• \delta(q_1, 0) = (q_1, 0, R): 남은 0을 건너뜀
• \delta(q_1, Y) = (q_1, Y, R): 이미 표시된 Y를 건너뜀
• \delta(q_1, 1) = (q_2, Y, L): 1을 찾으면 Y로 바꾸고 왼쪽으로
• \delta(q_2, 0) = (q_2, 0, L): 0을 건너뛰며 왼쪽으로
• \delta(q_2, Y) = (q_2, Y, L): Y를 건너뛰며 왼쪽으로
• \delta(q_2, X) = (q_0, X, R): X에 도달하면 다시 오른쪽으로
• \delta(q_3, Y) = (q_3, Y, R): Y를 건너뜀
• \delta(q_3, \sqcup) = (q_{\text{accept}}, \sqcup, R): 공백 도달 시 수락

입력 w = 0011에 대한 실행 추적

기계는 12단계 만에 0011 \in L을 올바르게 수락하였다.

실행 추적의 분석적 의의

시간 복잡도의 측정

실행 추적의 단계 수는 기계가 해당 입력에 대해 소요하는 시간(Time)의 측도이다. 위 0^n1^n 인식기에서 입력 0^n1^n에 대한 단계 수는 O(n^2)이다. 각 짝 맞추기 단계에서 테이프를 좌우로 순회하며, 이 순회가 n번 반복된다.

공간 복잡도의 측정

실행 추적에서 헤드가 방문하는 셀의 최대 범위는 기계가 사용하는 공간(Space)의 측도이다.

정확성 검증

실행 추적은 기계의 정확성을 구체적 입력 사례에 대해 검증하는 직접적 방법이다. 각 단계에서 전이 함수가 올바르게 적용되었는지, 최종 결과가 기대와 일치하는지를 확인할 수 있다.

실행 추적은 추상적 튜링 기계의 동작을 구체적이고 명시적인 단계들의 열로 전개함으로써, 기계적 계산의 본질—형식적 규칙의 반복 적용에 의한 기호 변환—을 가장 직접적으로 보여주는 분석 도구이다.