Peter Grogono says:
August 25, 2012 at 3:26 pm
I think it is important to take into account the way in which Godel’s proof actually works. He considers a particular logical system and constructs a special statement that is not provable within that system. His result is important because it is general: a similar proof can be given for any logic that can encode its own formulas (e.g., using arithmetic).
Douglas Hofstadter gives a nice analogy in his book “Godel, Escher, Bach”. One person tries to build a perfect record-player and another person tries to construct disks that it cannot play. (When the book was written, most readers were familiar with such machines.) Give a particular record-player P, for example, you might find frequencies at which it resonates and record exactly those frequencies on a disk, D. When P plays D, it shakes itself to pieces. The point is to distinguish between the claims “this disk cannot be played” and “for each player P of sufficient quality, we can create a disk D that it cannot play”. There is a dependency between D and P.
Here’s my answer as to whether mathematicians (or even ordinary people) have Godelian limitations. Imagine a kind of super MRI machine that can monitor the state of each one of your brain cells and thus allow you to inspect your own brain. There would probably be statements of the form “Cell 12345 is not firing now” which you could see to be true but could not say, because saying them would make them false. This is how Godel’s proof works: it uses the system to operate against itself.
In Computer Science, the “Halting Theorem” is a result similar to Godelian incompleteness. (Many people actually consider HT and GI to be the same.) It says that there is no algorithm (or, equivalently, computer program) that can decide whether a given program terminates (“halts”) in a finite time. Again, it is proved by carefully constructing a program to defeat the algorithm. Here’s an informal description of the proof:
Let H be a program that decides termination. Specifically, H(P) yields “true” if program P halts and “false” otherwise. Now consider this program:
Q = if H(Q) then loop for ever else halt
From this program, and assuming H works as advertised, we conclude that Q terminates if and only if it doesn’t terminate. Since this is a contradiction, we infer that there is no such program H. Once again, the proof depends on a very special program, one designed to defeat the proposed algorithm.
Godel demonstrated the existence of just one unprovable statement for a given system. In fact, there will be many, but the others are harder to find. The work of Chaitin and others suggests that, in some sense, most statements are unprovable. The success of mathematics, however, suggests that there are enough interesting and provable statements to keep us going for a while.
Q: Does Gödel?s Incompleteness Theorem imply that it?s impossible to be logical? | Ask a Mathematician / Ask a Physicist
, sono andato a rileggermi la Wikipedia su Gödel e ho trovato quel paragrafo.
)
)
)!!!
