Applications of the Recursion Theorem

Return to List of Lectures

Previous Lecture

• Misc
  • SOFIs
    • Fill out online per email
    • Very helpful to me in shaping course in the future
  • CIT looking for student database programmer for next fall
    • Some experience with databases would be ideal, but will train
    • Contact Paul Jackson (jackson at geneseo.edu) if interested and/or for more information
• Questions?
• Applying the Recursion Theorem
  • Last part of section 6.1
    • Streamlined diagonalization proofs
      • For example, prove that it is undecidable whether running Turing machine M on input w will infect your Turing machine with a virus (or otherwise do something bad to it).
        • Assume H decides whether M run on w does something bad
        • Construct machine P as…
          

          On input w:
              Get own description, ⟨P⟩ via Recursion Theorem
              Run H on ⟨P⟩ and w
              If H rejects, do something bad, if H accepts, reject

    • Whether a Turing machine has the shortest description of all machines that do a certain computation is unrecognizable
      • Assume this set is recognizable; therefore it has an enumerator
        • Enumerator generates all strings in language (in infinite time, but will eventually generate any string in the language)
      • Proof’s machine C uses this enumerator to find a machine D whose description is longer than C’s
      • But then C computes exactly what D does, i.e., C and D are equivalent and C has a shorter description
      • Contradiction to assumption that there is an enumerator for the set of minimal-description Turing machines, i.e., to assumption that set is Turing recognizable
      • How can one machine simulate another?
        • Thanks to the existence of universal Turing machines, i.e., machines that take a description of another machine and a string as input and that carry out that other machine’s transitions when run on that string
        • Fairly easy to imagine what a universal Turing machine algorithm looks like, so by Church-Turing Thesis it also exists as a Turing machine
    • Fixed point theorem: Let t() be any computable function from encodings of Turing machines to encodings of Turing machines. Then there is a string ⟨M⟩ such that t(⟨M⟩) is machine G equivalent to M
      • Proof: consider the following Turing machine, M:
        

        On input x
            Get own description, ⟨M⟩
            Compute t(⟨M⟩), call result ⟨G⟩
            Run G on x

• Next
  • Introduction to Lambda Calculus
  • Read section 1 of Raul Rojas’s “A Tutorial Introduction to the Lambda Calculus” at http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/tutorials/lambda.pdf
    • (Be sure you get version 2 from 2015, not older versions)

Next Lecture