# CS代考计算机代写 Computational Complexity and Computability

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 ∈SDD. 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