Church-Turing Thesis

Creator
Created
Created
2019 Nov 5 5:18
Editor
Edited
Edited
2023 Dec 19 3:35
Refs
Refs

There is no formal answer

There is no known model of computation more powerful than Turing Machines
anything solvable via mechanical procedure can be done on a Turing machine - not mathmatical statement to prove
Evidence: Most extensions to the TM model like multi-tape, non-determinism, multi-dimension, etc can be simulated on a TM. In addition, λ-calculus, random access machines, general recursive functions, general grammars, π-calculus, first order reasoning, ... are all equivalent to TMs
모든 기계에서 수행되는 연산은 튜링기계에서 수행 가능. 명제인 이유는 완전하지 않기 때문. 아직까지 틀림 증명 안댐
 
 
 
 
 

Recommendations