Church?Turing thesis

In computability theory the Church?Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers.

Philosophical implications

The Church?Turing thesis has some profound implications for the philosophy of mind. There are also some important open questions which cover the relationship between the Church?Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:

Related Topics:
Philosophy of mind - Hypercomputation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• The universe is equivalent to a Turing machine (and thus, computing non-recursive functions is physically impossible). This has been termed the strong Church?Turing thesis and is assumed in digital physics.
• The universe is not a Turing machine (ie, the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
• The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it has been proved that any system built out of qubits is (at best) Turing-complete. John Lucas (and famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is little scientific evidence for this theory.

There are actually many technical possibilities which fall outside or between these three categories, but these should serve to illustrate the concept.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~