[강동옥]

생각해보니 튜링머신이 익숙하지 않은분들이 있군요

숙제의 튜링 머신은 인풋으로

1. 테잎의 초기모습 (symbol들의 리스트)
2. initial state
3. 튜링머신이 작동하는 규칙(ruletable)
을 받습니다.

=========자연수 둘을 더하는 Turing machine=========

테입에 쓰여진 'one 심볼의 갯수를 자연수로 인코딩 하겠습니다.

예를들어 'one 'one 'one 'plus 'one one 이 테입에 쓰여있으면 3+2 를 하라는 의미입니다.

symbol 이 쓰여져있지 않은 테입에는 BLANK symbol 이 있어야합니다.


rule은 state와 symbol 을 받아서 전이되는 state, 테잎에 쓰는 symbol, 테입을 움직이는 방향을 내놓는 함수로 생각할 수 있습니다.

(읽기쓰기 헤드를 오른쪽으로 움직이려면 테입을 왼쪽으로 움직여야 합니다.)


==rule table==
초기 state를 s0 이라 하면

(s0, one) -> (s0, one , left)
(s0, plus) -> (s1, one , left)
(s1, one) -> (s1, one , left)
(s1, blank) -> (s2, blank, right)
(s2, one) -> (s3, blank, right)
(s3, one) -> (s3, one, right)
(s3, blank) -> (s4, blank, left)

라는 rule 을 만들 수 가 있고 final state 는 s4가 됩니다.


==튜링머신의 동작==

s0 one one one plus one one (첫번째 심볼에 헤드가 위치하며 state 는 s0 를 의미)
one s0 one one plus one one (두번째 심볼에 헤드가 위치하며 state 는 s0 를 의미)
one one s0 one plus one one
one one one s0 plus one one
one one one one s1 one one
one one one one one s1 one
one one one one one one s1 BLANK
one one one one one s2 one
one one one one s3 one
one one one s3 one one
one one s3 one one one
one s3 one one one one
s3 one one one one one
s3 BLANK one one one one one
s4 one one one one one

튜링머신의 동작이 끝나면 테잎에는 5가 쓰여진 것을 보실 수 있습니다.

위의 머신을 만들 때에, make-tm 함수의 인자로 들어가는 것은

(list 'one 'one 'one 'plus 'one 'one) 's0 ruletable
이 됩니다.

[강동옥]

========주어진 문자열 w 를 받았을 때 ww 를 출력하는 Turing machine========

문자열을 구성하는 문자는 a와 b로 이루어져있다고 가정하면

'a 'b 'a 'a 를 초기 인풋으로 주면 'a 'b 'a 'a 'a 'b 'a 'a 를 리턴해야 합니다.

==rule table=

(s0, a) -> (s1, a_1, left)
(s0, b) -> (s2, b_1, left)
(s1, a) -> (s1, a, left)
(s1, b) -> (s1, b, left)
(s1, a_2) -> (s1, a_2, left)
(s1, b_2) -> (s1, b_2, left)
(s1, BLANK) -> (s3, a_2, right)
(s2, a) -> (s2, a, left)
(s2, b) -> (s2, b, left)
(s2, a_2) -> (s2, a_2, left)
(s2, b_2) -> (s2, b_2, left)
(s2, BLANK) -> (s3, b_2, right)
(s3, a_2) -> (s3, a_2, right)
(s3, b_2) -> (s3, b_2, right)
(s3, a) -> (s_noend, a , right)
(s3, b) -> (s_noend, b , right)
(s3, a_1) -> (s_semifinal, a_1, left)
(s3, b_1) -> (s_semifinal, b_1, left)
(s_noend, a) -> (s_noend, a ,right)
(s_noend, b) -> (s_noend, b ,right)
(s_noend, a_1) -> (s0, a_1, left)
(s_noend, b_1) -> (s0, b_1, left)
(s_semifinal, a_2) -> (s_semifinal, a_2, left)
(s_semifinal, b_2) -> (s_semifinal, b_2, left)
(s_semifinal, BLANK) -> (s_ff, BLANK, right)
(s_ff, a_2) -> (s_ff, a ,right)
(s_ff, a_1) -> (s_ff, a ,right)
(s_ff, b_2) -> (s_ff, b ,right)
(s_ff, b_1) -> (s_ff, b ,right)
(s_ff, BLANK) -> (s_final, BLANK, left)

initial state 는 s0 이고 final state 는 s_final이 됩니다.


==a b a 라는 인풋이 있을 때의 동작==

s0 a b a
a_1 s1 b a
a_1 b s1 a
a_1 b a s1 BLANK
a_1 b s3 a a_2
a_1 s_noend b a x
s_noend a_1 b a a_2
a_1 s0 b a a_2
a_1 b_1 s2 a a_2
a_1 b_1 a s2 a_2
a_1 b_1 a a_2 s2 BLANK
a_1 b_1 a s3 a_2 b_2
a_1 b_1 s3 a a_2 b_2
a_1 s_noend b_1 a a_2 b_2
a_1 b_1 s0 a a_2 b_2
a_1 b_1 a_1 s1 a_2 b_2
a_1 b_1 a_1 a_2 s1 b_2
a_1 b_1 a_1 a_2 b_2 s1 BLANK
a_1 b_1 a_1 a_2 s3 b_2 a_2
a_1 b_1 a_1 s3 a_2 b_2 a_2
a_1 b_1 s3 a_1 a_2 b_2 a_2
a_1 b_1 a_1 s_semifinal a_2 b_2 a_2
...
a_1 b_1 a_1 a_2 b_2 a_2 s_semifinal BLANK
a_1 b_1 a_1 a_2 b_2 s_ff a_2
a_1 b_1 a_1 a_2 s_ff b_2 a
a_1 b_1 a_1 s_ff a_2 b a
a_1 b_1 s_ff a_1 a b a
a_1 s_ff b_1 a a b a
...
s_ff BLANK a b a a b a
s_final a b a a b a


위의 머신을 만들 때에, make-tm 함수의 인자는

(list 'a 'b 'a) 's0 (위에서 만든 ruletable)
이 되겠습니다.

[박재성]

state가 string으로 주어지므로 "s0"같은 방식으로 되어야 하지 않나요 ?

[강동옥]

네 맞습니다. 형식 따지지 않고 그냥 적은 것입니다.

[최민아]

예년에는 state을 symbol로 구현하게 하였으나, 올해에는 string이라고 명시되어 있으므로 state을 string으로 하시면 됩니다. 혼란을 드려 죄송합니다.