- #1
yuiop
- 3,962
- 20
Hi,
I came across this article on Godel's incompletess theorem that seems to relate to number theory so I hope this is the right place to post this question.
This paragraph is from http://www.miskatonic.org/godel.html
=================================================================
In The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:
Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
Now Gödel laughs his high laugh and asks UTM whether G is true or not.
If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
"I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
Think about it - it grows on you ...
With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...
Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.
=================================================================
Now as I see it the sentence:
"The machine constructed on the basis of the program P(UTM) will never say that this sentence is true."
can be replaced with:
"The machine constructed on the basis of the program P(UTM) will never say that G is true."
since G = "this sentence". That means the sentence can further be restated as:
"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true."
and then as :
"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true.") is true."
Clearly the statement G is recursive and would take an infinite amount of time to even ask the full question in its full form. Is this not asking the UTM to give a true or false answer to a question that has no finite form?
I came across this article on Godel's incompletess theorem that seems to relate to number theory so I hope this is the right place to post this question.
This paragraph is from http://www.miskatonic.org/godel.html
=================================================================
In The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:
Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
Now Gödel laughs his high laugh and asks UTM whether G is true or not.
If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
"I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
Think about it - it grows on you ...
With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...
Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.
=================================================================
Now as I see it the sentence:
"The machine constructed on the basis of the program P(UTM) will never say that this sentence is true."
can be replaced with:
"The machine constructed on the basis of the program P(UTM) will never say that G is true."
since G = "this sentence". That means the sentence can further be restated as:
"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true."
and then as :
"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true.") is true."
Clearly the statement G is recursive and would take an infinite amount of time to even ask the full question in its full form. Is this not asking the UTM to give a true or false answer to a question that has no finite form?