[오토마타] Turing Machine

- Turing Machine의 기본개념

 

Turing Machine은 Tape을 이용한 오토마타이다.

 

- tape에는 input이 들어가 있고, TM은 tape에서 read와 write 모두 가능하다.

 

- input을 왼쪽에서 오른쪽으로만 읽는 기존의 machine들과 다르게 Left, Right, Stay방향으로 진행 가능하다. (stay의 경우 left right 두번이라고 생각하면 된다)

 

- tape는 infinite한 성질을 가지는데, 맨 왼쪽에서 leftmove할경우 무시하고, rightmove할 경우 blank(오른쪽으로 무한한 blank를 가진다고 이해하면 쉽다)을 계속 읽을 수 있다.

 

- TM이 accept나 reject되지 않고 loop를 가져서 무한히 동작할 수도 있다. 모든 input에 대해 무한히 동작하지 않고 accept나 reject에서 halt되는 TM은 Dicider라고 한다.

 

 

 

1. Standard(Deterministic) Turing Machine

 

 Deterministic TM의 경우 기본적으로 DFA와 유사성을 가진다. State diagram으로 표현하면 한 state에서 한개의 input을 read해서 write, move할수 있다.

• Q : state
• Σ : input alphabet (Π를 제외한다 - tape의 Π는 input으로 인식하지 않아야 한다 - 인식하게되면 Π를 계속 읽어서 문제가 발생할 수 있다.
• Τ : tape alphabet : Σ에 Π를 포함한다. (tape의 문자이긴 하므로,,)
• δ : function : Q - {qaccept, qreject} x Τ -> Q x Τ x {L, R, S}
• q0 : start state
• qaccept, qreject : accept state, reject state

<Configuration 표현법>

• (q0)w : Start configuration. input w 맨앞에 q0(start state)가 위치함을 의미한다
• ua(qi)acv : a에서 state qi가 위치함을 의미한다.
• u(qaccept)v : accepting configuration

 

 

 

2.  Multitape Turing Machine

 

 multitape (ex.k-tape)을 가지는 Turing Machine을 의미한다.

 

k-tape TM의 Transition function :

δ : Q - {qaccept, qreject} * T = Q * T^k * {L, R, S}^k

δ(qi, a1, a2, ..., ak) = (qj, b1, b2, ..., bk, L, R, ...,L)

> head가 qi state에 위치할 때 a1...ak를 읽으면 qj state로 가고 b1...bk를 쓰고 L...R로 이동함을 의미

 

k-tape TM의 time complexity : 

t(n) time k-tape TM = O(t(n)²)-time standard TM

 

 

 

 

3. Nondeterministic Turing Machine

 

 하나의 state에서 여러개의 transition function이 존재할 수 있다.

 

Nondeterministic TM의 Transition function :

δ : Q - {qaccept, qreject} * T = 2^Q*T*{L,R,S}

(qj, b, L) ∈ δ(qi, a)  (여러개의 함수가 존재할수있다)

 

NTM이 w∈L인 input w중에 최소 하나라도 accept되면 NTM은 L을 recognize한다고 이야기한다. 

NTM이 w∈L || w∉L인 모든 input w가 accept나 reject로 halt된다면 NTM은 decider라고 이야기한다.

 

 

 

 

 

4. Universal Turing Machine

 

 Universal turing machine은 어떤 machine M이 input w에 대해 수행하는 계산을 따라하는 Deterministic한 TM을 말한다.

{<M,w> : ~ } 

Tape 1 : Description of M, transition function을 어떤식으로던지 binary encoding한다 (read only)

Tape 2 : Tape contends of M, 현재 tape의 모양 (input넣기)

Tape 3 : Internal state of M, M의 state를 적음

 

δ(q0, 1) -> (q1, 1, R)

1. tape1에서 δ를 읽는다

2. tape2의 값을 바꾸기 (1->1)

3. tape3의 값을 바꾸기 (q0->q1)

4. header 오른쪽으로 옮기기

 

 

5.  Features of Turing Machine

 

- Turing's Halting Theorem

 Halt = {<M,w> : M halts on w} 는 turing decidable하지 않다. 즉, 정지문제는 TM에서 판정할 수 없다. (recognizable하다.)

pf) 임의의 문자열 w에 대해서 종료하면 true(accept), 종료하지 않으면 false(reject)를 내놓는 튜링머신 M이 있다고 하자.

  H(<M,w>) = if (M halt) return true; else return false;

이때 우리는 M이 halt하면 루프를 돌고, halt하지 않으면 true를 리턴하는 다음과 같은 TM D를 정의할 수 있다.

  D(<M>) = if (H(<M,<M>>)==true) loop forever; else return true; 

(모든 프로그램은 어떤 문자열로 포현될 수 있으므로 이렇게 표현가능)

만약 이때, D(<D>)를 실행시키면

  D(<D>)는 D가 halt하면 루프를 돌고, D가 halt하지 않으면 true를 반환하게 된다. 따라서 모순이며, Halt를 판별해주는 TM은 존재하지 않는다

 

 

 

1. recognizable하다고 dicidable하지는 않다.

 : {<M,w> : TM M halts on w} 는 decidable(x), recognizable(o)

2. 세상에는 Turing recognizable하지 않은 language도 존재한다

 : Turing machines의 binary encoding은 셀 수 있지만, binary language의 집합 개수는 셀 수 없다.

3. L이 Turing decidable하면 L^c도 decidable하다 (역 성립)

 : L을 decide하는 machine M은 w∈M을 accept하고 w∈M^c을 reject한다. 반대로 M^c은 w∈M을 reject하고 w∈M^c을 accept한다. 따라서 둘중에 하나가 decidable하면 역도 decidable하다.

