[계산이론](19)[여러가지 TM]

여러가지 TM
앞에서 본 TM(Deterministic Turing Machine)말고도 여러 TM이 있다.
그리고 이 TM들의 power는 전부 같다!

 

stay TM

Left, Right 말고도 제자리에 멈춰있는 Stay가 포함된 TM
즉, $\delta : \ Q \times \Gamma \rightarrow Q \times \Gamma \times {L, \ R, \ S}$

stay TM = TM 증명

• TM -> stay TM
  일반 TM은 stay 기능을 사용하지 않는 stay TM과 같으므로,
  TM을 stay TM으로 나타낼 수 있다.
• stay TM -> TM
  stay 기능을 left, right만 있는 TM에서 구현하는 법은
  tape과 state에 아무 변화도 주지 않고
  left, right 1번씩 하는 것이다.
  즉, stay TM의 trans δ(q1, a) = (q2, b, S)
      ⇔ δ(q1, a) = (r, b, L), δ(r, b) = (q2, ?, R)
      (?는 head가 가리키는 tape의 원소)

 

Multitape TM

tape가 여러개인 TM
즉, $\delta : \ Q \times \Gamma^{k} \rightarrow Q \times \Gamma^{k} \times {L, \ R, \ S}^k$
    단, k = tape의 개수

multitape TM = TM 증명

• TM -> multitape TM
  일반 TM은 tape을 1개만 쓰는 multitape TM과 같으므로,
  TM을 multitape TM으로 나타낼 수 있다.
• multitape TM -> TM
  k개의 tape의 정보를 1개의 tape로 옮길 수 있는가? -> yes!
      tape은 무한한 저장공간을 가지고 있으므로,
      1개의 tape에서 충분히 표현 가능
          $\aleph_0$ == $k \times \aleph_0$ 
          더 알길 원한다면 집합론을 보시오...
  
  구체적으로 어떻게?
  구분자 #와 시작에 . 찍기
  1. 각 tape의 input string a, b, ... 는 tape에
     $# \dot{a_1}a_2a_3...# \dot{b_1}b_2b_3...# \dot{⊔} ...$
  2. #를 지나고 .이 찍힌 문자를 본다면 해당 trans 수행
     만약 뒤에 공간이 없는데 오른쪽으로 이동하려 한다면?
     -> 뒤의 모든 것들을 오른쪽으로 1칸씩 밀고 ⊔채우고 계속
  3. 연산에 따라 .과 tape, state를 바꾸며 연산하면 됨~

 

Nondeterministic TM (NTM)

여러 경우의 수를 다 보는 TM (NFA에서랑 똑같음)
즉, $\delta : \ Q \times \Gamma \rightarrow P(Q \times \Gamma \times {L, \ R, \ S})$
trans의 결과가 집합이 됨
경우의 수 중 하나라도 accept하면 accept

NTM = TM 증명

• TM -> NTM
  일반 TM은 경우가 1가지인 NTM과 같으므로,
  TM을 NTM으로 나타낼 수 있다.
      즉, $P(Q \times \Gamma \times \{L, \ R, \ S\})$ = $Q\times \Gamma \times \{L, \ R, \ S\}$
• NTM -> TM
  multitape TM = TM이므로, NTM -> MTM을 증명하겠다.
  k=3인 MTM
      tape 1: input tape
          NTM에 들어온 input w의 원본을 저장
      tape 2: simulation tape
          원본을 복사해서 여기서 연산
      tape 3: address tape
          NTM에서 어느 경우를 따라가고 있는지 나타냄
  NTM의 경우의 수를 tree 형태로 나타내어 tape 3에서 BFS를 한다
      (DFS의 경우 loop에 빠지면 큰일!)
  
  다음 과정으로 연산하면 MTM으로 NTM과 동일한 일을 할 수 있다.
  1. tape 2를 w로 초기화
  2. tape 2에서 연산을 진행하며,
     이때, tape 3를 참고하여 다음 어떤 경우를 따를 지 봐야 함
  3. tape 3에 기호가 남아있지 않음 or reject or invalid이면 해당 분기 종료 후 4번으로 이동
     아니라면 2번으로 가서 반복
  4. tape 3의 값을 "BFS 순서"에 의해 다음 값으로 바꾸고 2번으로 가서 반복

이때, 모든 branch가 무조건 멈추는 NTM은 decider이다.

 

기타 TM

• enumerator
  enumerator가 나타내는 langugage L의 문열을 1개씩 출력한다.
      모든 L의 원소를 출력한다
      중복 출력은 허용
  암호학에서 많이 쓰인다
  recursively enumerable language
  L={w∈Σ∗∣w is printed by E}
  w∈L⟺∃t∈N(E at step t outputs w)
• TM의 특징
  같은 power를 가지는 TM을 보면 공통적으로
      무제한 메모리
      임의 위치 엑세스
  이 2가지를 가지고 있다