UNIT – V Turing Machines and Undecidability
UNIT – V Turing Machines and Undecidability Syllabus: Turing Machine and Tape System · Multi-Tape Turing Machine · Universal Turing Machine · Halting Problem · Undecidability · Post Correspondence Problem · Church–Turing Thesis Notation Used in These Notes Symbol Meaning Example M A Turing Machine M = (Q, Σ, Γ, δ, q 0 , B, F) Q Finite set of states {q 0 , q 1 , q f } Σ Input alphabet (does not contain the blank) Σ = {0, 1} Γ Tape alphabet; Σ ⊆ Γ and B ∈ Γ Γ = {0, 1, X, B} δ Transition function δ(q 0 , 1) = (q 1 , 0, R) q 0 , F Start state; set of accepting (final) states F = {q f } B Blank symbol (an empty tape cell) …B B 1 0 1 B B… L, R, S Head moves Left, ...