Computational Complexity and Computability
Lecture 8 – Undecidable Problems
Koushik Pal
University of Toronto
February 3, 2021
Reducibility
Definition
Let A, B be two languages. We say A is mapping reducible to B, written A ≤m B, if there is a computable function f : Σ∗ → Σ∗ such that for every w ∈ Σ∗,
w∈A ⇐⇒ f(w)∈B.
The function f is called the reduction from A to B.
The Halting Problem Definition
HALTTM := {⟨M,w⟩ | M is a TM which halts on w}. Theorem
HALTTM ∈SD\D. Proof.
We will prove the theorem by showing that
HALTTM ≤m ATM (hence, HALTTM ∈ SD); and ATM ≤m HALTTM (hence, HALTTM ̸∈ D).
This is equivalent to saying HALTTM ≡m ATM.
The Halting Problem
HALTTM ≤m ATM : Define f : Σ∗ → Σ∗ as follows: ⟨M,w⟩ → ⟨M′,w⟩
x → ⟨Mloop, ε⟩,
where M′ accepts w iff M halts on w, and Mloop always loops.
Clearly, f is computable and y ∈ HALTTM ⇐⇒ f(y) ∈ ATM. ATM ≤m HALTTM : Define f : Σ∗ → Σ∗ as follows:
⟨M,w⟩ → ⟨M′,w⟩
x → ⟨Mloop, ε⟩,
where M′ halts on w iff M accepts w.
Clearly, f is computable and y ∈ ATM ⇐⇒ f(y) ∈ HALTTM.
The Equality Problem Definition
EQTM := {⟨M,M⟩ | M,M are TMs with L(M) = L(M)}. Theorem
EQTM is neither in SD nor in coSD. Proof.
We will prove the theorem by showing that
ATM ≤m EQTM (hence, EQTM ̸∈ coSD); and ATM ≤m EQcTM (hence, EQTM ̸∈ SD).
The Equality Problem
ATM ≤m EQTM : Define f : Σ∗ → Σ∗ as follows: ⟨M,w⟩ → ⟨Maccept,M′⟩
x → ⟨Maccept, Mreject⟩,
where Maccept is a TM that accepts everything, Mreject is a TM that rejects everything, and M′ is a TM that, on any input, runs M on w and accepts iff M accepts. In other words,
Thus,
L(M ) =
⟨M,w⟩ ∈ ATM
⇐⇒ ⇐⇒ ⇐⇒
M accepts w L(Maccept) = L(M′) ⟨Maccept,M′⟩ ∈ EQTM.
′
Σ∗ ∅
if M accepts w otherwise.
The Equality Problem
ATM ≤m EQcTM : Define f : Σ∗ → Σ∗ as follows: ⟨M,w⟩ → ⟨Mreject,M′⟩
x → ⟨Maccept, Maccept⟩, where Maccept, Mreject and M′ are as before.
Thus,
⟨M,w⟩∈ATM ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒
M accepts w L(Mreject)̸=L(M′) ⟨Mreject,M′⟩ ̸∈ EQTM ⟨Mreject,M′⟩ ∈ EQcTM.
Rice’s Theorem
Theorem
Let P be any language consisting of Turing machine descriptions such that
1. P is nontrivial, i.e., P contains some, but not all, Turing machine descriptions.
2. P is a property of the TM’s languages, i.e., whenever L(M) = L(M), then ⟨M⟩ ∈ P ⇐⇒ ⟨M⟩ ∈ P.
Then P is undecidable.
Proof of Rice’s Theorem Proof.
We prove this by showing ATM ≤M P.
Let Mreject be a TM that always rejects. We may assume without
loss of generality that Mreject ̸∈ P (otherwise replace P by Pc).
Since P is nontrivial, there exists a TM T such that ⟨T ⟩ ∈ P .
Define f : Σ∗ → Σ∗ as follows:
⟨M, w⟩ → Mw
x → Mreject,
where Mw, on input y, rejects if M rejects w, else simulates T on y and outputs whatever T outputs.
Proof of Rice’s Theorem
If M accepts w, then L(Mw) = L(T). Hence, Mw ∈ P.
If M rejects w, then L(Mw) = ∅ = L(Mreject). Hence, Mw ̸∈ P.
Finally, if M loops on w, then Mw loops on all inputs y. In this case too, L(Mw) = ∅ = L(Mreject). Hence, Mw ̸∈ P.
Consequently,
i.e., ATM ≤M P.
⟨M,w⟩∈ATM ⇐⇒Mw∈P,
Applications of Rice’s Theorem
Applications
1. EMPTYTM :={⟨M⟩|M isaTMandL(M)=∅}
2. FINITETM := {⟨M⟩ | M is a TM and L(M) is finite}
3. REGULARTM := {⟨M⟩ | M is a TM and L(M) is regular}
4. DECIDABLETM := {⟨M⟩ | M is a TM and L(M) is decidable}
By Rice’s Theorem, all the above languages are undecidable.
Venn diagram of different classes
semi-decidable
EQTM
decidable context-free regular
finite
∅, {ε}
{an |n≥} {anbn |n≥} {anbncn | n ≥ }
co-semi-decidable
DIAGT M
ATM HALTTM