- #36
vanesch
Staff Emeritus
Science Advisor
Gold Member
- 5,117
- 20
michinobu said:I don't know if it's mathematically possible. I remember reading in "Introduction to the Theory of Computation" by Michael Sipser, that Kurt Godel, Alan Turing, and Alonzo Church discovered that computers can't solve certain "basic" problems which are solvable to humans - such as being able to prove if a mathematical statement is true or false.
I would like to react to this. It is a common error, and you are in good company: even Penrose fell into that trap.
What Goedel and Co demonstrated is that every system based upon first order formal logic (and so are classical computers: the von Neumann machine is an implementation of a first order formal system) is such that some statements in it are not provable "but are nevertheless true" ; however, this is something you can only derive when you consider that first order formal system in a "larger" system. So if you have a "larger" system and you analyse that given first order system, you will be able to construct a statement expressed in that first order system of which you can demonstrate that no proof exists within that first order system, but of which you've demonstrated nevertheless (in the larger system) the truth.
However, that "larger" system might just as well be a larger first order system, with its OWN unprovable statements, and as long as you dwell within that larger system, you won't be able to find out. You'd need to analyse your larger system in a still larger system before you'd be able to do so.
So it is very well possible that we humans "run a large first order system" with our own unprovable statements in it. It is not because we are able to find such things in smaller systems, that it doesn't mean that we don't have our own "Goedel limit". From within a system, you can never find out.