Outline

• Impossible Programs
• The Halting Problem

• TMs are functions which turn input strings into output strings.

• Does every function {input strings} --> {output strings} correspond to a TM?

• The setup:
  • Encode binary input/output strings (see p 277) as integers:

    s1 = b; s2 = 0; s3 = 1; s4 = 00; s5 = 01; s6 = 10; s7 = 11; s8 = 000; ...
    

    binary string w corresponds to sn where n = 2length(w) + makeDecimal(w)

  • Encode TMs as integers (TM serial number---see pp 274-275; different TMs have different serial numbers, though not every integer is a serial number). Serial numbers are computed from TM binary encodings:

    111 <1st move code> 11 <2nd move code> 11 .. 11  111 
    

    where a "move code" for (present state, present symbol, write symbol, move newstate) = (pst, psm, w, m, nst) has the form

    [pst 0's] 1 [psm-code] 1 [w-code] 1 [m-code] 1 [nst 0's] 1
    

    symbol codes: 0 == 0; 1 == 00; b = 000; move-code: left == 0; right == 00 (Example: see figure 7.5, p 276)
    TM-serial-number = makeDecimal(TM-binary-encoding)

  • We can now "list" the Turing Machines, TM1, TM2, TM3, ..., where TM1 is the TM with smallest serial number, TM2 has 2nd smallest serial number, etc. Every Turing Machine is somewhere on this (infinite) list!

• Back to the question: is every function {input strings} --> {output strings} "computable"?
  • Consider the function P: {input strings} --> {output strings} defined by

    P(sn) = 0              if TMn(sn) has no output; 
    P(sn) = empty-string   if TMn(sn) has some output 
    

  • Consider the table with rows labelled by input strings and columns labelled by TMs. A (string,TM) entry in this table is TM(string). (Draw the table; check the diagonal!)

           TM1       TM2       TM3       TM4       TM5       TM6    ...
    s1  *TM1(s1)*  TM2(s1)   TM3(s1)   TM4(s1)   TM5(s1)   TM6(s1)	...
    s2   TM1(s2)  *TM2(s2)*  TM3(s2)   TM4(s2)   TM5(s2)   TM6(s2)	...
    s3   TM1(s3)   TM2(s3)  *TM3(s3)*  TM4(s3)   TM5(s3)   TM6(s3)	...
    s4   TM1(s4)   TM2(s4)   TM3(s4)  *TM4(s4)*  TM5(s4)   TM6(s4)	...
    s5   TM1(s5)   TM2(s5)   TM3(s5)   TM4(s5)  *TM5(s5)*  TM6(s5)	...
    s6   TM1(s6)   TM2(s6)   TM3(s6)   TM4(s6)   TM5(s6)  *TM6(s6)*	...
    

    P can't be TM1 since P(s1) differs from TM1(s1); P can't be TM2 since P(s2) differs from TM1(s2); P can't be TM3 since P(s3) differs from TM1(s3); P can't be TM4 since P(s4) differs from TM1(s4); ...; P can't be any of {TM1, TM2, TM3, ...}, so no Turing Machine can compute P. That is, program P is not computable!

• Problem: write a program H whose input is (M, s), where M is a TM (encoding thereof) and s is a binary string such that
  • if M(s) "halts" then H(M,s) = "yes"
  • if M(s) "hangs" then H(M,s) = "no"

• Is the Problem doable? I.e., is there a TM which computes H?
  • Suppose the answer is YES. Then we can define another TM, superH by
    • if H(x, x) = "yes" then superH(x) hangs (enter an "infinite loop")
    • if H(x, x) = "no" then superH(x) halts

    where x is a binary string.

  • Now, suppose x is superH, an encoding of superH :

    What does superH(superH, superH) do?

    This question poses a paradox whose resolution is that there cannot be a Turing Machine which computes H.

Click here to visit the CS10.1 web site.

Click here to visit the CS10.2 web site.