The Recursion Theorem via Programs

Return to List of Lectures

Previous Lecture

• Misc
  • Graduate School Information Session
    • Wednesday (April 20), 2:30 PM, South 336
    • Information about applying to, going to, etc. graduate school in math, math education, or related areas
    • Profs. Haddad, Pawlikowski, current grad-school-bound students, maybe recent alums in grad school
    • For anyone “who might even remotely be considering attending graduate school” in the next 2 years.
• Questions?
• Problem Set re Computation Histories
  • Handout
• The Recursion Theorem
  • Outline
    • Theorem (slightly modified from how it’s stated in Sipser): For every Turing machine T, there is a variant T′ that runs T on a description of T′ (which includes T) along with any other input(s) T needs
      • Thus “A Turing machine can access its own description”
    • Proof hinges on SELF, a Turing machine that writes its own description to tape
    • SELF can easily be modifed to write its own description followed by T’s description
    • Thus T′ = SELF followed by T
  • What does SELF really look like?
    • Write it in Matlab
    • To model Turing machine, use variable “tape” as input and output from each stage
      

      ...
      tape = ...
      ...
      tape = ...
      ...

    • Initial version, assuming external function q to create code to assign a string to tape:
      

      % Part A
      tape = 'tape = [ q(tape), tape ]';
      % Part B
      tape = [ q(tape), tape ]

    • Running this produces…
      

      >> selfClass
      tape =
      tape = 'tape = [ q(tape), tape ]';tape = [ q(tape), tape ]
      >> % This is an accurate enough reproduction that it can be executed too:
      >> eval( tape )
      tape =
      tape = 'tape = [ q(tape), tape ]';tape = [ q(tape), tape ]

    • Turing machines aren’t really able to call external functions such as q from their file system, they embed a Turing machine to compute q. But you can do the same in SELF:
      

      % A MATLAB script that acts as Sipser's "SELF" Turing machine from his
      % proof of the Recursion Theorem. This script generates a string containing
      % its own code (less comments) when run. To closely model a Turing machine,
      % this script places key values in a variable named "tape," as a Turing
      % machine stores information on its tape. Furthermore, this script expands
      % the "q" function inline, since Turing machines, unlike Matlab, don't call
      % external functions.
      
      %% A part. Put the code of part B into the tape variable.
      tape = 'tape = [ ''tape = '''''', strrep( tape, '''''''', '''''''''''' ), '''''';'', tape ]';
      
      %% B part. Retrieve the description of B from the tape variable, use it
      % to generate the code of the A part, then put that followed by the old
      % tape contents (the description of the B part) into the tape variable.
      tape = [ 'tape = ''', strrep( tape, '''', '''''' ), ''';', tape ]

• Next
  • Applications of the Recursion Theorem
  • Read last part of section 6.1, “Terminology for the Recursion Theorem” to end
    • Last 1/3 of page 249 through top 1/3 of 252
  • Time permitting, also an introduction to lambda calculus
    • The “Church” part of “Church-Turing Thesis”

Next Lecture