Turing-Post computational model

• Turing-Post computational model:

• Greatly simplified model
• Infinite tape, each cell contains symbol (0 or 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 exists 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 ( can arise in unexpected places)

• 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.

• Many tasks are uncomputable; e.g. “If we start Game of life in this configuration, will cell (100, 100) ever have a critter?”

False argument for impossibility:

• False 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