|
|
|
| Authored by: PolR on Tuesday, June 12 2012 @ 10:55 PM EDT |
In formal proof the Church-Turing thesis is treated as an implicit assumption.
You prove formally something about Turing-computability or some equivalent
notion and then you extrapolate that it applies to everything that is
intuitively computable on the basis of the thesis. If the thesis is falsified,
the theorem still holds but with the limited scope of Turing-compatibility
because this part is mathematically rigorous. Only the extrapolation would be
invalidated.
Some mathematical propositions are undecidable in the sense you can prove they
are true and you can't prove they are false. There is theorem that shows that
either way a contradiction would immediately ensue. The only salvation is when
you can't decide. The famous Gödel incompleteness theorems are results of this
nature. This assumes consistency. If the system of mathematics is not consistent
then you can prove everything and its contrary. Then the whole system vanishes
into meaninglessness. Some systems of mathematics have had to be discarded
because they have been found to be inconsistent.
Some mathematical problems are undecidable in the sense that there is no
algorithm for solving them in all cases. There is a theorem showing that as soon
as such an algorithm is found a contradiction will ensue. It may be possible to
find partial solutions that work for some special cases though. The halting
problem is an example of a problem of this type.
[ Reply to This | Parent | # ]
|
|
|
|
|
