[오토마타] 18. 범용 튜링머신(Universal TM)과 알고리즘

우리는 지금까지 특정 기능만 수행하는 튜링머신을 다뤘다. 이것을 고정 튜링머신(Hardwired TM)이라고 부른다. 어떤 1번 TM이 w에 대해서 수행하는 일도, 2번 TM이 y에 대해 수행하는 일도, 3번 TM이 z에 대해 수행하는 일도 다 해내는 범용 튜링머신(Universal TM)에 대해 알아본다.

 

범용 튜링머신(Universal TM)

만약 어떤 튜링머신 M에 대한 정보와 M이 원래 입력으로 받는 문자열 w를 함께 입력으로 받아서 동작하는 프로그래머 TM(programmable TM)이 있다면, 그것이 곧 범용 튜링머신(UTM)이 될 것이다. UTM은 M이 하는일을 흉내내서 w에 대한 연산을 처리한다. 이 UTM의 동작 방식은 쿠르트 괴델(Kurt Friedrich Gödel)에 의해 제시되었다. 

Figure 1. Universal TM, Sipser 2012

1. 입력으로는 M과 w를 받는다. 어떻게 받는지는 잠시 뒤에 논의한다.
2. 원래 M이 w를 연산할 때 테이프의 상태를 흉내내는 테잎이 있다.
3. M이 w를 연산할때 의 상태의 전이를 흉내낼 수 있는 테잎이 있다.

알고리즘과 튜링 머신

알고리즘은 어떤 지시사항들의 나열을 의미한다. 알고리즘에 대한 수학적인 엄밀한 정의는 앨런 튜링(Alan Turing)과 알론조 처치(Alonzo Church)로부터 제시되었다. 둘은 각각 알고리즘의 정의에 튜링머신과 λ-계산법(λ-calculus)를 사용했는데, 이 둘은 실질적으로 동일했다. 그래서 이 알고리즘의 엄격한 정의에 관한 내용을 처치-튜링 명제(Church-Turing Thesis)라고 부른다.

튜링머신을 일상적인 수준으로 데려올 수 있다. 어떤 언어 $D=\{p|\text{p는 변수 x에 대한 정수 근을 갖는 다항식}\}$를 인식하는 TM은 존재할까? 예를 들어, $x^3+2x^2-1=0$을 입력으로 받아, 정수근이 있는지 없는지를 판단하는 TM이 존재할까? $x=0,1,-1,2,-2,3,-3,4,...$ 순으로 값을 넣어보다 보면, 언젠가 정수근을 찾을 수 있을테니 인식가능한 TM은 존재한다. 정수근이 없다면 정지하지 않고 영원히 TM은 연산을 수행할 것이다. 즉, 인식 가능한(recognizable) TM은 있지만, 결정 가능한(decidable) TM은 없다. TM이 결정 가능하다는 것은 모든 연산이 정지된다는 뜻이라고 앞선 글에서 다뤘다. 한편, $D'=\{p|\text{p는 변수 x에 대한 -5에서 5사이의 정수 근을 갖는 다항식}\}$으로 구간이 주어진다면, $D'$에 대한 결정기 TM은 존재함을 유추할 수 있다.

이런식으로, 알고리즘은 TM에 대응된다. 알고리즘은 3가지 수준으로 나눠서 표현할 수 있다.
1. 가장 낮은 수준: 우리가 지금까지 해왔던 것처럼, TM의 전이함수와 상태 등 모든 엄격한 정의(formal definition)으로 표현하기
2. 중간 수준: TM이 어떻게 동작하는지를 일상 언어로 표현하기
3. 가장 높은 수준: TM의 테이프나 헤드는 전혀 언급하지 않고, 그냥 일상 언어나 수도코드(pseudo-code)로 알고리즘을 표현하기

입력을 문자열로 인코딩하기

높은 수준에서는 입력을 문자열이 아닌 어떤 형태로 받아도 상관없다. 하지만, TM은 입력을 문자열로 밖에 받을수 없다. 앞서 UTM에 대해 논의할때도 튜링머신을 입력으로 어떻게 받을지에 대한 논의를 생략했었다. 입력을 문자열로 변환할 수 있으면, UTM의 입력에 대한 문제도, 알고리즘의 고수준 표현과 저수준 표현 사이의 간극도 해결된다. 이 절에서는 입력을 문자열로 변환하는 방법에 대해 다룬다.

만약 입력으로 어떤 객체 $O_1$를 입력으로 한다면, 인코딩된 입력은 $<O_1>$으로 표기하기로 한다. 여러개라면 $<O_1, O_2>$로 표기한다.

예를 들어, $A=\{<G>| G는 연결 그래프\}$라는 언어가 있다고 하자. <G>는 Figure 2처럼 인코딩된다. 앞 부분 $(1,2,3,4)$은 노드의 나열이다. 뒷부분 $((1,2),(2,3),(3,1),(1,4))$은 엣지(edge)의 나열이다. 이러면 그래프 정보인 G를 문자열 <G>로 변환하였기 때문에, 인식하는 TM M을 정의하는데에 문제가 없다.

Figure 2. Encoding, Hopcroft 3rd edition

M = "입력 ⟨G⟩에 대해, 그래프 G의 인코딩:
1. G의 첫 번째 노드를 선택하고 표시한다.
2. 새로운 노드가 표시되지 않을 때까지 다음 단계를 반복한다:
3. G의 각 노드에 대해, 이미 표시된 노드에 가장자리로 연결되어 있으면 표시한다.
4. G의 모든 노드를 스캔하여 모두 표시되었는지 확인한다. 모두 표시되었으면 수락하고, 그렇지 않으면 거부한다."

 

튜링머신의 정의를 문자열로 변환하는 과정은 다음과 같다. 모든 $Q, \Gamma$에 순서를 할당한다. 대신, 1,2,3번 상태는 초기 상태, 수용상태, 거부 상태로 고정한다. 하나의 전이 $\delta(q_h, a_i) = (q_j,a_k, L)$는 $(h,i,j,k,L)$ 5개의 정수로 설명가능하다. L은 1, R은 0에 대응된다. 그러면 $(h,i,j,k,L)$을 $0^h10^i10^j10^k1L$로 변환한다. 그리고 가능한 모든 전이를 $11$을 구분자 삼아 나열하면 변환이 끝난다.

그러면, UTM은 아래의 언어를 인식한다.
$A = \{<M,w>| \text{ M은 튜링머신이고, M이 w를 수용한다.}\}$

UTM U에 대한 고수준의 설명은 다음과 같다(AI로 생성함). 

U = "입력 ⟨M, w⟩에 대해, 여기서 M은 튜링 머신이고 w는 입력 문자열이다:

1. 입력 ⟨M, w⟩가 올바른 형식인지 검증한다. 즉, M이 유효한 튜링 머신의 인코딩이고 w가 유효한 문자열 인코딩인지 확인한다.
2. M의 전이 함수를 테이프에 저장한다.
3. M의 초기 구성을 시뮬레이션한다:
   - M의 시작 상태를 현재 상태로 설정한다.
   - w를 테이프에 기록하고 헤드를 w의 첫 번째 심볼 위에 위치시킨다.
4. 다음을 반복한다:
   - 현재 상태와 헤드 아래의 심볼을 확인한다.
   - M의 전이 함수를 참조하여 다음 전이를 결정한다.
   - 전이에 따라:
     - 상태를 변경한다.
     - 테이프 심볼을 쓴다.
     - 헤드를 이동시킨다.
     - M이 수락 상태에 도달하면 수락한다.
     - M이 거부 상태에 도달하면 거부한다.
     - (M이 무한 루프에 빠지면 U도 무한 루프에 빠진다)"