Slide 1MenuUndecidability + Rice + Church-TuringProgram Halting ProblemExamplesTougher ExampleSlide 7More Convincing Non-Existence ProofRecall from Lecture 16...Alternate Proof: ReductionDoes this work for Java?Universal Programming LanguageWhich of these are Universal Programming Languages?ProofsWhy is it impossible for a programming language to be both universal and resource-constrained?All universal programming language are equivalent in power: they can all simulate a TM, which can carry out any mechanical algorithm.Why so many programming languages?Proliferation of Universal PLsProgramming Language Design SpaceAre any Important Problems Undecidable?Virus DetectionSlide 22Vulnerability DetectionExample: Morris Internet Worm (1988)Impossibility of Vulnerability Detection“Solving” Undecidable ProblemsActual isVirus ProgramsRecapDavid EvansDavid Evanshttp://www.cs.virginia.edu/evanshttp://www.cs.virginia.edu/evanscs302: Theory of Computationcs302: Theory of ComputationUniversity of VirginiaUniversity of VirginiaComputer ScienceComputer ScienceLecture 18: Lecture 18: Important Undecidable Problems Important Undecidable Problems (and what to do about them)(and what to do about them)2Lecture 18: Important Undecidable ProblemsMenu•What does undecidability mean for problems real people (not just CS theorists) care about?•What do you do when your application’s requirements require “solving” an undecidable problem?3Lecture 18: Important Undecidable ProblemsUndecidability + Rice + Church-TuringUndecidability: undecidable languages that cannot be decided by any Turing MachineRice’s Theorem: all nontrivial properties about the language of a TM are undecidableChurch-Turing Thesis: any mechanical computation can be done by some TMConclusion: any nontrivial property about general mechanical computations cannot be decided!Language and Problems: any problem can be restated are a language recognition problem4Lecture 18: Important Undecidable ProblemsProgram Halting Problem•Input: a program P in some programming language•Output: true if P terminates; false if P runs forever.5Lecture 18: Important Undecidable ProblemsExampleshalts(“2+2”)halts(“def f(n): if n==0: return 1 else: return n * f(n-1) f(10)”)halts(“def f(n): if n==0: return 1 else: return n * f(n-1) f(10.5)”)”)TrueTrueFalse6Lecture 18: Important Undecidable ProblemsTougher Examplehalts(“ def isPerfectNumber(n): # n is perfect if factors sum to ndivs = findDivisors(n)return n == sum(divs) i = 3 while not isPerfectNumber (i): i = i + 2 print i”)Note: it is unknown where an odd perfect number exists. (Numbers up to 10300 have been tried without finding one yet.)Unknown7Lecture 18: Important Undecidable ProblemsIf you had halts, you could prove or disprove nearly every open mathematical problem!–Does an odd perfect number exist?–Reimann hypothesis: The real part of any non-trivial zero of the Riemann zeta function is ½. –Goldbach conjecture: Every number > 2 is the sum of three primes (including 1).–Poincaré conjecture: Every simply connected closed three-manifold is homeomorphic to the three-sphere. –...This suggests it is unlikely halts exists...but doesn’t prove it (yet).8Lecture 18: Important Undecidable ProblemsMore Convincing Non-Existence Proofdef paradox(): if halts(“paradox()”): while True: print “You lose” else: return “You lose”If halts(“paradox()”) is True: paradox() loops foreverIf halts(“paradox()”) is False: paradox() haltsNeither option makes sense, so halts must not exist!9Lecture 18: Important Undecidable ProblemsRecall from Lecture 16...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 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!10Lecture 18: Important Undecidable ProblemsAlternate Proof: Reduction•A Python procedure that solves halts must not exist, since if it did we could:–Write a TM simulator in Python: def simulateTM(M,w): # simulates M on input w–Determine if a TM M halts on w using halts:halts(“simulateTM(M,w)”)•But, we know HALTTM is undecidable. Hence, halts for Python must not exist.11Lecture 18: Important Undecidable ProblemsDoes this work for Java?12Lecture 18: Important Undecidable ProblemsUniversal Programming Language•Definition: a programming language that can describe every algorithm.•Equivalently: a programming language that can simulate every Turing Machine.•Equivalently: a programming language in which you can implement a Universal Turing Machine.13Lecture 18: Important Undecidable ProblemsWhich of these are Universal Programming Languages?PythonJavaC++C#HTMLSQLSchemeRubyCOBOLFortranJavaScriptPostScriptPLANBASICx8614Lecture 18: Important Undecidable ProblemsProofs•BASIC, C, C++, C#, Fortran, Java, JavaScript, PostScript, Python, Ruby, Scheme, etc.:–Proof: implement a TM simulator in the PL•HTML is not universal:–Proof: show some algorithm that cannot be implemented in HTML–Easy choice: an infinite loop•PLAN (Packet Language for Active Networks):–Designed to be non-universal: resource-constrained language15Lecture 18: Important Undecidable ProblemsWhy is it impossible for a programming language to beboth universal and resource-constrained?Resource-constrained means it is possible to determine an upper bound on the resources any program in the language can consume.16Lecture 18: Important Undecidable ProblemsAll universal programming language are equivalent in power: they can all simulate a TM, which can carry out any mechanical algorithm.17Lecture 18: Important Undecidable ProblemsWhy so many programming languages?18Lecture 18: Important Undecidable ProblemsProliferation of Universal PLs•“Aesthetics”–Some people like :=, others prefer =.–Some people think whitespace shouldn’t matter (e.g., Java), others think programs should be formatted like they mean (e.g., Python)–Some people like goto, others like throw.•Expressiveness vs. “Truthiness”–How much you can say with a little code vs. how likely it is your code means what you think it does19Lecture 18: Important Undecidable ProblemsProgramming Language Design SpaceExpressiveness“Truthiness”SchemePythonJavaC++ClowhighSpec#Adastrict typing,staticBASICmore mistake