[오토마타] Turing Machine as Accepter & Transducer

튜링머신의 용도는 크게 2가지로 나뉜다.

어떤 Language의 Accept여부를 판단하는 Accepter

어떠한 Input을 받아서 원하는 Output을 반환하는 Tansducer

 

Accepter

튜링 머신은 특정한 Language를 Aceept할 수 있다. 예를 들어서 아래 언어를 승인하는 튜링 기계를 만들어 보자

L = { anbn : n ≥1 } ∑ = { a , b }

 

이 언어를 승인 하려면 튜링 기계에서는 a의 연속된 문자열과 b의 연속된 문자열이 이어져 있고, a와 b의 개수가 같음이 판단되었을 때 final state로 이동 되게 하면 된다.

 

그렇게 하려면 a와 b를 다른 임의의 문자열로 하나씩 비교하면서 갯수를 판별한다. 예를 들어 a를 x로 b를 y로 한개씩 바꾸어 나가다 보면 모든 a가 x로 바뀌어 졌는데 b가 남아 있거나 그 반대의 경우가 생길 수 있다. 그건 정의된 언어에 위배되는 것이므로 accept하지 않고, 모든 a가 x로, 모든 b가 y로 변경 되었을때 final state로 보내 주변된다. 이때 주의 할 점은 변경된 테이프와 헤드의 위치를 원상태로 돌려 주어야 한다는 것이다. 전이 함수를 하나씩 글로 써 보자.

 

q1은 오른쪽으로 이동하며 a가 나오면 a를 x로 변경하고 바로 q2로 전이된다.
q2는 오른쪽으로 이동하며 a는 무시하고 b가 나오면 y로 변경하고 q3로 전이된다.

q3는 왼쪽으로 이동하며 x가 나오면 q1으로 전이된다.

 

이렇게 해 두면 왼쪽에 있는 a를 차례로 x로 바꾸고 오른쪽의 b를 차례로 y로 바꾸는 과정이 완료된다. 여기서 갯수가 일치 하는지 판별 하려면 a가 더이상 없을때 b도 없는지 체크 해야한다. 다시 q1를 확장한다.

 

q1은 y를 만나면 q2로 전이된다.

q2는 오른쪽으로 이동하며 blank를 만나면 확인완료! 복구를 위해 q4로 전이된다.

q4는 왼쪽으로 이동하며 y를 b로, x를 a로 바꾸어 준다. blank를 만나면 qf로 전이된다.

 

1aaabbb

x2aabbb

xa2abbb

xaa2bbb

xa3aybb

x3aaybb

3xaaybb

x1aaybb

xx2aybb

xxa2ybb

xxay2bb

xxa3yyb

xx3ayyb

x3xayyb

xx1ayyb

xxx2yyb

xxxy2yb

xxxyy2b

xxxy3yy

xxx3yyy

xx3xyyy

xxx1yyy

xxxy2yy

xxxyy2y

xxxyyy2

xxxyy4y

xxxy4yb

xxx4ybb

xx4xbbb

x4xabbb

4xaabbb

4□aaabbb

faaabbb

 

 

Transducer

도메인 D에 속하는 모든 w에 대하여, q₀w├^*_M q_ff(w), q_f∈F 인 Turing Machin M이 존재하면 그 함수 f는 Computable하다 라고 표현한다. 즉, 함수 f가 있을때 w가 여러번의 전이를 거쳐 f(w)가 되면서 accept되는 튜링 머신을 만들 수 있다면 그 함수를 Computable한 함수라고 말 하는 것이다. 더 쉽게 말하면 튜링 머신으로 만들 수 있는 함수는 Computable한 함수다.

 

모든 일반적인 수학함수(사칙 연산, 나머지 계산, 거듭제곱 등)은 Computable하다.

 

x+y(add 함수)를 수행하는 튜링머신을 만들어 보자.

 

1로만 이루어져 있는 문자열 w 사용한다. w(x)는 1이 w개 있는 문자열이다. ( w(x)∈{1}⁺, |w(x)| = x )

함수는 다음과 같은 Input과 Output을 가진다.

 

q₀w(x)0w(y)├^*_M q_fw(x+y)0

 

위 식을 풀어 보면, 2+3은 q₀110111으로 Input되고, q_f111110으로 output 된다는 것이다. 0은 일종의 special symbol로, input에선 더하기를 뜻하고, output에서는 식의 끝을 의미한다.

