1David 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 thatrecognizes 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.27Lecture 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 configurations11Lecture 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 finish 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 1which can simulate System 2which can simulate System 3which can simulate System 4which can simulate System 5which can simulate any 2-colorcyclic tag systemwhich 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 themselves313Lecture 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 muchmuch much bigger!14Lecture 16: Undecidability and UniversalityAcceptance ProblemInput: A Turing Machine M and an input w. Output: Yes/no indicating if M eventually enters qAccepton 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 defined on the previous slide).Is ATMTuring-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 qrejector M never terminates… if there exists a TM M such that for all strings w:– If w ∈ L eventually M enters qacceptor M never terminates– If w ∉ L either M enters qrejector M never terminatesIn a previous lecture, I incorrectly defined it as:Why can’t this be the right definition?17Lecture 16: Undecidability and UniversalityRecognizing ATMRun a UTM on <M, w> to simulate running Mon 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?419Lecture 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.Define 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>?Define 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: Undecidability and UniversalityReaching a ContradictionDefine 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 D accepts <D>:H(D, <D>) accepts and D(<D>) rejectsIf D rejects <D>,H(D, <D>) rejects and D(<D>) acceptsWhatever D does, it must do the opposite, so there is a contraction!22Lecture 16: Undecidability and UniversalityProving UndecidabilityDefine D (<M>) = Construct a TM that:Outputs the opposite of the result of simulating