Turing Machines

상위 문서: 계산 이론 개론

개요

튜링 머신(Turing Machine)은 계산의 본질을 단순한 모델로 표현한 이론적 컴퓨터 모델이다. 튜링 머신은 모든 계산 가능한 것을 정의하는 최초의 이론적 모델로서 현대 컴퓨터의 이론적 토대를 마련했다. 또한 , 튜링 머신을 통해 계산 가능성의 한계를 증명하고, 어떤 언어의 능력을 평가하는 '튜링 완전성' 개념의 기반이 되었다.

Basic Concepts of Turing Machines

튜링 머신의 핵심적인 구성요소는 Control unit, Tape, Read/Write Head이다:

1. Control unit: Control unit은 유한한 상태 집합 Q 중 하나의 상태에 머물며 작동한다.
   • 현재 상태를 기억하고 다음 동작을 결정하는 역할을 한다.
2. Tape: 무한히 긴 1차원 테이프이며, 칸에는 하나의 기호(symbol)를 쓸 수 있다.
   • 이때 사용할 수 있는 기호들의 집합을 테이프 알파벳$(\mathrm{\Gamma })$이라고 한다.
3. Read/Write Head: 한 번에 한 칸씩 왼쪽(L) 또는 오른쪽(R)으로 이동하면서, 현재 칸의 기호를 읽거나 바꾼다.

튜링 머신은 위의 구성 요소를 바탕으로 유한한 개수의 명령(전이 함수, transition function)을 따라서 작동한다.

Mathematical Formalization

튜링 머신은 아래와 같은 7-튜플($Q,\mathrm{\Sigma },,\mathrm{\Gamma },\delta ,q_0,q_{accept},q_{reject}$)을 통해서 정의된다:

1. $Q$: 상태들의 유한 집합(states)
2. $\mathrm{\Sigma }$: 입력 알파벳 (input alphabet)
3. $\mathrm{\Gamma }$: 테이프 알파벳 (tape alphabet), $\mathrm{\Sigma }\in \mathrm{\Gamma },␣\in \mathrm{\Gamma }$
4. $\delta$: 전이 함수(transition function)이며, 아래와 같은 형식이다:
   $\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$
5. $q_0$: 시작 상태(start state)
6. $q_{accept}$: 받아들이는 상태(accept state)
7. $q_{reject}$: 거부 상태(reject state)

튜링 머신의 전이 함수를 풀어 설명하면, 아래와 같은 형태이다:

“만약 현재 상태가 q이고, 테이프에서 기호 a를 읽었다면,

이를 기호 b로 바꾸고, 머리를 L 또는 R로 한 칸 이동한 뒤, 상태를 r로 바꿔라.” 즉, 명령은 (q, a) → (r, b, L/R)과 같이 정의된다고 할 수 있다.

튜링 기계의 형식적 정의는 사람마다 약간씩 다를 수 있다. 예를 들어, reject 상태를 따로 두지 않고 accept 상태 만을 정의하고 나머지는 자동으로 reject로 간주하기도 한다. 또한 테이프의 왼쪽 끝 표시(left-end marker)를 따로 두어 기계가 더 이상 왼쪽으로 이동하지 않도록 제한하기도 하기도 한다. 해당 위키에서 참조하는 Michael Sipser의 『Introduction to the Theory of Computation, Third Edition』에서도 아래와 같이 추가적인 정의를 추가한다:

"어떤 구성 $(u,q,v)$에서 $q\in \{q_{accept},q_{reject}\}$일 때, 반드시 하나의 후속 구성(successor configuration)을 가진다."

이는 모호하지 않은(결정적) 동작을 보장하여 결정적 튜링 머신(Deterministic Turing Machine)을 전제로 하기 위한 것이다.

Configurations of Turing Machines

튜링 머신에서의 구성(Configuration)이란 튜링 머신의 현재 상태 전체를 나타내는 한 단위 상태이다. 이는 아래와 같이 정의된다:

$(u,q,v)$

이때 $q\in Q$는 현재 튜링 머신이 위치한 상태를 나타낸다. 또한 $u\in \mathrm{\Gamma }*$는 헤드의 왼쪽에 있는 테이프 내용을, $v\in {\mathrm{\Gamma }}^{+}$는 헤드의 오른쪽에 있는 테이프 내용을 의미한다. 예를 들어 $(u,q,v)=(101,q_3,0␣␣␣)$와 같이 구성이 주어지면, 현재 상태는 $q_3$이며, 테이프 왼쪽에는 "101"이, 오른쪽에는 "0"과 공백이 있다는 것을 의미한다. 이때 공백은 테이프 위에서 아무것도 적혀 있지 않은 칸을 의미하며, 입력 이외의 칸을 나타내기 위해 사용하는 심볼이다. 이때 중요한 것은 오른쪽 끝의 공백은 몇 개가 있든 동일한 구성으로 간주한다. 이는 아래와 같이 나타낼 수 있다:

