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 recursive if and only if there is an algorithm to compute the function.
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.]
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 Tn 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 n and
(ii) with output 1 if Tn does not halt with input n.
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, and
if Tn does not halt on input n, then B does halt on 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.