Turing Machines & Decidability

Turing Machine — The Ultimate Computer

Analogy: A Turing Machine is like a robot with an infinite scroll of paper. It can read a symbol, write a symbol, and move left or right. That is all it takes to compute anything a modern computer can compute.

TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

Q   = finite set of states
Σ   = input alphabet (does not include blank ⊔)
Γ   = tape alphabet (Γ ⊇ Σ, includes blank ⊔)
δ   = transition: Q × Γ → Q × Γ × {L, R}
      (current state + tape symbol → new state + write symbol + move direction)
q₀  = start state
q_accept = accepting state (halt and accept)
q_reject = rejecting state (halt and reject)

---

Three Levels of Language Recognition

                  Decidable (Recursive)
                  /
    Always halts  → ACCEPT or REJECT

                  RE (Turing-recognisable)
                  /
    Accepts members → ACCEPT
    On non-members → may LOOP FOREVER or REJECT

                  non-RE
                  /
    No TM can even reliably accept all members

Class	TM Behaviour	Closed under complement?
Decidable	Always halts (accept or reject)	Yes
RE	Accepts members, may loop on non-members	No
co-RE	Complement of RE	No

Key fact: L is decidable ⟺ both L and its complement are RE.

---

The Halting Problem — Undecidable!

Problem: Given (M, w) — description of TM M and input w — does M halt on w?

Proof by contradiction (diagonalisation):

Assume there exists TM H that decides the halting problem:
  H accepts (M, w) if M halts on w
  H rejects (M, w) if M loops on w

Construct TM D using H:
  D on input ⟨M⟩:
    Run H on (M, ⟨M⟩)
    If H says "halts" → D loops forever
    If H says "loops" → D accepts

Now ask: What does D do on input ⟨D⟩?
  If D halts → H says "halts" → D loops → contradiction!
  If D loops → H says "loops" → D accepts (halts) → contradiction!

Both cases lead to contradiction → H cannot exist → Halting problem is UNDECIDABLE.

---

ATM — Acceptance Problem

ATM = {⟨M, w⟩ | TM M accepts input w}

ATM is RE (Turing-recognisable): just simulate M on w; if it accepts, accept.
ATM is NOT decidable: if M loops on w, we loop forever — cannot always reject.

Complement of ATM is NOT even RE.

---

Rice's Theorem — The Big Hammer

Any non-trivial property of the LANGUAGE of a TM is undecidable.

"Non-trivial" = the property is true for SOME TMs and false for OTHERS

If P is a non-trivial property of L(M), then:
  "Does TM M have property P?" is UNDECIDABLE.

Examples — undecidable by Rice's theorem:

"Does M accept the empty string ε?"
"Is L(M) a regular language?"
"Is L(M) finite?"
"Does M accept at least 5 strings?"
"Is L(M) = ∅?"

NOT Rice's theorem (structural properties — decidable):

"Does M have exactly 5 states?" — about the machine, not the language
"Does M have a self-loop?" — structural

---

Reductions — Proving Undecidability

Idea: If you can show that solving problem B would let you solve the already-impossible problem A, then B must also be impossible.

A ≤m B  ("A many-one reduces to B")
= there is a computable function f such that: w ∈ A ⟺ f(w) ∈ B

Implication table:
┌────────────────┬──────────┬────────────────┐
│ A ≤m B and ... │ A is...  │ Then B is...   │
├────────────────┼──────────┼────────────────┤
│                │undecidable│ undecidable   │
│                │ non-RE   │  non-RE        │
│                │ decidable│  nothing new   │
└────────────────┴──────────┴────────────────┘

Also: if B is decidable and A ≤m B → A is decidable

---

The Chomsky Hierarchy (Summary)

Type 0: Recursively Enumerable → Turing Machine
Type 1: Context-Sensitive → Linear Bounded Automaton (LBA)
Type 2: Context-Free → Pushdown Automaton (PDA)
Type 3: Regular → Finite Automaton (DFA/NFA)

Each level is strictly more powerful than the one below.

---

Quick Check

Q1. Is the property "Does TM M accept all strings over {0,1}?" decidable? Answer: No — this is a non-trivial semantic property of L(M). By Rice's theorem, it is undecidable.

Q2. L is RE and complement of L is also RE. What can you conclude? Answer: L is decidable. (A language is decidable iff both it and its complement are RE.)

Q3. If problem A reduces to problem B (A ≤m B), and A is undecidable, what do we know about B? Answer: B is also undecidable. (If B were decidable, we could solve A using the reduction — contradicting A being undecidable.)