## 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ş:** |