상위 문서: 계산 이론 개론
개요
튜링 머신(Turing Machine)은 계산의 본질을 단순한 모델로 표현한 이론적 컴퓨터 모델이다. 튜링 머신은 모든 계산 가능한 것을 정의하는 최초의 이론적 모델로서 현대 컴퓨터의 이론적 토대를 마련했다. 또한 , 튜링 머신을 통해 계산 가능성의 한계를 증명하고, 어떤 언어의 능력을 평가하는 '튜링 완전성' 개념의 기반이 되었다.
Basic Concepts of Turing Machines
튜링 머신의 핵심적인 구성요소는 Control unit, Tape, Read/Write Head이다:
- Control unit: Control unit은 유한한 상태 집합 Q 중 하나의 상태에 머물며 작동한다.
- 현재 상태를 기억하고 다음 동작을 결정하는 역할을 한다.
- Tape: 무한히 긴 1차원 테이프이며, 칸에는 하나의 기호(symbol)를 쓸 수 있다.
- 이때 사용할 수 있는 기호들의 집합을 테이프 알파벳[math]\displaystyle{ (\Gamma) }[/math]이라고 한다.
- Read/Write Head: 한 번에 한 칸씩 왼쪽(L) 또는 오른쪽(R)으로 이동하면서, 현재 칸의 기호를 읽거나 바꾼다.
튜링 머신은 위의 구성 요소를 바탕으로 유한한 개수의 명령(전이 함수, transition function)을 따라서 작동한다. 즉, 명령은 (현재 상태, 읽은 기호) → (새 상태, 쓸 기호, 이동 방향)과 같이 정의된다고 할 수 있다.
Mathematical Formalization
튜링 머신은 아래와 같은 7-튜플([math]\displaystyle{ Q, \Sigma, , \Gamma, \delta, q_0, q_{accept}, q_{reject} }[/math])을 통해서 정의된다:
- [math]\displaystyle{ Q }[/math]: 상태들의 유한 집합(states)
- [math]\displaystyle{ \Sigma }[/math]: 입력 알파벳 (input alphabet)[1]
- [math]\displaystyle{ \Gamma }[/math]: 테이프 알파벳 (tape alphabet), [math]\displaystyle{ \Sigma \in \Gamma, \textvisiblespace \in \Gamma }[/math][2]
- [math]\displaystyle{ \delta }[/math]: 전이 함수(transition function)이며, 아래와 같은 형식이다:
[math]\displaystyle{ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\} }[/math] - [math]\displaystyle{ q_0 }[/math]: 시작 상태(start state)
- [math]\displaystyle{ q_{accept} }[/math]: 받아들이는 상태(accept state)
- [math]\displaystyle{ q_{reject} }[/math]: 거부 상태(reject state)[3]
Configurations of Turing Machines
튜링 머신에서의 구성(Configuration)이란 튜링 머신의 현재 상태 전체를 나타내는 한 단위 상태이다. 이는 아래와 같이 정의된다:
[math]\displaystyle{ (u,q,v) }[/math]
이때 [math]\displaystyle{ q \in Q }[/math]는 현재 튜링 머신이 위치한 상태를 나타낸다. 또한 [math]\displaystyle{ u \in \Gamma* }[/math]는 헤드의 왼쪽에 있는 테이프 내용을, [math]\displaystyle{ v\in \Gamma^+ }[/math]는 헤드의 오른쪽에 있는 테이프 내용을 의미한다. 예를 들어 [math]\displaystyle{ (u,q,v)= (101, q_3, 0\textvisiblespace\textvisiblespace\textvisiblespace) }[/math]와 같이 구성이 주어지면, 현재 상태는 [math]\displaystyle{ q_3 }[/math]이며, 테이프 왼쪽에는 "101"이, 오른쪽에는 "0"과 공백이 있다는 것을 의미한다. 이때 공백은 테이프 위에서 아무것도 적혀 있지 않은 칸을 의미하며, 입력 이외의 칸을 나타내기 위해 사용하는 심볼이다. 이때 중요한 것은 오른쪽 끝의 공백은 몇 개가 있든 동일한 구성으로 간주한다. 이는 아래와 같이 나타낼 수 있다:
[math]\displaystyle{ (u,q,v\textvisiblespace^n)=(u,q,v\textvisiblespace^m) for\,\, n,m\ge 0 }[/math]
이는 튜링 기계가 “무한히 많은 빈 칸”을 상정하므로, 불필요한 공백 개수는 의미가 없기 때문이다. [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]