• 테이프(Tape): 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다.
• 헤드(Head): 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동한다.
• 상태 기록기(State register): 현재 튜링 머신의 상태를 기록하고 있는 장치.
  • 개시 상태(Start state): 상태 기록기가 초기화된 상태를 의미한다.
  • 종료 상태(Halt state): 수행이 종료된 상태.
• 행동표(Action table, transition table of instructions): 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다.
  • 기호를 지우거나 고쳐 쓴다.
  • 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머문다.
  • 상태를 변경한다. 같은 상태에 머무를 수도 있다.

Turing Machine (TM)

$M = (Q, \Sigma, \Gamma, \delta, q_0, \sqcup, F)$

• Q: states
• $\Sigma$: input alphabet, $\Sigma \subseteq \Gamma - \{ \sqcup\}$
• $\Gamma$: tape alphabet
• $\delta$: $Q \times \Gamma → Q \times \Gamma \times \{L,R\}$: transition function
  • 입력: $\delta(q,Z)$: state q와 tape symbol Z을 받아서 움직인다. 즉 특정 state에서 어떤 기호를 읽었을 때 어떻게 행동할지를 정의한다.
  • 출력: $(p,Y,D)$: state p와 새로운 tape symbol Y, 방향 D(L or R) state가 p로 바뀌고 Z를 Y로 바꾸었으며 왼쪽/오른쪽으로 한칸 이동
• $q_0 \in Q$: start state
• $\sqcup$: blank
• $F \subseteq Q$: final states

ex. 1을 찾으러 오른쪽으로 이동하는 튜링 머신 1을 찾으면 0으로 바꾸고 final로 바뀌어 정지(halt) 빈칸에 도달하면 1을 기록하고 왼쪽으로 한칸

정지? 마지막 state에서는 아무런 transition을 정의해 놓지 않기 때문에 TM은 영구적으로 정지할 것이다

• 불행하게도 정지하는지 판별할 수 없다(정지 문제)