Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 6615-251Great Theoretical Ideas in Computer ScienceaboutAWESOMESomeGeneratingFunctionsProbabilityInfinityComputabilityWith Alan! (not Turing)Mind-blowingWhat 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 ComputationAnything 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 generalThe HELLO assignmentWrite 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 ScriptHow exactly might such a script work?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.What does this do?_(__,___,____){___/__<=1?_(__,___+1,____):!(___%__)?_(__,___+1,0):___%__==___/ __&&!____?(printf("%d\t",___/__),_(__,___+1,0)):___%__>1&&___%__<___/__?_(__,1+ ___,____+!(___/__%(___%__))):___<__*__?_(__,___+1,____):0;}main(){_(100,0,0);}Nasty Programn:=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 theRiemann 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:The “grading function” we just describedis not computable! (We’ll see a proof soon.)Are all reals describable?Are all reals computable?NONOWe saw that computable ⇒ describablebut do we also have describable ⇒ computable?This lecture will hopefully shed light on whatis 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 createusing Turing Machines! Arithmetic operations Conditionals (if) Loops (while, for, do) Arrays, pointers Functions Integers, stringsSome examples: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 ProgramProgram Turing MachineSource code⇔Description of statesand transitionsPrint statement⇔Write to a special “output” area of the tapeReturn true/false⇔Accept/RejectAll of the proofs in this lecture will be about programs. We are still being rigorous because of this equivalence.Computable FunctionHence: countably many computable functions!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).There are only countably many programs. Hence, there are only countably many computable functions.Uncountably Many FunctionsThe functions f: Σ*→ {0,1} are in 1-1 onto correspondence with the subsets of Σ* (the powerset of Σ* ).Subset S of Σ* ⇔ Function fSx in S ⇔ fS(x) = 1x not in S ⇔ fS(x) = 0Hence, the set of all f:Σ* → {0,1} has the same size as the power set of Σ*, which is uncountable.Countably many computable functions.Uncountably manyfunctions from Σ* to {0,1}.Thus, most functions from Σ* to {0,1} are not computable.Decidable/Undecidable SetsA set (more precisely, a language) L ⊆Σ* issaid to be decidable (or recursive) if thereexists a program P such that:P(x) = yes, if x ∈LP(x) = no, if x ∉LNotice that this is the Turing Machineequivalent of a regular language.The theory becomes nicer if we restrict“computation” to the task of decidingmembership 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 ProblemNotation And ConventionsWhen 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 xThe 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 KDefinition:K is the set of all programs P such that P(P) halts.K = { Program P | P(P) halts }The Halting ProblemIs the Halting Set K decidable? In other words, is there a program HALT such that:HALT(P) = yes, if P(P) haltsHALT(P) = no, if P(P) does not haltTHEOREM: There is no program to solve the halting problem(Alan Turing 1937)Suppose a program HALT existed that solved the halting problem.HALT(P) = yes, if P(P) haltsHALT(P) = no, if P(P) does not haltWe will call HALT as a subroutine in a new program called CONFUSE.CONFUSEDoes CONFUSE(CONFUSE) halt?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}CONFUSECONFUSE(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 CONFUSESuppose CONFUSE(CONFUSE) does not haltthen
View Full Document
Unlocking...