Midterm in-class 3/10

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 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!’

• (can be resolved…)

• 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