3.3 튜링 기계의 형식적 정의와 구성 요소

1. 형식적 정의

튜링 기계(Turing Machine)는 다음의 7-튜플(7-Tuple)로 형식적으로 정의되는 추상적 계산 모델이다:

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$

각 구성 요소의 정의는 다음과 같다.

상태 집합 $Q$

$Q$ 는 유한하고 비어 있지 않은 상태(State)들의 집합이다. 기계의 유한 상태 제어 장치(Finite State Control)가 취할 수 있는 모든 내부 상태를 포함한다. 튜링의 원래 해석에서 이 상태들은 인간 계산자의 “마음의 상태(State of Mind)“에 대응한다.

상태 집합 $Q$ 에는 두 개의 특별한 상태가 포함된다:

$q_{\text{accept}} \in Q$ : 수락 상태(Accept State). 기계가 이 상태에 도달하면 계산이 종료되고 입력이 수락된다.
$q_{\text{reject}} \in Q$ : 거부 상태(Reject State). 기계가 이 상태에 도달하면 계산이 종료되고 입력이 거부된다.
$q_{\text{accept}} \neq q_{\text{reject}}$ 가 요구된다.

입력 알파벳 $\Sigma$

$\Sigma$ 는 유한하고 비어 있지 않은 입력 기호(Input Symbol)들의 집합이다. 기계에 제공되는 입력 문자열은 $\Sigma$ 의 기호로 구성된다. 공백 기호(Blank Symbol) $\sqcup$ 는 $\Sigma$ 에 포함되지 않는다: $\sqcup \notin \Sigma$ .

테이프 알파벳 $\Gamma$

$\Gamma$ 는 유한한 테이프 기호(Tape Symbol)들의 집합이다. 테이프의 각 셀에 기록될 수 있는 모든 기호를 포함한다. 다음의 포함 관계가 성립한다:

$\Sigma \subset \Gamma, \quad \sqcup \in \Gamma$

$\Gamma$ 는 입력 알파벳 $\Sigma$ 의 모든 기호와 공백 기호 $\sqcup$ , 그리고 계산 과정에서 필요한 추가 작업 기호(Auxiliary Symbol)를 포함한다.

1.1 전이 함수 $\delta$

전이 함수는 기계의 동작 규칙을 정의하는 함수로서, 기계의 핵심 구성 요소이다. 결정론적 튜링 기계(Deterministic Turing Machine)의 전이 함수는 다음과 같이 정의된다:

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

