
TuringPost computational model

tarix  25.11.2017  ölçüsü  479 b.   #12425 

TuringPost 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 TP program, and vice versa Fact 2: There exists a universal TP program
Decide whether P halts on V or not Cannot be solved! Turing proved that no TuringPost 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.”
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ş: 