$(u,q,v{␣}^n)=(u,q,v{␣}^m)forn,m\ge 0$

이는 튜링 기계가 “무한히 많은 빈 칸”을 상정하므로, 불필요한 공백 개수는 의미가 없기 때문이다.

아래 표는 튜링 머신이 계산을 시작하거나 끝내는 특수 상태들을 열거한 것이다:

구성 유형	형태
시작 구성 (Start configuration)	$q_{0}w$
Accept 구성 (Accepting)	$u{q}_{accept}v$
Reject 구성 (Rejecting)	$u{q}_{reject}v$

이때 어떤 튜링 머신 M이 $w$를 accept한다고 하는 것은 아래 조건들을 만족하는 구성열(sequence)이 존재할 때이다:

1. $C_1=q_{0}w$
2. 중간의 $C_i$들은 accept/reject가 아닌 일반 상태
3. 각 $C_i$는 $C_{i+1}$을 yield함
4. 마지막 $C_k$는 accepting configuration

즉, $C_1\Rightarrow C_2\Rightarrow \cdots \Rightarrow C_k$이고, $C_k$가 accept 상태에 도달하면 문자열 $w$는 accept된다.

The Yields Relation

튜링 머신이 한 단계에서 다음 단계로 이동하는 규칙은 $\delta$와, 해당 튜링머신의 구성을 통해 정의된다. 예를 들어,

Configuration $C_1$ yields $C2$

는 주어진 튜링 머신의 상태가 단 한번의 동작으로 $C_1$에서 $C_2$로 바뀐다는 것을 의미한다. 이때, 이 yield 관계(relation)는 전이함수 $\delta$에 의해서 결정된다. 이때 yield 관계는 아래와 같이 구분된다:

1. 왼쪽으로 이동 (Move Left)
   • $q_{i}bv$ yields $q_{j}cv,if\delta (q_i,b)=(q_j,c,L)$: 단순히 머리 위치를 그대로 두고, 공백을 유지한다.
   • $ua{q}_{i}bv$ yields $u{q}_{j}acv,if\delta (q_i,b)=(q_j,c,L)$: $b$를 $c$로 바꾸고 왼쪽으로 이동하여 왼쪽 기호 $a$ 위로 헤드를 옮긴다.
2. 오른쪽으로 이동 (Move Right)
   • $ua{q}_{i}b$ yields $uac{q}_j␣,if\delta (q_i,b)=(q_j,c,R)$: 공백(blank)을 새로 하나 추가해야 한다.
   • $ua{q}_{i}bv$ yields $uac{q}_{j}v,if\delta (q_i,b)=(q_j,c,R)$: $b$를 $c$로 바꾸고, 한 칸 오른쪽으로 이동한다.

Deciders

어떤 튜링 머신 $M$이 decider라고 불리기 위해서는 입력 문자열에서 출발했을 때, 영원히 멈추지 않고 돌기만 하는 경우가 없어야 한다. 즉, 어떤 입력 $w$에 대해서도 반드시 Accepting 혹은 Rejecting 구성에 도달해야 한다. 이때 모든 튜링 기계가 Decider인 것은 아니며, 어떤 기계는 특정 입력에서 무한 루프에 빠질 수도 있다. 이러한 경우를 recognizer라고 부른다. 이에 따라 튜링 기계가 인식(recognize)하거나 결정(decide)할 수 있는지 여부에 따라 언어(Language)의 종류를 구분할 수 있다. 아래는 이를 정리한 표이다:

구분	정의	특징
Turing-recognizable	어떤 튜링 기계 M이 있어서, L=L(M) 일 때	입력이 언어에 속하면 Accept, 속하지 않으면 멈추지 않고 무한 루프 가능
Turing-decidable	어떤 Decider M이 있어서, L=L(M) 일 때	모든 입력에 대해 반드시 멈추며, Accept 또는 Reject 중 하나 출력

이때 모든 Decidable 언어는 Recognizable 언어이지만, 그 반대(Recognizable → Decidable)는 성립하지 않는다. 이때 중요한 것은, "모든 정규 언어가 튜링 기계로 결정 가능하다(decidable)"하다는 것이다. 언어를 입력받을 때, 해당 입력이 끝나는 것은 공백(blank symbol)을 통해 판단한다. 즉, 입력을 다 읽고 처음 만나는 blank가 입력의 끝이다.

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$