방법은 쉽다. 중간에 있는 0을 1로 바꾸고, 마지막에 있는 1을 0으로 바꾸면 된다.

 

실제로 2 + 3 을 수행 하면서 state를 하나씩 만들어 보자.

 

Head		▼
State
Tape		1	1	0	1	1	1
변하는 값

 

일단 중간에 있는 0을 1로 만드는데 필요한 state를 만들고 q_0to1이라고 명명한다.

헤드는 테이프의 젤 앞에 있으므로 Right 방향으로 진행해야 한다. 진행하면서 1을 만나면 그대로 두고 계속 이동,

 

δ( q_0to1 , 1) = ( q_0to1 , 1, R)

 

Head		→	→	▼
State		q0to1	q0to1	q0to1
Tape		1	1	0	1	1	1
변하는 값				1

 

0을 만나면 1로 바꾼다. 이제 남는건 1밖에 없으므로 는 쓸데가 없다. 이제 다른 스테이트로 전환한다.

 

δ( q_0to1 , 1) = ( 다른 State , 1, R)

 

다른 state는 어떤게 될까? 이제 해야 할 일은 마지막에 있는 1을 0으로 바꾸는 것이다. 일단 마지막으로 이동하는 State이 필요하니 q_toend 라고 명명한다. 그럼

 

δ( q_0to1 , 1) = ( q_toend , 1, R)

 

Head		→	→	→	▼
State		q0to1	q0to1	q0to1	qtoend
Tape		1	1	1	1	1	1
변하는 값

 

이렇게 될것이다. q_toend 에 관한 전이함수를 만들어 보자. 지금 head가 오른쪽으로 이동하다 중간에 멈춰있는 상태이다. blank가 나올때 까지 계속 오른쪽으로 이동하면 된다.

 

δ( q_toend , 1) = ( q_toend , 1, R) 

 

Head					→	→	→	▼
State					qtoend	qtoend	qtoend	qtoend
Tape		1	1	1	1	1	1
변하는 값

 

그리고 blank를 만나면 그 앞에 있는 1을 0으로 바꾸어 줘야 한다. 그러기 위해서 blank는 그대로 두고 Left로 한칸 이동하여 1의 위치에서 1을 0으로 바꾸는 state로 바꾼다. 이 state를 q_1to0이라고 한다.

 

δ( q_toend , □) = ( q_1to0 , □ , L)

 

Head							▼	←
State							q1to0	qtoend
Tape		1	1	1	1	1	1
변하는 값

 

q_1to0은 말그대로 1을 0으로 바꾼다. 이렇게 되면 원하는 결과가 완성되었다. 그럼 head를 다시 원위치로 돌려 놓아야 한다. 이를 하기 위한 state를 q_tobegin라고 한다.

 

δ( q_1to0 , 1) = ( q_tobegin , 0 , L)

 

Head						▼	←	←
State						qtobegin	q1to0
Tape		1	1	1	1	1	1
변하는 값							0

 

은 가장 오른쪽에 있는 1에 head를 위치 시켜야 한다. 1을 만나면 1을 그대로 두고 계속 왼쪽으로 이동한다.

 

δ( q_tobegin , 1) = ( q_tobegin , 1 , L)

 

Head	▼	←	←	←	←	←
State	qtobegin
Tape		1	1	1	1	1	0
변하는 값

 

blank를 만나면 다시 오른쪽으로 한칸 이동한다. 그럼 그것이 제일 첫부분이다. 원하는 결과를 도출하고 head를 원위치에 돌려 놓았으므로 이제 final state로 가면 완성이다.

 

δ( q_tobegin , □) = ( q_final , □ , R)

 

Head	→	▼
State	qtobegin	qfinal
Tape		1	1	1	1	1	0
변하는 값

 

 

결국 M = ({q_0to1, q_toend, q_1to0, q_tobegin, q_{final}, {1,0}, {1,0,□}, δ,} q_{0to1, □, {}q_final})

δ( q_0to1 , 1) = ( q_0to1 , 1, R)

δ( q_0to1 , 1) = ( q_toend , 1, R)

δ( q_toend , 1) = ( q_toend , 1, R)

δ( q_toend , □) = ( q_1to0 , □ , L)

δ( q_1to0 , 1) = ( q_tobegin , 0 , L)

δ( q_tobegin , 1) = ( q_tobegin , 1 , L)

δ( q_tobegin , □) = ( q_final , □ , R)

 

이러면 완성!