[컴퓨테이션 이론] Turing Machine_정의

튜링머신이란?
제한적이지 않은 메모리에서 infinite한 tape을 사용하는 모델이다 .symbol에 읽고 쓸 수 있는 tape head를 가지고 이 tape head는 tape 위를 좌우로 움직인다.

튜링머신의 특징
1. 튜링 머신은 좌우로 움직이며 읽고 쓸 수 있다.
2. 테이프(tape)는 무한하다.
3. reject state나 accept state를 만나면 즉시 종료한다.만약 만나지 않으면, 무한 루프를 돈다.
예시 B = { w#w | w ∈ {0,1}* }

language B = { w#w | w ∈ {0,1}* } 이 있다고 하자.
input 011#011을 accept한다는 것을 어떻게 보일 것인가?
#의 앞부분과 뒷부분을 왔다갔다하면서 같은지 다른지 비교할 것이다. 처음에 0을 보면 오른쪽 첫번째 부분도 0인지를 비교할 것이다. 여러번 왔다갔다하면서 비교할 것이다.
#의 양쪽 string 을 체크할 것이다 . 0을 봤다 하면 X로 체크하고 , 그리고 #옆의 0을 보고 다시 돌아왔을 때, X로 체크한 것을 보고 아 이부분 은 '체크했구나' 를 깨닫는다. 이제 1을 cross out한 다음, 아 맞구나! 그리고 # 다다음을 보고 아맞구나!라고 하면서 그러다가 #를 만나면 다 끝난것인데, 본 string의 맨 오른쪽 글자 옆에 글자가 있으면 accept하면 안된다. reject state라는 것이있다. 이 state로 들어가버리면 중간에 끝나지 않더라도 들어가면 끝나게 된다.

Reject or Accept 조건
1. Zig - zag하면서 같은 symbol인지를 check
- #없이 끝까지 가면 reject.
2. #를 만나서 그옆의 symbol을 봤더니 같지 않으면 reject.
- # 오른쪽에 string이 남아있으면 reject. 아니면 accept
Accept state도 있고 reject state도 있다. 중요한 것은 transition function이다. 현재 상태에서 다음 상태로 어떻게 움직일 것인가? #를 가만히 놔두면 read하는 것이고 x로 고치면 write하는 것이다.
그 다음 head를 왼쪽으로 갈수도 있고 오른쪽으로 갈수 있다.

Turing machine의 Formal Definition

---

Turing machine의 Transition function
현재 어떤 상태에서 어떤 심볼을 읽었을 때 다음 상태를 어떤 상태로 전이할 것이고, 현재 심볼을 바꿀 것이 정의하는 것이 transition function이다.
어떤 상태 Q에서

이란뜻은, q에서 헤드 r에 a가 있으면 , r로 움직인다.
(이때, r은 state) 또한, symbol a는 b로 바꾸고 왼쪽으로 움직이라는 뜻이다 .(LEFT) pushdown automata 나 Finite automata랑 비슷하게 생겼지만 다르게 생겼다. Γ (감마) 는 tape alphabet이다.

B = { w#w | w ∈ {0,1} * }
011 # 011 이 langauge B에 들어가는 지 안들어가는 지 파악해보자. 0을 x로 바꾸어야 할 때 새로운 심볼을 허용해주겠다.
Blank 까지 허용하는 것이 Γ (감마)이다. tape에 쓸 수 있는 모든 symbol들이다 .

Example

첫번째 example을 보자. (Example 3.9 )
1) 테잎에 0이 있으면 0을 x로바꾸고 오른쪽으로 가세요. (q1 -> q2)
2) 0,1 -> R 0,1이건 고치지 말고 오른쪽으로 가고 q2에 머물러있으세요. (q2->q2)
3) 중간에 #를 꼭 만나야 하므로 세 덩어리로 분리해놓았다.
4) 0이거나 1이거나 x를 만나도 Left로 가세요! (q6 -> q6)
5) 왼쪽 뭉치와 오른쪽 뭉치는 다른 일을 해야한다.
6) q3는 #전에까지 계속 skip하도록 하는 state이다.
M이 어떤 string을 accept하는 것을 보여줄 것이다.
tape은 infinite한데 m개짜리니까 왼쪽에 딱 맞도록 되어있다 .

w1

w2

w3

w4

w5

..

..

..

wn

blank

어디까지 input인지 알아야되는데, blank는 시그마에 들어가지 않기 때문에,' Wn 까지 input이구나' 를 알 수 있다.  화살표 대로 고대로 정확히 해야한다.
그대로 한다는 것이 무엇이냐?
M이 transition function에 따라 head를 왼쪽, 오른쪽으로 움직인 다는 것이다. tape이 무한하기(inifinite) 때문에 언제든지 오른쪽으로 갈 수 있다. 첫번째 심볼에서는 왼쪽으로 가도 아무것도 없기 때문에 왼쪽으로 갈 수 없다 . 시작 state에서 accept나 reject 로 들어가면 끝나는 것이다. 두 가지 state에 가지 않으면 계속 왔다갔다 거린다.
FA나 PDA는 input을 한칸한칸읽고 끝을 만나면 끝나지만,
튜링머신은 끝나지 않고 무한 루프를 돌 수 있다. (암호학과 연관)
이제 우리는 configuration이라는 용어를 쓰려고 한다.
지금 어떤 상태에 있어요! 라는 스냅샷같은 것이 configuration이다 . configuration을 얘기하려는 이유는, 튜링머신 M이 있을때 M이 w를 어떻게 accept하려는 지 얘기하려고하는것이다.

튜링머신에 관한 다음글
https://life-with-coding.tistory.com/228

[컴퓨테이션 이론] Turing Machine 의 Decidable, Recognizable