[오토마타] 16. 튜링머신(Turing Machine)

튜링머신은 DFA, PDA와는 다른 또 새로운 오토마타다. 

Figure 1. Turing machine, Sipser 2012

1. 읽기-쓰기 테이프(Read-write tape)를 갖는다. 테이프는 오른쪽으로 무한하다. 테이프의 초깃값은 입력 문자열로 채워져 있으며, 나머지는 blank(⊔)로 채워져있다.
2. 최초에 헤드(Head)는 가장 왼쪽 셀(cell)을 가리키고 있다.
3. 이제 오토마타는 매 전이마다 아래의 행동을 해야한다.
→ 헤드를 오른쪽 혹은 왼쪽으로 움직인다.
→ 심볼(symbol)의 값을 다른 심볼로 바꾸거나 그대로 둔다.
→ 상태를 옮긴다.

 

튜링머신(TM)의 엄격한 정의(Formal Definition)

$\text{TM is a 7-tuple}(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) \text{ while }\\\\
Q\text{: states}\\
\Sigma\text{: input alphabet}\\
\Gamma\text{: tape alphabet, while }\Sigma\cup\{\sqcup\}\subseteq \Gamma\\
\delta\text{: transition function}(Q\times\Gamma \to Q\times\Gamma\times\{Left, Right\})\\
q_0\text{: initial state}\\
q_\text{accept}\text{: accept state}\\
q_\text{reject}\text{: reject state}, q_\text{accept} \neq q_\text{reject}
$

위 전이함수의 정의를 풀어서 설명하면 아래와 같다.
입력: 현재 상태, 현재 심볼
출력: 다음 상태, 다음 심볼, 헤드 이동방향(좌, 우)
튜링머신은 반드시 결정적(deterministic)해야한다. 다르게 말하면, 모든 가능한 상태와 가능한 심볼의 조합에 대해서 다음 행선지를 안내하는 전이함수가 정확히 하나씩 존재해야한다. 없거나 여러개여서는 안된다.

예를 들어, "상태는 $q$에서 $q'$로 전이하고, 테잎에 써있던 심볼 $b$는 $c$로 고치고, 헤드는 오른쪽으로 이동한다" 를 아래와 같이 표기한다.

$u\,q\,bv\text{ yields } uc\,q'\,v$
또는
$\delta(q,b) = (q',c,R)$

 

눈여겨 볼 점은, DFA나 PDA에서는 수용 상태(accept state)만을 정의하고, 나머지 상태는 모두 거부(reject)했다. 그러나, 튜링머신은 $q_\text{accept}$와 $q_\text{reject}$를 명시적으로 요구한다. 수용도, 거부도 아닌 상태가 존재하는 것이다. 그것은, 여러 상태를 전이하며 정지(halt)하지 못하고 빙빙 루프(loop)에 빠지는 입력이 있기 때문이다. 

정확히 튜링머신 연산 결과, 수용 상태에서 종료되는 문자열 $w$들만을 튜링머신 $M$의 언어 $L(M)$이라고 한다. $M$은 $L(M)$을 인식(recognize)한다. $L(M)$이 아닌 문자열들은 거부되거나 루프에 빠진 경우다. 어떤 언어 A를 설명하는 튜링머신이 있으면, 언어 A는 재귀적으로 나열가능하다(recursively enumerable)고 한다.

튜링머신 $M$이 주어진 알파벳 $\Sigma^{*}$의 모든 문자열 $w$에 대해 정지한다면, $M$은 $L(M)$을 결정(decide)한다. 이런 튜링머신이 있는 언어 A를, 재귀적(recursive)이라고 한다.

 

튜링머신의 예시

언어 $A=\{w\#w: w\in\{0,1\}^*\}$를 인식하는 튜링머신

$\#$을 기준으로 앞 뒤 내용이 같은 문자열을 인식하는 튜링머신은 대강 이렇게 동작한다.
1. 헤드가 첫 심볼을 읽고, $x$로 변경 후 헤드를 오른쪽으로 이동, 심볼이 0인지 1인지에 따라 서로 다른 상태로 전이해서 첫 심볼을 기억
2. 심볼이 $\#$이 될때까지 아무것도 하지 않고 헤드를 계속 오른쪽으로 이동
3. 심볼이 $x$가 아닐때까지 아무것도 하지 않고 헤드를 계속 오른쪽으로 이동
3. 현재 심볼이 (1)에서 기억했던 심볼과 같으면 $x$로 심볼 변경 후, 헤드를 가장 왼쪽의 $x$가 아닌 심볼로 이동시킴. (1)에서 기억했던 심볼과 다르다면 즉시 거부
4. $\#$ 왼쪽에 모든 심볼이 $x$가 되면 수용

Figure 2. # 앞뒤가 똑같은 문자열을 인식하는 튜링머신, Sipser 2012