4. L&L^c이 Turing Recognizable하면 L&L^c은 Turing Decidable하다. 역은 당연히 성립한다.

 : L을 recognize하는 M1과 L^c을 recognize하는 M2가 있다고 하자. 임의의 input w에대해 M1, M2중 1개는 accept할 것이고, M1이 accept하면 M2는 reject하므로 decidable하다. (L과 L^c 둘중하나는 무조건 accept하게 된다.)

5. L이 recognizable하다고 L^c도 recognizable하지는 않는다. (3과 반대)

 : Halt를 recognize하는 TM은 존재하는데, 만약 Halt^c를 recognize하는 TM도 존재한다면, 4번에 의해 Halt가 decidable하게 되는데 이것은 Turing Halting Algorithm에 위배된다.

 

1-1. standard turing machine이 l을 recognize하면 l에 속하는 입력 w의 computation tree높이는 유한하다

> stm이 recognize하다는것은 tree의 마지막에 accept한다는 것이므로 true..

1-2. standard turing machine이 l을 recognize하면 l에 속하지 않는 입력 w의 computation tree높이는 무한하다.

> l에 속하지 않는 입력은 stm에서 loop를 돌 수 있으므로 true

2-1. standard turing machine이 l을 decide하면 l에 속하는 입력 w의 computation tree의 높이는 유한하다.

> l을 decide하면 무조건 halt하므로 유한. true

2-2. standard turing machine이 l을 decide하면 l에 속하지 않는 입력 w의 computation tree의 높이는 무한하다.

> l을 decide하면 무조건 halt하므로 무조건 reject한다는 의미이므로 유한하다. false.

3-1. Non-deterministic Turing Machine에 의해 accept되는 입력의 Computation Tree 높이는 유한하다.

> accept되는 branch의 높이는 유한하지만 tree의 높이는 무한할 수 있다.. false

3.2 Non-deterministic Turing Machine에 의해 accept되는 입력의 Computation Tree 높이는 무한하다.

> tree의 높이는 무한할 수 있다. false

4.1 Non-deterministic Turing Machine에 의해 reject되는 입력의 Computation Tree 높이는 유한하다.

> reject되는 입력의 tree높이는 무한할 수 있다. (reject되는 branch만 유한)

> reject된다면 계속 accept를 찾을 것이므로 tree의높이는 유한하다.

4-2. Non-deterministic Turing Machine에 의해 reject되는 입력의 Computation Tree 높이는 무한하다.

> true

5-1. Non-deterministic Decider에 의해 accept되는 입력의 Computation Tree 높이는 유한하다. 

> true. decider이므로

5-2. Non-deterministic Decider에 의해 reject되는 입력의 Computation Tree 높이는 유한하다. 

> decider면 reject든 accept든 모든 branch에서 halt한다.

6-1. 3-Tape Decider로 Poly(n) step에 풀 수 있는 문제는 Standard Turing Machine으로  Poly(n)  step에 풀 수 있다. 

> Poly(n)^2 step이므로 true

6-2. Non-deterministic Decider로 Poly(n) step에 풀 수 있는 문제는 Standard Turing Machine으로  Poly(n)  step에 풀 수 있다. 

> false

7-1. Universal Turing Machine은 Deterministic Turing Machine이다. 

> universal turing machine은 deterministic하다. decider는 아니다.

7-2. Universal Turing Machine은 Non-deterministic Turing Machine이다. 

> false

> Deterministic은 Non-deterministic에 속한다

8-1. Standard Turing machine M이 인풋 w를 accept한다면 Universal Turing Machine은 인풋 <M,w>에 대해 종료한다. 

> true,

8-2. Standard Turing machine M이 인풋 w를 reject한다면 Universal Turing Machine은 인풋 <M,w>에 대해 종료한다.

> true

8-3 Standard Turing machine M이 인풋 w에 대해 무한히 돈다면 Universal Turing Machine은 인풋 <M,w>에 대해 무한히 돈다.

> true. universal turing machine은 machine을 그대로 따라하는 머신이다.

9-1. Halting language는 Turing Recognizable이다.

> true

9-2. Halting language는 Turing Decidable이다.

> false

10-1. Halting language의 complement는 Turing Recognizable이다.

> false. HAM

10-2. Halting language의 complement는 Turing Decidable이다.

> false.

11-1. L이 Turing Decidable이면, L의 complement는 Turing Recognizable이다. 

> true.

11-2. L이 Turing Decidable이면, L의 complement는 Turing Decidable이다. 

> true

12-1. L이 Turing Recognizable이면, L의 complement는 Turing Recognizable이다.

> false (halting problem)

12-2. L과 L의 complement이 둘 다 Turing Recognizable이면, 둘 다 Turing Decidable이다.

> true?

13-1. A가 P에 속하면 A의 complement는 P에 속한다. 

> true

13-2. A가 NP에 속하면 A의 complement는 NP에 속한다. 

> false

14-1.  A와 B가 P에 속하면 그들의 합집합은 P에 속한다. 

> true

14-2. A와 B가 P에 속하면 그들의 교집합은 P에 속한다. 

> true

14-3. A와 B가 P에 속하면 그들의 차집합 A-B는 P에 속한다. 

> true

15-1. A와 B가 NP에 속하면 그들의 합집합은 NP에 속한다. 

> true

15-2. A와 B가 NP에 속하면 그들의 교집합은 NP에 속한다. 

> true

15-3.A와 B가 NP에 속하면 그들의 차집합 A-B는 NP에 속한다. 

> false. B=NP라고 ~B=NP라는 보장이 없으므로 B에서 reject algorithm을 확인할 수 없다.