Difference between revisions of "Church-Turing thesis"
(Created page with "The Church-Turing thesis claims that the universal Turing machine is the most general form of computation. == The different versions of the thesis == There are several sligh...") |
m |
||
| Line 1: | Line 1: | ||
| − | The Church-Turing thesis claims that the universal Turing machine is the most general form of computation. | + | The Church-Turing thesis claims that the universal Turing machine is the most general form of computation [https://www.youtube.com/watch?v=PLVCscCY4xI UpAndAtom20]. |
== The different versions of the thesis == | == The different versions of the thesis == | ||
Latest revision as of 17:03, 4 February 2020
The Church-Turing thesis claims that the universal Turing machine is the most general form of computation UpAndAtom20.
The different versions of the thesis
There are several slightly distinct versions of this thesis.
Perhaps the most important one is to claim that it is the most general form of computation of any machine that can be built in our universe. In particular, this would mean that the halting problem cannot be solved in our space-time.
The computational complexity Church-Turing thesis is widely believed to be wrong, because of quantum mechanics. But it can be upgraded to a quantum complexity Church-Turing thesis.
Justifications from physics
Gandy theorem.
Bekenstein bound.
Lloyd02 estimate computational capacity measures of the universe.
Implications
It's all about information and information processing!
No "fundamental law" of physics. Any universal Turing machine is.
Nothing special about intelligence.
Computational moral philosophy.
