|
|
|
| Authored by: PolR on Tuesday, June 12 2012 @ 10:28 PM EDT |
It is neither an axiom, nor a definition, nor a theorem. It is a thesis.
The Church Turing thesis is a statement which can't be stated in precise
mathematical notation because it equates an imprecise philosophical notion, the
intuitive concept of "computable", with a mathematically precise
notion, the concept of Turing machine. Because the thesis involves a
philosophical notion, it is not amenable to rigorous mathematical proof. This is
why it is called a thesis and not a theorem. However the Church-Turing thesis is
falsifiable. If one is to discover a model of computation which corresponds to
the intuitive philosophical notion and is not Turing-equivalent, then the thesis
would be falsified.
The Church-Turing thesis has a unique status in mathematics because it is one
of the rare mathematical principles whose evidence is empirical, like a law of
nature. Mathematicians have repeatedly attempted to falsify it and have failed.
This is our evidence. However the thesis must be (and is) constantly verified.
Whenever someone discovers a new model of computation the question of its Turing
computability arises. Then mathematicians will find a theorem solving this
question and publish it.
The Turing computability of software is proven. The model of computation
corresponding to a CPU is known as a Random-Access Stored Program, or RASP. It
has been defined with mathematical precision and its Turing equivalence is a
proven theorem. Falsifying the Church-Turing thesis requires finding a model of
computation the current crop of computers can't replicate. This would be a major
discovery.
[ Reply to This | Parent | # ]
|
| |
| Authored by: Anonymous on Tuesday, June 12 2012 @ 10:32 PM EDT |
If you are correct, then it is a theory (thesis, synthesis of hypotheses,
etc.).
It's definitely not an axiom, although I believe it is often taken as axiomatic
in informal proofs.
As I understand it, though, some things are provably unprovable (or at least
indeterminable - eg the halting problem) - but that could just be my poor
understanding of incompleteness showing.[ Reply to This | Parent | # ]
|
|
|
|
|
