[이영석]

Turing machine 의 예

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

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



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

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

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

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


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

있습니다.

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


초기 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) (list 's4) 's0 ruletable
이 됩니다.

[이영석]

숙제 문서에는 나와있지 않지만 turing 머신에는 blank symbol 이 있어야합니다. (erase 를 한 결과, 또는 테입의 끝에 비어있는 tape 을 나타냅니다.)

blank symbol 은 'BLANK 로 정하겠습니다.

테입을 만들 때나 erase 를 할 때에 꼭!!! 위의 symbol로 작성해주세요

[이영석]

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

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

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

rule은 다음과 같이 정의 됩니다.

(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) (list 's_final) 's0 (위에서 만든 ruletable)
이 되겠습니다.

[박유군]

예제의 ruletable 에서 'left 는 tape를 왼쪽으로

움직이라는 의미로 사용된 거 같은데

저희가 구현하는 make-rule: state × symbol × todo × move × state -> rule

에서 move 가 'left 일때도 마찬가지로

읽기쓰기 헤드를 왼쪽으로 움직이는 것이 아니라

테이프를 왼쪽으로 움직이도록 구현하면 되나요?

[박유군]

blank 에 관해서도 질문이 있습니다

실행이 종료되었을 때 tape 에 blank 가 있다면

BLANK 로 출력해주면 되는 건가요? 아니면 blank는 출력하지는 않는건가요?



아님 혹시 애초에 실행종료되었을 때에

tape에 blank가 남지 않도록 ruletable 을 작성하나요?

blank 가 남는다면 테이프 양 끝에만 존재할 수 있나요 아니면

중간중간에도 존재 할 수 있는 건가요?

[이영석]

숙제문서에 보시면 left right 는 테입의 움직이는 방향입니다.

출력에 관한내용은 빠른 시일내에 공지하겠습니다.

[엄태건]

[이영석]

사실 문제를 해석하기 나름인데 todo 의 left right 도 테입이 움직이는 방향으로 숙제를 작성해주세요