computation theory (8) -Turing machine

    Turing machine은 무한한 tape와 오른쪽/왼쪽으로 움직이며 tape를 읽고 쓰기가 가능한 head로 이루어진 계산 모델이다. Turing machine은 7-tuple로 다음과 같이 정의한다.

Turing machine T = (Q, Σ, Γ, δ, q0, qaccept, qreject) Q 는 states의 집합 Σ 는 ⌊⌋(blank symbol)을 포함하지 않는 input alphabet  Γ 는 tape alphabet ( ⌊⌋ ∈ Γ and Σ ⊆ Γ ) δ 는 Q x Γ -> Q x Γ x {R, L} 인 transition function q0 는 start state qaccept 는 accept state qreject  는 reject state

Turing machine이 recognize하는 language를  Turing-recognizable또는 recursively enumerable language라고 한다. Turing-recognizable language는 accept, reject, loop한다. loop 상태에 빠지지 않고 항상 halting하는 machine을 decider라고 하며 decider가 recognize하는 language는 Turing-decidable 또는 decidable이라고 한다.