Midterm - in-class 3/10 Midterm - in-class 3/10 - Review session Wed during lab slot.
- Past midterm available on website for self-study.
Turing-Post computational model: - Greatly simplified model
- Infinite tape, each cell contains 0/1
- Program = finite sequence of instructions (only 6 types!)
- Unlike pseudocode, no conditionals or loops, only “GOTO”
- code(P) = binary representation of program P
Fact 1: Every pseudocode program can be written as a T-P program, and vice versa Fact 2: There is a universal T-P program
Decide whether P halts on V or not Cannot be solved! Turing proved that no Turing-Post program can solve Halting Problem for all inputs (code(P), V).
Κρῆτες ἀεί ψεύσται Κρῆτες ἀεί ψεύσται “Cretans, always liars!” But Epimenides was a Cretan!’ More troubling: “This sentence is false.”
Computation is a very simple process; 6 simple types of operations! ( Later: can arise in unexpected places) Computation is a very simple process; 6 simple types of operations! ( Later: can arise in unexpected places) Universal Program No real boundary between hardware, software, and data. (basis of much of modern computer technology, eg JAVA) No program that decides whether or not mathematical statements are theorems. Many tasks are uncomputable; e.g. “If we start Game of life in this configuration, will cell (100, 100) ever have a critter?”
Fallacious argument for impossibility: Fallacious argument for impossibility:
Print this sentence twice, the second time in quotes. “Print this sentence twice, the second time in quotes.” Print this sentence twice, the second time in quotes. “Print this sentence twice, the second time in quotes.”
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 tape
Dostları ilə paylaş: |