Math 446 M. Flashman 5-8-02

[Based on A.G Hamilton's

Prop 7.21 (Enumeration) The set of all Turing machines
may be listed T0, T1, T2, T3, ... So that each number determines completely
and effectively the instructions for the corresponding machine. [**Proof:
**Use
Goedel numbers for the instruction list.]

**Def'n.: A number theoretic (partial) function is Turing
computable if there is a Turing machine which computes its values.**

Turing's Thesis: A (partial)
function is **Turing computable** if and only if there is** an algorithm
to compute the function**.

Church's Thesis: A (partial) function is

Prop 7.25 [Church=Turing] A (partial) function is
**Turing
computable** if and only if the (partial) function is** recursive.**
[Proof: not easy! see Minsky.]

Prop 7.26 [Universal Turing machine] There is a turing
machine which when given the pair (m,n) will compute the result of applying
Tm to the number n.

[**"proof":** Find Tm on the list , then apply Tm
to n. This algorithm gives the desired result... now apply Turing's thesis.]

Algorithm: Suppose fn is a recursive function with Turing machine Tn. Apply Tn to compute fn(n). Now add 1 to the result.

This algorithm corresponds to a recursive function fN by Church's thesis. Then what is fN(N)? If we follow the algorithm we have fN(N) = fN(N)+1. !!!!

The paradox is resolved by noting that these are partial functions... so the result is that there is no value for fN(N). That is the algorithm doesn't terminate or the Turing maching doesn't halt.

**Prop 7.28** **There is no
effective enumeration of all the (total) recursive functions of one variable**.
**Proof: **Suppose there is such an enumeration :
f0, f1, f2, ...

Algorithm: Given n, find fn, then compute fn(n) and add
1.

By Church's thesis there is a total recursive function
h(n) = fn(n) + 1.

But then h= fk for some k and we have h(k) = fk(k)
= fk(k) +1. OOOPs!

**The Halting Problem: Given (m,n) does the Turing
machine Tm halt when given the input n?**

**Prop 7.29. [The Halting Problem is unsolvable.]**
**There is no algorithm which will decide the halting
problem for all pairs (m,n).**

**Proof: ** Suppose there is such an algorithm.

Then , there is an algorithm will decide the question:

does the Turing machine T**n**
halt when given the input **n**?

By Turing's thesis, this will correspond to a Turing machine T that will give a result 0 or 1 depending upon whether Tn halts or not for the input n.

Thus with input n we have T halts

Here's a new Turing machine B:(i) with output 0 if Tn halts with input nand(ii) with output 1 if Tn does not halt with input n.

Do T and when T halts, look for a non zero square on the tape.

If it finds a nonzero square, halt, otherwise, keep looking!

Thus for any n,

Now B is on the list of Turing machines, suppose B = TN.If Tn halts on input n, then B does not halt on n, andif Tn does not halt on input n, then B does halt on n.

So Does TN halt on input N?

So there is no algorithm that will decide the Halting problem.If TN halts, then B doesn't halt... ooops B= TN ..If Tn doesn't halt, then B halts... OOOOPs.