Church-Turing thesis

From RB Wiki

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.