Introduction to Formal Languages, Automata Theory and Computation

Chapter 11. Universal Turing Machine and Decidability

In this chapter, we consider universal turing machine (TM), the halting problem, and the concept of undecidability.

Encoding and Enumeration of Turing Machines

The TM is specified by a 6-tuple M = (K, Σ, Γ, δ, q₀, F) (refer Definition 9.1). in Γ is a special symbol. The TM can be encoded as a binary string. Without loss of generality, we can take the state set as (q₁,q₂, ..., q_s} where q₁ is the initial state and q₂ is the final state. The tape symbol set can be taken as {,0,1}. A move of the TM ...