Halting Problem

Halting Problem is closely related with reduction.

Church-Turing Thesis

Object O "O"

Problem; Given G, is G is a connected graph?
Language: L={G:G is a connected graph}



A reduction from A(A over ΣA) to B(B over ΣB) is a recursive(computable) function f(ΣA)ΣB such that for wΣA, wA iff f(w)B

Theorem: Suppose there is a reduction f from A to B. If B is recursive, that A is recursive.

Proof: MB decides B, find MA to decide A.
MA = on input w
(1) compute f(w)
(2) run MB on f(w)
(3) output the result


What is Countable

A set is countable if it is finite or it is equinumerous with N.
Let A be a set. The following statements are equiv.
(1) A is countable
(2) injection f:AN
(3) there exists some way to enumerate A such that for aA, a can be enumerated within n steps where n only depends on a

Lemma: Any subset of a countable set is countable

Lemma: Turing Machine is countable.

Let Σ be an alphabet. Σ is countable

enumerate all the strings in Σ, in increasing length wΣ, w will be listed within

|Σ0|+|Σ1|+|Σ|w|| steps
L is uncountable

Let Σ be some alphabet
Let L be the set of all languages
Suppose that L is countable
The language in L can be listed as


Since Σ is countable, the strings in Σ can be listed as $$S_1, S_2, S_3, \dots$$
D={si:siLi} is a language over Σ

for any i,siDif and only if si LiD LiDL


Give the definition of H and Hd

H={M w: M is a TM that halts on w}Hd={M:M is a TM that does NOT halt on M}


Rice's theorem

Rice's theorem
R = {"M": M is a TM with L(M)L} is not recursive where L is a proper, non-empty subset of all recursively enumerable language.

Proof: Make a reduction from H to R
(1) If L
construct f("M""w") = on input v
step1 run M on w
step2 run MA on v, where MA satisfy that L(MA)L

L[f(M w)]={L(MA)=ALif M wHLif M wH

 M wH if and only if f(M w)R
(2) If L
transform the the problem from L into L¯

Closure Property

operator recursive recursive enumerable
Lemma: A language A is recursive if and only if A and A¯ are recursively enumerable

H is recursively enumerable, H¯ is not recursively enumerable

According to the Lemma, because H is not enumerable

Turing Enumerable


We say a TM M enumerates a language L is for some state q,


Lexicographically Turing Enumerable


Let M be a TM that enumerates L
We say M lexicographically enumerate L if whenever


w is after w in lexicographically order, M+ means at least one step.

What is lexicographical?