[오토마타] 17. 변형된 튜링머신(Variants of TM)

이번 글에서는 튜링머신에 변형을 가해서, 새로운 튜링머신을 만든다. 새로운 튜링머신들은 기존 튜링머신보다 좋아보이지만, 우리의 직관과 추론에 도움을 줄 뿐, 기존 튜링머신과 같은 언어를 인식한다. 달리 말하면, 동등하다.

헤드를 움직이지 않아도 되는 튜링머신

앞선 튜링머신은 매 전이마다 헤드를 왼쪽이나 오른쪽으로 움직여야했다. 하지만, 변형된 튜링머신은 헤드를 가만히 있어도 된다. 원래 튜링머신의 전이 함수는 $Q\times\Gamma \to Q\times\Gamma\times\{L, R\}$ 이었다면, $Q\times\Gamma \to Q\times\Gamma\times\{L, R, S\}$의 함수다.

왜 $S$를 추가하고도 기존 튜링머신과 동등할까? $\delta(q, a) = (q',b,S)$를 기존 튜링머신의 정의로도 시뮬레이션 가능하기 때문이다. 새로운 상태 $q''$를 추가하야, $\delta(q,a) = (q'', b, L)$와 $\delta(q'',b) = (q', b, R)$을 수행한다. 헤드의 심볼은 업데이트 하면서, 헤드는 움직이지 않은 효과를 낸다.

 

다중 테잎 튜링머신(Multitape TM)

튜링머신은 테잎이 하나였지만, 여러 개의 테잎을 갖는 튜링머신도 생각할 수 있다. 원래 튜링머신의 전이 함수는 $Q\times\Gamma \to Q\times\Gamma\times\{L, R, S\}$ 이었다면, $Q\times\Gamma \to Q\times \Gamma^k \times\{L, R, S\}^k$의 함수다. 여전히 두 튜링머신이 인식하는 언어는 같다.

테잎이 하나인 튜링머신의 전이는 $\delta(q, a) = (q',a',L)$ 처럼 표현했다면, 테잎이 두개인 튜링머신은 $\delta(q, a, b) = (q',a',b',L,R)$ 처럼 표현할 수 있다. 두 개의 테잎이 있는 튜링머신을 시뮬레이션 하는 단일 테잎 튜링머신을 설계해보자. 아래의 특징을 갖는다.

• 새로운 심볼들을 갖는다. 구분자 $\#$과 모든 심볼에 대하여 $\bar{a}$ 처럼 마킹된 심볼이 추가된다.
• 멀티테잎 TM의 테잎 초깃값이 각각 $w$와 $z$라면, 새로운 TM은 $\#w\#z\#$을 초깃값으로 갖는다.
• 멀티테잎 TM에서 두개의 헤더가 가르키고 있는 심볼은 마킹으로 표현한다. $\#w\#z\#$에서 각 헤더가 가리키는 심볼은 원래 $a$였다면 $\bar{a}$로 바꿔둔다.
• 이제 $\delta(q, a, b) = (q',a',b',L,R)$은 다음과 같이 실행한다.
  - $\bar{a}$를 찾아서 $a'$로 업데이트하고, 헤더를 왼쪽으로 옮긴다. 이동한 헤더가 가리키고 있는 심볼을 다시 마킹한다. 이 과정은 첫번째 테잎의 $\delta(q, a)=(q',a',L)$전이를 시뮬레이션한 효과다.
  - $\#$가 나올때까지 헤더를 오른쪽으로 이동한다.
  - $\bar{b}$를 찾아서 $b'$로 업데이트하고, 헤더를 오른쪽으로 옮긴다. 이동한 헤더가 가리키고 있는 심볼을 다시 마킹한다. 이 과정은 두번째 테잎의 $\delta(q,b)=(q',b',R)$전이를 시뮬레이션한 효과다.
  - 혹시나 매 테잎의 시뮬레이션 과정에서 헤더를 옮겼는데 옮긴 자리에 $\#$가 있다면, $\bar{\sqcup}$를 추가한다. 매 테잎은 오른쪽으로 무한하고, 모두 $\sqcup$로 채워져 있는 것을 시뮬레이션 하는것이다. (테잎에 $\bar{\sqcup}$를 추가하는 과정은 생략했다.)
  
  

 

비결정적 튜링머신(Non-deterministic TM)

기존 튜링머신은 주어진 상태와 심볼에 따라 (다음 상태, 다음 심볼, 다음 헤더의 이동방향)이 결정적(deterministic)했다. 이제는 (다음 상태, 다음 심볼, 다음 헤더의 이동방향)이 없거나 여러개일 수 있다. $Q\times\Gamma \to Q\times\Gamma\times\{L, R, S\}$ 이었다면, $Q\times\Gamma \to 2^{Q\times\Gamma\times\{L, R, S\}}$의 함수다. 어떤 입력의 계산 이력 중에서 하나라도 수용되는 계산이 있으면 그 입력은 수용된다. 하나도 수용되지 않으면 거부된다.

비결정적 튜링머신(NTM)의 연산이력은 NFA처럼 트리 형태로 표현된다. 그리고 우리는 NTM을 시뮬레이션할 떄 BFS(너비 우선 탐색)로 트리를 순회할 것이다. DFS(깊이 우선 탐색)가 아닌 이유는, 정지(halt)하지 않는 연산을 무한히 수행하는 굴레에 빠질 수 있기 때문이다.

NTM을 시뮬레이션 하려면 Figure 1과 같은 튜링머신이 필요하다.
- 입력 테잎(input tape): 초깃값은 테잎의 입력과 같다. 시뮬레이션 중 절대 변경되지 않는다.
- 주소 테잎(address tape): 트리를 순회하는 순서를 저장한다. 예를 들어, 심볼에 "231"이 들어있다면 루트, 2번째, 3번째, 1번째 연산을 입력값으로부터 수행하라는 뜻이다. 수행은 시뮬레이션 테잎에서 이뤄진다.
- 시뮬레이션 테잎(simulation tape):  BFS로 순회하면서 새로운 노드를 시뮬레이션 할 때마다, 입력 테잎의 값을 이 테잎으로 옮겨온다. 그리고 현재 주소테잎(address tape)의 헤더가 가리키는 심볼의 흐름대로 연산을 수행한다. 하나라도 수용상태에 도달하면 해당 입력은 수용된다.

Figure 1. Sigser 2012