Notes on Turing Machines and an Unsolvable Problem.
Math 446 M. Flashman 5-8-02
[Based on A.G Hamilton's Logic for Mathematicians, Revised edition.]
Introduction:
  • Example 7.17 from Hamilton in part.
  • Turing Machine: Stanford Encyclopedia of Philosophy
  • Turing Machines - AMS link
  • Virtual Turing Machine

    •  

     

    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.]


    Universal Turing machine "paradox":
    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 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

    (i) with output 0 if Tn halts with input n and
    (ii) with output 1 if Tn does not halt with input n.
    Here's a new Turing machine  B:
    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,

    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.
    Now B is on the list of Turing machines, suppose B = TN.
    So Does TN halt on input N?
     
    If  TN halts, then B doesn't halt... ooops B= TN ..
    If Tn doesn't halt, then B halts... OOOOPs.
    So there is no algorithm that will decide the Halting problem.