Mathematical Logic 10 Halting Problem

---

R-computable

Let F: A* -> B* (A,B are 2 alphabets)

(1)A program P computes F if for all w $\in$ A*, P: w->F(w)

(2)F is R-computable if there is a program which computes F.

---

Halting Problem for the register machine

---

Gödel numbering

Def:
B:= A U {A,B,…,Z} U {0,1,…,9} U {=,+,-,|}.
Words in B* are ordered lexicographically(字典序).

Encode each program as a word in B*
Example:
0LETR1 = R1 - a0|1PRINT|2HALT.

Assume that this word is the n-th word in the lexicographical ordering of B∗.Then we set:

$w_p$ = $a_0a_0...a_0$(n times)

Π := { $w_P$ |P a program over A }.

The mapping P->$w_P$ is called Gödel numbering.
$w_P$ is called the Gödel number of P.

Π is R-decidable.

Π’halt is not R-decidable.

Π’halt := { $w_P$ |P a program over A and P:$w_P$->halt}
PF:
Assume that P0 decides Π’halt
0 …
1 …
…
10 PRINT
…
k HALT

We can build a P1
0 …
1 …
…
10 IF R = □ THEN k ELSE k or k or k… or k
…
k IF R = □ THEN k ELSE k+1 or k+1 or k+1… or k+1
k+1 HALT

Clearly contradict!

Πhalt is not R-decidable.

Πhalt := { $w_P$ |P a program over A and P: □ ->halt}

PF:
Build P+:
P : $w_P$ -> halt -> P+ : □ -> halt

A further program T:
$w_P$ -> $w_{P+}$

With P0 and T we design a program which decides Π’halt. On any w $\in$ A∗:

• the program first test whether w = $w_P$ for some P.If not, it rejects immediately.
• Otherwise, it uses T to computes $w_{P+}$. Then the program calls P0 on input wP+.
• It correctly decides whether P : wP -> halt.

---

The undecidability of first-order logic.(see u next time)