Introduction to the Recursion Theorem

Return to List of Lectures

Previous Lecture

• Misc
  • GREAT Day
    • (Day of student research talks, art exhibits/performances, etc.)
    • Tuesday, April 19
    • No class(es)
    • Extra credit (up to 2 problem set points per summary) for math session summaries
      • 1 paragraph to 1 page discussing whatever connects the presentations in a session
      • Max 3 sessions per person
• Questions?
• Problem Set re Computation Histories
  • Online now
  • Handout Monday
• The Recursion Theorem
  • Section 6.1 through “Self-Reference”
    • “Computable function?” Function f(x) is computable iff there exists Turing machine M that halts with ⟨f(x)⟩ as only thing on tape whenever started with ⟨x⟩ on tape
    • Parts A and B of SELF
      • Heart of the proof proves these machines can exist
      • Rely on each other to complete descriptions
    • Proves self-reference: machine can output own description
    • Trace of SELF running on page 248
    • Definition of recursion theorem
      • Any computation of function f by a Turing machine can be modified into a computation that computes f with a description of the Turing machine doing so as an additional input
    • Diagram of R (fig 6.4)?
      • Shows flow of transitions between states composing different parts of machine
      • Exactly what the parts are gets back to SELF and its parts
  • What does SELF Turing machine really look like?
    • SELF = AB
    • A, B, defined by/use q()
    • q(w) = Turing machine that writes w to tape
    • q isn’t hard to write in real programming languages, e.g., Matlab:
      

      function [ f ] = q( w )
      %Q Given string w, return a description of a function that returns w
      wQuote = strrep( w, '''', '''''' );
      f = [ 'function w = returnString(); w = ''', wQuote, '''; end' ];
      end

    • And in fact writing programs that print/return their own code is a popular recreation for lots of real languages. They’re called “quines” and you can find a collection at http://www.nyx.net/~gthompso/quine.htm
• Next
  • Finish Recursion Theorem

Next Lecture