What computers just cannot do.(Part II)COS 116: 3/5/2008Sanjeev AroraAdministriviaMidterm - in-class 3/13Review session Tues and Wed during lab slot.2006 midterm linked under “extras” on webRecap from last timeTuring-Post computational model:Greatly simplified modelInfinite tape, each cell contains 0/1Program = finite sequence of instructions (only 6 types!)Unlike pseudocode, no conditionals or loops, only “GOTO”code(P) = binary representation of program PExample: doubling program1. PRINT 0 2. GO LEFT 3. GO TO STEP 2 IF 1 SCANNED 4. PRINT 1 5. GO RIGHT 6. GO TO STEP 5 IF 1 SCANNED 7. PRINT 1 8. GO RIGHT 9. GO TO STEP 1 IF 1 SCANNED 10. STOP Program halts on this input data if STOP is executed in a finite number of stepsSome factsFact 1: Every pseudocode program can be written as a T-P program, and vice versaFact 2: There is a universal T-P program U1 1 0 0 1 0 1 1 0 1 1 1 0 0……code(P)VU simulates P’s computation on VIs there a universal pseudocode program ? How would you write it?What are some examples of universal programs in real life?Discussion TimeHalting ProblemDecide whether P halts on V or notCannot be solved! Turing proved that no Turing-Post program can solve Halting Problemfor all inputs (code(P), V).1 1 0 0 1 0 1 1 0 1 1 1 0 0……code(P)VMakes precise something quite intuitive: “Impossible to demonstrate a negative” Suppose program P halts on input V. How can wedetect this in finite time? “Just simulate.”Intuitive difficulty: If P does not actually halt, no obvious wayto detect this after just a finite amount of time.Turing’s proof makes this intuition concrete.Ingredients of the proof…..Fundamental assumption:A mathematical statement is either true or false “When something’s not right, it’s wrong.”Bob DylanIngredient 1: “Proof by contradiction”Aside: Epimenides ParadoxΚρῆτες ἀεί ψεύσται “Cretans, always liars!”But Epimenides was a Cretan!’(can be resolved…)More troubling: “This sentence is false.”Ingredient 2:Discussion TimeSuppose you are given some T-P program PHow would you turn P into a T-P program that does NOT halt on all inputs that P haltson?Finally, the proof…Suppose program Hsolves Halting Problemon ALL inputs of the formcode(P), V.HConsider program D•On input V, check if it iscode of a T-P program.•If no, HALT immediately.•If yes, use doubling program to create the bit string V, V and simulateH on it.•If H says “Doesn’t Halt”,HALT immediately.•If H says “Halts”, go intoinfinite loopGotcha! Does D halt on the input code(D)?If H halts on every input, so does DLessons to take awayComputation is a very simple process ( can arise in unexpected places)Universal ProgramNo real boundary between hardware, software, and dataNo program that decides whether or not mathematical statements are theorems. Many tasks are uncomputable; e.g. “If we start Game oflife in this configuration, will cell (100, 100) ever havea critter?”Age-old mystery: Self-reproduction.How does the seed encode the whole?Self-ReproductionFallacious argument for impossibility:BlueprintBlueprintBlueprintM.C. EscherPrint GalleryFallacy Resolved: “Blueprint” can involve some computation; need not be an exact copy! Print this sentence twice, the second time in quotes. “Print this sentence twice, the second time in quotes.”High-level description of program that self-reproducesPrint 0Print 1...Print 0. . . . . . . . . . . .. . . . . .. . . . . .}Prints binary code of B}Takes binary string on tape, and in its place prints (in English) the sequence of statements that produce it, followed by the translation of the binary string into English.ABFact: for every program P, there exists a program P’ that has the exact same functionality except at the end it also prints code(P’) on the tapeSelf-reproducing programsMyDoomCrash user’s computer!Reproduce program send to someone
View Full Document
Unlocking...