15 251 MindSome AWESOME blowing Great Theoretical Ideas in Computer Science about Generating Functions Probability Infinity Computability With Alan not Turing What does this do 1 1 1 0 printf d t 1 0 1 1 1 0 main 100 0 0 Turing s Legacy The Limits Of Computation Anything I say say is false This lecture will change the way you think about computer programs Many questions which appear easy at first glance are impossible to solve in general The HELLO assignment Write a Java program to output the words HELLO WORLD on the screen and halt Space and time are not an issue The program is for an ideal computer PASS for any working HELLO program no partial credit Grading Script The grading script G must be able to take any Java program P and grade it G P Pass if P prints only the words HELLO WORLD and halts Fail otherwise How exactly might such a script work What does this do 1 1 1 0 printf d t 1 0 1 1 1 0 main 100 0 0 Nasty Program n 0 while n is not a counter example to the Riemann Hypothesis n print Hello World The nasty program is a PASS if and only if the Riemann Hypothesis is false A TA nightmare Despite the simplicity of the HELLO assignment there is no program to correctly grade it And we will prove this The theory of what can and can t be computed by an ideal computer is called Computability Theory or Recursion Theory From the last lecture Are all reals describable NO Are all reals computable NO We saw that computable describable but do we also have describable computable The grading function we just described is not computable We ll see a proof soon This lecture will hopefully shed light on what is and isn t possible using a program But wait Why are we reasoning about programs Don t we need to use Turing Machines to be mathematically precise Not necessarily Remember the Church Turing Thesis any reasonable and sufficiently powerful notion of a program is equivalent to a Turing Machine It s okay to just reason about algorithms What s Allowed in an Algorithm Anything that we can create using Turing Machines Some examples Arrays pointers Functions Integers strings Arithmetic operations Conditionals if Loops while for do As long as we use reasonable primitives like these we are really reasoning about Turing Machines so our statements have a formal backing Extending the Idea of a Program Program Turing Machine Source code Description of states and transitions Print statement Write to a special output area of the tape Return true false Accept Reject All of the proofs in this lecture will be about programs We are still being rigorous because of this equivalence Computable Function Fix a finite set of symbols A function f is computable if there is a program P that when executed on an ideal computer one with infinite memory computes f That is for all strings x in f x P x Hence countably many computable functions There are only countably many programs Hence there are only countably many computable functions Uncountably Many Functions The functions f 0 1 are in 1 1 onto correspondence with the subsets of the powerset of Subset S of Function fS x in S fS x 1 x not in S fS x 0 Hence the set of all f 0 1 has the same size as the power set of which is uncountable Countably many computable functions Uncountably many functions from to 0 1 Thus most functions from to 0 1 are not computable Decidable Undecidable Sets A set more precisely a language L is said to be decidable or recursive if there exists a program P such that P x yes if x L P x no if x L Notice that this is the Turing Machine equivalent of a regular language The theory becomes nicer if we restrict computation to the task of deciding membership in a set Again by giving a counting argument we can say that there must be some undecidable set The set of all languages is uncountable but there can only be countably many decidable languages because there are only countably many programs Can we explicitly describe an undecidable set The Halting Problem Notation And Conventions When we write P by itself we are talking about the text of the source code for P P x means the output that arises from running program P on input x assuming that P eventually halts P x means P did not halt on x The meaning of P P 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 Halting Set K Definition K is the set of all programs P such that P P halts K Program P P P halts The Halting Problem Is the Halting Set K decidable In other words is there a program HALT such that HALT P yes if P P halts HALT P no if P P does not halt THEOREM There is no program to solve the halting problem Alan Turing 1937 Suppose a program HALT existed that solved the halting problem HALT P HALT P 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 CONFUSE CONFUSE P if HALT P then loop forever i e we don t halt else exit i e we halt text of HALT goes here Does CONFUSE CONFUSE halt CONFUSE CONFUSE P if HALT P then loop forever i e we don t halt else exit i e we halt text of HALT goes here Suppose CONFUSE CONFUSE halts then HALT CONFUSE TRUE so CONFUSE will loop forever on input CONFUSE Suppose CONFUSE CONFUSE does not halt then HALT CONFUSE FALSE so CONFUSE will halt on input CONFUSE CONTRADICTION Alan Turing 1912 1954 Theorem 1937 There is no program to solve the halting problem Turing s argument is essentially the reincarnation of Cantor s Diagonalization argument that we saw in the previous lecture All Programs the input All Programs P0 P1 P2 Pj P0 P1 Pi Programs computable functions are countable so we can put them in a countably long list All Programs the input All Programs P0 P1 P2 Pj P0 P1 Pi YES if Pi Pj halts No otherwise All Programs the input All Programs P0 P0 P1 Pi P1 P2 Pj Let di HALT Pi d0 d1 di CONFUSE Pi halts iff di no The CONFUSE function is the negation of the diagonal Hence CONFUSE cannot be on this list Is there a real number that can be described but not computed Consider the real number R whose binary expansion has a 1 in the jth position iff the jth program halts on input itself Proof that R cannot be computed Suppose it is and program FRED computes it then consider the following program MYSTERY program text P for j 0 to forever do if P Pj then use …
View Full Document
Unlocking...