[계산이론](18)[Turing Machine]

 

Turing machine

tape: PDA의 input과 stack 역할
control: state diagram

특징

• 무제한 메모리 용량
  PDA의 stack마냥 메모리가 무한하다
• 무제약 메모리 접근
  PDA는 stack이라 맨 윗부분만 접근 가능했지만,
  TM은 어느 곳이든 head를 옮겨 데이터를 읽고 쓸 수 있다.
• accept, reject, loop
  accept, reject state에 도달만 하면 바로 accept, reject
  그리고 accept, reject에 도달하지 못하고 반복하는 loop가 존재할 수 잇다.

 

수학적 정의

정의 ($Q$, $\sum$, $\Gamma$ $\delta$, $q_0$, $q_{accept}$, $q_{reject}$)

• $Q$: 상태의 유한 집합
• $\sum$: input alphabet의 유한 집합
• $\Gamma$: tape alphabet의 유한 집합 (blank(⊔) 포함)
• $\delta$: transition function
  $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times {L, \ R}$
  즉, input과 tape를 보고 다음 state, tape 변동사항, {왼쪽, 오른쪽}움직임 을 정한다
• $q_0$: start state
  $q_0 \in Q$
• $q_{accept}$: accept state
  $q_{accept} \in Q$ <- 딱 1개
• $q_{reject}$: reject state
  $q_{reject} \in Q$ <- 딱 1개
  
  
• snapshot
  해당 정보만 가지고 주어진 튜링머신의 정확히 같은 상태를 복원할 수 있는 정보
  • 현재 state
  • 현재 tape
  • 현재 head
    예) 1 0 $q_3$ 1 0 이렇게 한다면,

recognizable VS decidable

앞서 TM의 결과가 accpet, reject, loop라고 했다.

• turing recognizable
  TM이 recognize할 수 있는 language
  
  
• decider
  오직 accept, reject만 존재하는 TM
  (즉, loop forever 없이 언젠가는 끝남)
• turing decidable
  decider가 recognize하는 language

즉, decidable ⊆ recognizable