Turing Machines, Undecidability & Rice's Theorem
“Recursive vs RE languages, Halting problem proof by diagonalization, and Rice's Theorem.”
1.The Formal Turing Machine Model & Language Classes
§ 5.1.A Turing Machine (TM) is formally defined as a 7-tuple M = (Q, \Sigma, \Gamma, \delta, q_0, B, F), where:
- \Gamma: Tape alphabet containing \Sigma \subsetneq \Gamma and blank symbol B \in \Gamma \setminus \Sigma.
- \delta: Transition function mapping Q × \Gamma \to Q × \Gamma × {L, R}. The read/write head modifies the current cell and steps Left (L) or Right (R).
Language Class Hierarchy:
1. Recursively Enumerable (RE / Turing-Recognizable / Type 0):
- A language L is RE if there exists a TM M such that for any string w \in L, M halts and accepts. If w \notin L, M may either halt and reject OR loop indefinitely.
2. Recursive (REC / Turing-Decidable):
- A language L is Recursive if there exists a TM (a 'Decider') that halts on all inputs (accepts if w \in L, rejects if w \notin L). Never loops forever!
Fundamental Theorem: A language L is Recursive IF AND ONLY IF both L and its complement \overline{L} are Recursively Enumerable (L \in REC \iff L \in RE \land \overline{L} \in RE).
2.The Halting Problem & Proof by Diagonalization
§ 5.2.The Halting Problem (H_{TM}):
$H_{TM} = { \langle M, w \rangle \mid M is a TM and M halts on input w }$
Turing's Diagonalization Proof (1936):
1. Assume for contradiction that there exists a decider H that takes \langle M, w \rangle and returns YES if M halts on w, and NO if M loops on w.
2. Construct an adversarial machine D that takes the encoding of any machine \langle M \rangle as input:
- D runs H on \langle M, \langle M \rangle \rangle.
- If H says YES (i.e. M halts on its own code), D enters an intentional infinite loop.
- If H says NO (i.e. M loops on its own code), D immediately halts and accepts.
3. What happens when D is fed its own encoding: \langle D, \langle D \rangle \rangle?
- If D halts on \langle D \rangle \implies H says YES \implies D loops!
- If D loops on \langle D \rangle \implies H says NO \implies D halts!
4. Both branches produce a logical impossibility \implies H cannot exist! H_{TM} is UNDECIDABLE.
3.Rice's Theorem for Semantic Language Properties
§ 5.3.Rice's Theorem is the single fastest decision rule for GATE computability problems:
> Any non-trivial property of the LANGUAGE recognized by a Turing Machine is UNDECIDABLE.
The Two Criteria for Rice's Theorem:
1. Semantic Property: The property must be about the language L(M) accepted by the machine, NOT about the syntactic machine description (e.g., number of states, steps taken).
2. Non-Trivial: There exists at least one TM whose language satisfies the property, and at least one TM whose language does NOT satisfy it (P \ne \emptyset and P \ne All RE languages).
Examples of Undecidable Properties via Rice's Theorem:
- Is L(M) empty? \implies Undecidable!
- Is L(M) finite? \implies Undecidable!
- Is L(M) regular? \implies Undecidable!
- Is L(M) context-free? \implies Undecidable!
- Does L(M) contain the string '101'? \implies Undecidable!
If a question asks about the CODE, HARDWARE, or EXECUTION STEPS of the Turing machine (e.g. 'Does TM M take more than 100 steps on input w?' or 'Does M have 10 states?'), Rice's Theorem DOES NOT APPLY! We can simply inspect the state table or simulate the machine for 100 steps; such questions are completely DECIDABLE.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with clear minimal DFA construction and language classification.
Exam-pattern oriented with closure table drilling and decidability proofs.
Mathematically rigorous treatment for high-rank GATE aspirants.