Slide 1MenuProof-by-Simulation = Proof-by-ConstructionTM SimulationsSlide 5Can a TM simulate a TM?An Any TM SimulatorSlide 8Universal Turing Machines2-state, 3-symbol Universal TMSlide 11Rough Sketch of ProofEnumerating Turing MachinesAcceptance ProblemAcceptance LanguageTuring-RecognizableRecognizing ATMRecognizability of ATMUndecidability of ATMReaching a ContradictionSlide 21Proving UndecidabilitySlide 23Recall: Turing-RecognizableAn Unrecognizable LanguageChargeDavid Evanshttp://www.cs.virginia.edu/evanscs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 16: Lecture 16: Universality and Universality and UndecidabilityUndecidabilityPS4 is due nowSome people have still not picked up Exam 1! After next week Wednesday, I will start charging “storage fees” for them.2Lecture 16: Undecidability and UniversalityMenu•Simulating Turing Machines •Universal Turing Machines•Undecidability3Lecture 16: Undecidability and UniversalityProof-by-Simulation = Proof-by-ConstructionTo show an A (some class of machines) is as powerful as a B (some class of machines) we need to show thatfor any B, there is some equivalent A. Proof-by-construction: Given any b  B, construct an a  A that recognizes the same language as b.Proof-by-simulation:Show that there is some A that cansimulate any B.Either of these shows: languages that can be recognized by a B  languages that can be recognized by an A4Lecture 16: Undecidability and UniversalityTM SimulationsRegular TM2-tape, 2-head TM“Can be simulated by”“Can be simulated by”3-tape, 3-head TM“Can be simulated by”“Can be simulated by”If there is a path fromM to Regular TMand a path from Regular TM to Mthen M is equivalent to a Regular TM5Lecture 16: Undecidability and UniversalityTM SimulationsRegular TM2-tape, 2-head TM“Can be simulated by”3-tape, 3-head TM2-dimensional TMNondeterministic TM2-DPDA+PS4:36Lecture 16: Undecidability and UniversalityCan a TM simulate a TM?Can one TM simulate every TM?Yes, obviously.7Lecture 16: Undecidability and UniversalityAn Any TM SimulatorInput: < Description of some TM M, w >Output: result of running M on wUniversalTuringMachineMwOutput Tapefor runningTM-Mstarting on tape w8Lecture 16: Undecidability and UniversalityManchester Illuminated Universal Turing Machine, #9 from http://www.verostko.com/manchester/manchester.html9Lecture 16: Undecidability and UniversalityUniversal Turing Machines•People have designed Universal Turing Machines with–4 symbols, 7 states (Marvin Minsky)–4 symbols, 5 states –2 symbols, 22 states–18 symbols, 2 states–2 states, 5 symbols (Stephen Wolfram)•November 2007: 2 state, 3 symbols10Lecture 16: Undecidability and Universality2-state, 3-symbol Universal TMSequence of confgurations11Lecture 16: Undecidability and UniversalityOf course, simplicity is in the eye of the beholder. The 2,3 Turing machine described in the dense new 40-page proof “chews up a lot of tape” to perform even a simple job, Smith says. Programming it to calculate 2 + 2, he notes, would take up more memory than any known computer contains. And image processing? “It probably wouldn't fnish before the end of the universe,” he says.Alex Smith, University of Birmingham12Lecture 16: Undecidability and UniversalityRough Sketch of ProofSystem 0 (the claimed UTM)can simulate System 1 which can simulate System 2 which can simulate System 3 which can simulate System 4 which can simulate System 5 which can simulate any 2-colorcyclic tag system which can simulate any TM.See http://www.wolframscience.com/prizes/tm23/TM23Proof.pdffor the 40-page version with all the details…None of these steps involve universal computation themselves13Lecture 16: Undecidability and UniversalityEnumerating Turing Machines•Now that we’ve decided how to describe Turing Machines, we can number them•TM-5023582376 = balancing parens•TM-57239683 = even number of 1s•TM-3523796834721038296738259873 = Universal TM•TM-3672349872381692309875823987609823712347823 = WindowsXPNot the real numbers – they would be much much much much much bigger!14Lecture 16: Undecidability and UniversalityAcceptance ProblemInput: A Turing Machine M and an input w. Output: Yes/no indicating if M eventually enters qAccept on input w.How can we state this as a language problem?15Lecture 16: Undecidability and UniversalityAcceptance LanguageATM = { <M, w> | M is a TM description and M accepts input w }If we can decide if a string is in ATM, then we cansolve the Acceptance Problem (as defned on the previous slide).Is ATM Turing-recognizable?16Lecture 16: Undecidability and UniversalityTuring-RecognizableA language L is “Turing-recognizable” if there exists a TM M such that for all strings w:–If w  L eventually M enters qaccept –If w  L either M enters qreject or M never terminates… if there exists a TM M such that for all strings w:–If w  L eventually M enters qaccept or M never terminates–If w  L either M enters qreject or M never terminatesIn a previous lecture, I incorrectly defned it as:Why can’t this be the right defnition?17Lecture 16: Undecidability and UniversalityRecognizing ATMRun a UTM on <M, w> to simulate running M on w. If the UTM accepts, <M, w> is in ATM.UniversalTuringMachineMwOutput Tapefor runningTM-Mstarting on tape w18Lecture 16: Undecidability and UniversalityRecognizability of ATMDecidableRecognizableATMIs it inside the Decidable circle?19Lecture 16: Undecidability and UniversalityUndecidability of ATM•Proof-by-contradiction. We will show how to construct a TM for which it is impossible to decide ATM.Defne D (<M>) = Construct a TM that: Outputs the opposite of the result of simulating H on input <M, <M>>Assume there exists some TM H that decides ATM.If M accepts its own description <M>, D(<M>) rejects.If M rejects its own description <M>, D(<M>) accepts.20Lecture 16: Undecidability and UniversalityReaching a ContradictionWhat happens if we run D on its own description, <D>?Defne D (<M>) = Construct a TM that: Outputs the opposite of the result of simulating H on input <M, <M>>Assume there exists some TM H that decides ATM.If M accepts its own description <M>, D(<M>) rejects.If M rejects its own description <M>, D(<M>) accepts.If D accepts its own description <D>, D(<D>) rejects.If D rejects its own description <D>, D(<D>) accepts.substituting D for M…21Lecture 16: