What computers just cannot doCOS 1163/7/2006Instructor: Sanjeev AroraEpimenides Paradox! Κρτες ε ψεσται! “Cretians, always liars!”! But Epimenides was a Cretian!’(can be resolved…)! More troubling: “This sentence is false.”Recap from last time! Turing-Post computational model:" Greatly simplified model" Infinite tape, each square either 0/1" Program = finite sequence of instructions (only 6 types!)" Unlike pseudocode, no conditionals or loops, only “GOTO”" code(P) = binary representation of program PMotivationSimplify!(Get to the heart of the matter)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. STOPHalting1. 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. STOPProgramProgram halts on this input data if STOP is executed in a finite number of stepsSome facts! Fact 1: Every pseudocode program can be written as a T-P program, and vice versa! Fact 2: There is a universal T-P programU11 0 0 1 0 1 1 0 1 1 1 00……code(P)VU simulates P’s computation on VDiscussionIs there a universal pseudocode program ?How would you write it?Composing programs P1, P2Desired: A T-P program that, on input V:" First runs P1on V" If the previous step halts, runs P2on thenew tape contentsIdeas??Halting Problem! Decide whether P halts on V or not! Cannot be solved! Turing proved that no Turing-Post program can solve the Halting Problem1 1 0 0 1 0 1 1 0 1 1 1 00……code(P)VProof (by contradiction)! Suppose H is a Turing-Post program solving the Halting problem! Use it to write a new program P0:1. On input V, P0checks if V is the code to a Turing-Post program2. If not, HALT3. Else, use a Doubling Program to get V,V4. Run H on V,V5. If H says “doesn’t halt”, then HALT immediately6. Otherwise, go into an infinite loopProof (cont’d)1. On input V, check if V is the code to a Turing-Post program2. If not, HALT3. Else, use a Doubling Program to get V,V4. Run H on V,V5. If H says “doesn’t halt”, then HALT immediately6. Otherwise, go into an infinite loop! But does P0halt on code(P0)?! If it doesn’t, then at step 5 it should halt! If it does, then it should reach step 6 and go into an infinite loop (i.e. not halt!)P0Lessons to take away! Computation is a very simple process ( can arise in unexpected places)! Universal Program! No real boundary between hardware, software, and data! No program that decides whether or not mathematical statements are theorems.Age-old mystery: Self-reproduction.How does the seed encode the whole?! Fact: 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 else!Discussion next time: How to write a self-reproducing T-P program.Hint: The idea is the following:Write the following twice, the second time in quotes “Write the following twice, the second time in
View Full Document
Unlocking...