전이 함수의 해석: 현재 상태가 $q \in Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}$ 이고 헤드가 읽은 기호가 $a \in \Gamma$ 일 때, $\delta(q, a) = (q', b, D)$ 는 다음을 의미한다:

기계의 상태를 $q$ 에서 $q'$ 로 전이한다.
현재 셀의 기호 $a$ 를 $b$ 로 덮어쓴다.
헤드를 방향 $D \in \{L, R\}$ 로 한 셀 이동한다. $L$ 은 왼쪽, $R$ 은 오른쪽이다.

수락 상태와 거부 상태에서는 전이 함수가 정의되지 않으며, 기계가 이 상태에 도달하면 즉시 정지(Halt)한다.

시작 상태 $q_0$

$q_0 \in Q$ 는 기계가 계산을 시작할 때의 초기 상태이다. 모든 계산은 시작 상태 $q_0$ 에서 개시된다.

물리적 구성 요소의 상세 기술

무한 테이프(Infinite Tape)

테이프는 셀(Cell)의 무한한 선형 배열이다. 각 셀은 테이프 알파벳 $\Gamma$ 의 기호 중 정확히 하나를 저장한다. 표준적 정의에서 테이프는 오른쪽으로 무한하다(왼쪽 끝은 존재). 일부 정의에서는 양방향으로 무한한 테이프를 사용하나, 두 정의는 계산적으로 동치이다.

계산 시작 시, 입력 문자열 $w = w_1 w_2 \cdots w_n$ 이 테이프의 처음 $n$ 개 셀에 기록되고, 나머지 모든 셀은 공백 기호 $\sqcup$ 로 채워져 있다.

테이프는 다음의 세 가지 기능을 수행한다:

입력 저장: 기계에 제공되는 입력 데이터를 저장한다.
작업 공간: 계산 과정에서의 중간 결과를 저장한다.
출력 저장: 계산의 최종 결과를 저장한다.

테이프의 무한성은 이론적 이상화이며, 기계가 사용하는 테이프의 양이 원리적으로 제한되지 않음을 보장한다. 실제 계산에서 사용되는 테이프의 양은 항상 유한하다.

읽기/쓰기 헤드(Read/Write Head)

헤드는 매 시점에서 테이프의 정확히 하나의 셀 위에 위치한다. 헤드는 다음의 세 가지 동작을 수행한다:

읽기(Read): 현재 위치한 셀의 기호를 읽는다.
쓰기(Write): 현재 위치한 셀에 새로운 기호를 기록한다(기존 기호를 덮어쓴다).
이동(Move): 왼쪽(L) 또는 오른쪽(R)으로 정확히 한 셀 이동한다.

계산 시작 시, 헤드는 테이프의 가장 왼쪽 셀(입력의 첫 번째 기호) 위에 위치한다.

유한 상태 제어 장치(Finite State Control)

유한 상태 제어 장치는 기계의 현재 내부 상태를 유지하고, 전이 함수에 따라 기계의 동작을 결정하는 장치이다. 매 계산 단계에서, 제어 장치는 현재 상태 $q$ 와 헤드가 읽은 기호 $a$ 를 전이 함수 $\delta$ 에 입력하여 다음 상태 $q'$ , 쓸 기호 $b$ , 이동 방향 $D$ 를 결정한다.

제어 장치의 상태 수가 유한하다는 것은 기계의 “기억 용량“이 유한함을 의미한다. 그러나 무한한 테이프가 추가적 기억 공간을 제공하므로, 기계 전체의 기억 용량은 무한하다.

배치(Configuration)의 형식적 정의

튜링 기계의 순간적 전체 상태는 배치(Configuration)로 기술된다. 배치는 세 가지 정보를 포함한다:

현재 상태 $q \in Q$
테이프의 현재 내용
헤드의 현재 위치

형식적으로, 배치는 문자열 $uqv$ 로 표기한다. 여기서:

$u \in \Gamma^*$ : 헤드 왼쪽의 테이프 내용(공백이 아닌 부분)
$q \in Q$ : 현재 상태
$v \in \Gamma^*$ : 헤드 위치부터 오른쪽의 테이프 내용(공백이 아닌 부분). $v$ 의 첫 번째 기호가 헤드가 현재 읽고 있는 기호이다.

초기 배치

입력 $w$ 에 대한 초기 배치는 $q_0 w$ 이다. 기계가 시작 상태 $q_0$ 에 있고, 헤드가 $w$ 의 첫 번째 기호 위에 있다.

수락 배치와 거부 배치

$q_{\text{accept}}$ 를 포함하는 배치를 수락 배치(Accepting Configuration)라 ��고, $q_{\text{reject}}$ 를 포함하는 배치를 거부 배치(Rejecting Configuration)라 한다. 이들은 정지 배치(Halting Configuration)이다.

배치 전이(Configuration Transition)

배치 $C_1$ 에서 배치 $C_2$ 로의 전이는 $C_1 \vdash_M C_2$ 로 표기하며(또는 문맥이 명확할 때 $C_1 \vdash C_2$ ), 전이 함수 $\delta$ 의 한 번 적용에 의해 $C_1$ 에서 $C_2$ 가 도출됨을 의미한다.

구체적으로:

배치 $uaq_ibv$ 에서 $\delta(q_i, b) = (q_j, c, L)$ 이면 $uaq_ibv \vdash uq_jacv$ (헤드가 왼쪽으로 이동)
배치 $uaq_ibv$ 에서 $\delta(q_i, b) = (q_j, c, R)$ 이면 $uaq_ibv \vdash uacq_jv$ (헤드가 오른쪽으로 이동)

$\vdash^*$ 는 $\vdash$ 의 반사적·추이적 폐포(Reflexive Transitive Closure)를 나타내며, $C_1 \vdash^* C_2$ 는 $C_1$ 에서 유한 번(0회 포함)의 전이로 $C_2$ 에 도달함을 의미한다.

튜링 기계에 의한 언어의 인식과 결정

인식(Recognition)

튜링 기계 $M$ 이 문자열 $w$ 를 수락(Accept)한다 함은, 초기 배치 $q_0 w$ 에서 시작하여 유한 번의 전이 후 수락 배치에 도달함을 의미한다:

$q_0 w \vdash^* \alpha q_{\text{accept}} \beta \quad (\alpha, \beta \in \Gamma^*)$

$M$ 이 인식하는 언어 $L(M)$ 은 $M$ 이 수락하는 모든 문자열의 집합이다:

$L(M) = \{w \in \Sigma^* \mid M \text{ accepts } w\}$

결정(Decision)

기계 $M$ 이 결정기(Decider)라 함은, 모든 입력 $w \in \Sigma^*$ 에 대해 $M$ 이 정지함을 의미한다. 결정기는 모든 입력을 수락 또는 거부하며, 무한 루프에 빠지지 않는다.

언어 $L$ 이 결정 가능(Decidable) 또는 재귀적(Recursive)이라 함은, $L$ 을 결정하는 결정기가 존재함을 의미한다.

이 구별—인식 가능(Recognizable)과 결정 가능(Decidable)—은 계산 이론의 근본적 구분이며, 결정 불가능한(Undecidable) 문제의 존재가 튜링의 핵심 결과이다.