3.5 전이 함수(Transition Function)의 수학적 정의

1. 전이 함수의 정의

전이 함수(Transition Function)는 튜링 기계의 동작 규칙을 형식적으로 명세하는 함수이다. 전이 함수는 기계의 현재 상태와 헤드가 읽은 기호를 입력으로 받아, 다음 상태, 쓸 기호, 헤드의 이동 방향을 출력으로 산출한다.

1.1 결정론적 튜링 기계의 전이 함수

결정론적 튜링 기계(Deterministic Turing Machine, DTM)의 전이 함수 $\delta$ 는 다음과 같이 정의된다:

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

이 정의의 해석:

정의역(Domain): $(Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma$ . 수락 상태와 거부 상태를 제외한 상태와 테이프 기호의 순서쌍이다. 수락 상태와 거부 상태에서는 전이 함수가 정의되지 않으며, 기계가 이 상태에 도달하면 즉시 정지한다.
치역(Codomain): $Q \times \Gamma \times \{L, R\}$ . 다음 상태, 쓸 기호, 이동 방향의 순서 3-튜플이다.

$\delta(q, a) = (q', b, D)$ 의 해석:

현재 상태가 $q$ 이고 헤드가 기호 $a$ 를 읽을 때,
상태를 $q'$ 로 전이하고,
현재 셀의 기호를 $b$ 로 덮어쓰고,
헤드를 방향 $D$ 로 이동한다.

전이 함수의 전역성(Totality)

표준 정의에서 전이 함수는 전역 함수(Total Function)이다. 즉, 정의역의 모든 순서쌍 $(q, a) \in (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma$ 에 대해 $\delta(q, a)$ 가 정의된다. 이는 기계가 수락 또는 거부 상태에 도달하기 전까지는 항상 다음 동작이 결정됨을 보장한다.

일부 정의에서는 부분 함수(Partial Function) $\delta: Q \times \Gamma \rightharpoonup Q \times \Gamma \times \{L, R\}$ 를 허용한다. 이 경우 $\delta(q, a)$ 가 정의되지 않는 $(q, a)$ 쌍이 존재할 수 있으며, 기계가 이러한 상황에 도달하면 정지한다. 두 정의는 계산적으로 동치이다.

전이 함수의 표현 방식

전이 표(Transition Table)

전이 함수를 행이 상태, 열이 테이프 기호인 2차원 표로 나타낸 것을 전이 표(Transition Table)라 한다. 각 셀에 $(q', b, D)$ 가 기록된다.

예를 들어, 입력 문자열이 회문(Palindrome)인지 판별하는 단순한 튜링 기계의 전이 표 일부:

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

상태 전이 다이어그램(State Transition Diagram)

전이 함수를 방향 그래프(Directed Graph)로 시각화한 것이 상태 전이 다이어그램이다. 노드는 상태를, 방향 간선(Directed Edge)은 전이를 나타낸다. 각 간선에는 읽은 기호, 쓸 기호, 이동 방향이 레이블로 표기된다.

간선 $q \xrightarrow{a \rightarrow b, D} q'$ 는 $\delta(q, a) = (q', b, D)$ 를 나타낸다.

5-튜플 표기법

튜링의 원래 논문에서 사용된 표기법에 따르면, 각 전이는 5-튜플 $(q, a, q', b, D)$ 로 표기된다. 전이 함수 전체는 이러한 5-튜플의 유한 집합으로 명세된다:

$\delta = \{(q_i, a_j, q_k, b_l, D_m) \mid i, j, k, l, m \text{에 대한 조건}\}$

결정론적 튜링 기계에서 동일한 $(q_i, a_j)$ 쌍에 대해 하나의 5-튜플만이 존재해야 한다.

2. 비결정론적 튜링 기계의 전이 함수

비결정론적 튜링 기계(Nondeterministic Turing Machine, NTM)의 전이 함수는 결정론적 튜링 기계와 달리 다중값(Multi-valued)이다:

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

여기서 $\mathcal{P}(\cdot)$ 는 멱집합(Power Set)을 나타낸다. 동일한 $(q, a)$ 쌍에 대해 여러 개의 가능한 전이가 존재할 수 있으며, 기계는 이 중 하나를 “비결정론적으로” 선택한다.

비결정론적 튜링 기계의 계산은 분기하는 계산 트리(Computation Tree)로 표현된다. 비결정론적 튜링 기계가 문자열 $w$ 를 수락한다 함은, 계산 트리의 적어도 하나의 분기(Branch)가 수락 상태에 도달함을 의미한다.

비결정론적 튜링 기계와 결정론적 튜링 기계는 인식 가능한 언어의 클래스에서 동등하다. 즉, NTM이 인식하는 모든 언어는 DTM에 의해서도 인식 가능하다. 그러나 시간 복잡도에서는 지수적 차이가 발생할 수 있으며, 이 차이의 본질적 성격이 P 대 NP 문제( $\text{P} \stackrel{?}{=} \text{NP}$ )의 핵심이다.

전이 함수의 계산적 성질

결정론성(Determinism)

결정론적 전이 함수에서, 동일한 입력 $(q, a)$ 에 대해 출력이 유일하게 결정된다. 이는 기계의 동작이 완전히 예측 가능함을 보장한다. 동일한 입력에 대해 기계는 항상 동일한 계산 경로를 따른다.

국부성(Locality)

전이 함수의 입력은 현재 상태 $q$ 와 헤드가 위치한 셀의 기호 $a$ 뿐이다. 다른 셀의 기호, 헤드의 이전 위치, 과거의 상태 이력 등은 전이 함수에 직접 영향을 미치지 않는다. 과거의 정보는 오직 현재 상태 $q$ 와 테이프에 기록된 기호를 통해 간접적으로만 영향을 미친다. 이 국부성은 계산의 기계적 성격—각 단계의 동작이 국부적 정보만으로 결정됨—을 보장한다.

유한성(Finiteness)

전이 함수의 정의역은 유한 집합 $(Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma$ 이므로, 전이 함수는 유한한 수의 규칙으로 완전히 명세된다. 전이 규칙의 수는 최대 $\vert Q \vert \times \vert \Gamma \vert$ 이다. 이 유한성은 전이 함수가 유한한 표 또는 유한한 5-튜플 집합으로 기술 가능함을 보장하며, 이는 기계의 “프로그램“이 유한하다는 것을 의미한다.

전이 함수와 프로그램의 관계

전이 함수는 현대 컴퓨터에서의 프로그램(Program)에 대응한다. 프로그램이 명령어의 순서열로서 각 상황에서 컴퓨터가 수행할 동작을 규정하듯이, 전이 함수는 각 상태-기호 쌍에 대해 기계가 수행할 동작을 규정한다.

이 대응의 핵심적 차이점은, 전이 함수가 현대 프로그램에 비해 극도로 저수준(Low-Level)의 동작 명세라는 것이다. 현대 프로그래밍 언어의 고수준 구성체(반복문, 조건문, 함수 호출 등)는 전이 함수의 적절한 상태 설계로 모두 구현 가능하지만, 이러한 변환에는 상당한 상태 수의 증가가 수반된다.

범용 튜링 기계(Universal Turing Machine)에서 전이 함수 자체가 테이프에 부호화되어 입력으로 제공되는 것은 현대의 저장 프로그램 개념(Stored-Program Concept)—프로그램이 데이터와 동일한 메모리에 저장되는 것—의 이론적 원형이다.