Lecture 26 November 28 2006 Fall 2006 Carnegie Mellon University CS 15 251 says is false Anything Turing s Legacy The Limits Of Computation John Lafferty Great Theoretical Ideas In Computer Science PASS for any working HELLO program no partial credit Space and time are not an issue The program is for an ideal computer Write a JAVA program to output the word HELLO on the screen and halt The HELLO assignment How exactly might such a script work Pass if P prints only the word G P HELLO and halts Fail otherwise The grading script G must be able to take any Java program P and grade it Grading Script include stdio h main t a char a return 0 t t 3 main 79 13 a main 87 1 main 86 0 a 1 a 1 t main t 1 a 3 main 94 27 t a t 2 13 main 2 1 s d d n 9 16 t 0 t 72 main t n w w cdnr r de w w q n l n n n q n k r d 3 w K w K e dq l q d K k q r eKK w r eKK nl q n w nl n d rw i nl n n r w r nc nl l K rw iK nl w q n wk nw iwk KK nl w l w i nl q ld r nlwb de c nl rw nc nw kd e rdq w nr rl n t 50 a putchar 31 a main 65 a 1 main a t a 1 0 t main 2 2 s a main 0 main 61 a ek dc i bK q w n r3 l nuwloca O m vpbks fxntdCeghiry a 1 What does this do What kind of program could a student who hated his her TA hand in The nasty program is a PASS if and only if the Riemann Hypothesis is false n 0 while n is not a counter example to the Riemann Hypothesis n print Hello Nasty Program And we will prove this Despite the simplicity of the HELLO assignment there is no program to correctly grade it The theory of what can and can t be computed by an ideal computer is called Computability Theory or Recursion Theory The grading function we just described is not computable We ll see a proof soon We saw that computable describable but do we also have describable computable Are all reals describable NO Are all reals computable NO From Lecture 25 Whenever you run out of memory the computer contacts the factory A maintenance person is flown by helicopter and attaches 100 Gig of RAM and all programs resume their computations as if they had never been interrupted Aristotelian Version One memory location for each natural number 0 1 2 Platonic Version Infinite RAM Model A function f is computable if there is a program P that when executed on an ideal computer computes f That is for all strings x in f x P x A program is any finite string of characters that is syntactically valid Fix any finite set of symbols Fix any precise programming language e g Java Computable Function Hence countably many computable functions A function f is computable if there is a program P that when executed on an ideal computer computes f That is for all strings x in f x P x A program is any finite string of characters that is syntactically valid Fix any finite set of symbols Fix any precise programming language e g Java Computable Function Hence there are only countably many computable functions There are only countably many Java programs Subset S of x in S x not in S fS x 1 fS x 0 Function fS The functions f 0 1 are in 1 1 onto correspondence with the subsets of the powerset of Uncountably many functions And since is countably infinite its power set is uncountably infinite Hence the set of all f 0 1 has the same size as the power set of The functions f 0 1 are in 1 1 onto correspondence with the subsets of the powerset of Uncountably many functions Thus most functions from to 0 1 are not computable Uncountably many functions from to 0 1 Countably many computable functions Can we describe an interesting uncomputable function Can we explicitly describe an uncomputable function P x means P did not halt on x P x means the output that arises from running program P on input x assuming that P eventually halts When we write program P we are talking about the text of the source code for P Fix a single programming language Java Notation And Conventions It follows from our conventions that P P means the output obtained when we run P on the text of its own source code The meaning of P P P P So that s what I look like K Java P P P halts Definition K is the set of all programs P such that P P halts The Halting Set K HALT P HALT P yes if P P halts no if P P does not halt Is there a program HALT such that The Halting Problem yes if P K no if P K HALT decides whether or not any given program is in K HALT P HALT P Is there a program HALT such that The Halting Problem K P P P halts yes if P P halts no if P P does not halt We will call HALT as a subroutine in a new program called CONFUSE HALT P HALT P Suppose a program HALT existed that solved the halting problem THEOREM There is no program to solve the halting problem Alan Turing 1937 i e we dont halt i e we halt Does CONFUSE CONFUSE halt CONFUSE P if HALT P then loop forever else exit text of HALT goes here CONFUSE i e we dont halt i e we halt Suppose CONFUSE CONFUSE does not halt CONTRADICTION then HALT CONFUSE FALSE CONFUSE will halt on input CONFUSE Suppose CONFUSE CONFUSE halts then HALT CONFUSE TRUE CONFUSE will loop forever on input CONFUSE CONFUSE P if HALT P then loop forever else exit text of HALT goes here CONFUSE There is no program to solve the halting problem Theorem 1937 Alan Turing 1912 1954 Turing s argument is essentially the reincarnation of Cantor s Diagonalization argument that we saw in the previous lecture Pi P1 P0 P0 P1 P2 Pj All Programs the input Programs computable functions are countable so we can put them in a countably long list All Programs All Programs Pi P1 P0 P0 P1 P2 YES if Pi Pj halts No otherwise Pj All Programs the input Pi P1 P0 d0 P0 d1 P1 P2 di Pj All Programs the input Let di HALT Pi Hence CONFUSE cannot be on this list CONFUSE Pi halts iff di no The CONFUSE function is the negation of the diagonal All Programs There is no program to solve the halting problem Theorem 1937 Alan …
View Full Document
Unlocking...