Talk:Gödel's incompleteness theorems

Please place discussions on the underlying mathematical issues on the Arguments page. Non-editorial comments on this talk page may be removed by other editors.

Expert Needed To Clean This Article!!

I attempted to fix the inaccuracies and vagueness of just the introduction but someone switched it back. But the article as a whole is just a giant, disorganized mess and is filled with much nonsense. There are lots of people out there with expertise in this area. But this topic also attracts lots of people who have no idea what they're talking about. Can an expert please step forward?? And then lock it!!! — Preceding unsigned comment added by 98.224.222.241 (talk) 22:53, 30 August 2011 (UTC)

What are you talking about? The only one who has recently reverted one of your edits is you.

I looked over your edits and at a quick glance had no objection to them and thought they were even a modest improvement, so I left them in place. I didn't consider them large enough changes to get that worked up about in either direction, though (arithmetic is a more precise word than mathematics, but from my POV mathematics that can't even do arithmetic isn't very much mathematics, so to me this is not a huge change). --Trovatore (talk) 23:03, 30 August 2011 (UTC)

Without any hocus-pocus

So, after having read the page let me see if I got it straight. Without any hocus-pocus, the Godel sentence is in essence no more than a formal statement about natural numbers. Is this correct? Southttext (talk) 04:45, 30 October 2011 (UTC)

That's what it is, in fact. The essence is something else again. — Arthur Rubin (talk) 07:41, 30 October 2011 (UTC)

Thanks, in fact sounds indeed better. And 'true' as in 'true but unprovable' is as much as, and no more than, that the arithmetical fact 1+1=2 is 'true'? Southttext (talk) 12:32, 30 October 2011 (UTC)

Pretty much. The only difference is that the incompleteness theorem looks at a sequence of equations of the form F(n) = 0, where F is a particular concrete function from the natural numbers to the natural numbers, and n ranges over the natural numbers. The incompletness theorem shows that if the theory of arithmetic at hand is consistent then each of these equations is true (in the same sense as the equation "1+1=2"), but the single sentence "For every n, F(n) = 0" cannot be proved in the theory of arithmetic at hand. — Carl (CBM · talk) 20:02, 30 October 2011 (UTC)

Polynomial

My first impression is that this edit is overly detailed for this article, and perhaps for Wikipedia in general. What do others think? Possibly something about it could be summarized in a sentence or two. --Trovatore (talk) 01:11, 9 December 2011 (UTC)

Yah, you think! I couldn't believe my eyes . . . no explanation at all, 36+/- symbols on the first line alone (one of which has an exponent to the 5^60)^2, let alone 10 more lines of the same yielding about 350-400 symbols in a string that ends in =0 [about 3000 bits of ASCII code]. If the intent is to be ironic, it's out of place. Our ultimate role here, (Bill's version), is to make the hard easy, the complex simple, the inscrutible scrutible. Yes, if someone can gracefully, elegantly show how a Diophantine equation can encode a machine-like process, and from this one can prove incompleteness or undecidability, this would be a worthy endeavor. Bill Wvbailey (talk) 02:45, 9 December 2011 (UTC)

Addendum: This sort of thing should remain in a textbook, or perhaps go into its own sub-article with significant development around it. As I noted above: can we use Diophantine equations to prove incompleteness or undecidability? Chaitin 2005 Metamath! makes a rather noble stab at this cf pages 37-45, and Franzen 2005:70-71 briefly discusses the MRDP theorem. An example of really big numbers in texts: In Penrose's 1989 Emporer's New Mind on pages 71-73 is the complete listing in binary of a universal Turing machine code in 75 +/- lines of 74 +/- 1's and 0's. That's a lot of bits (5500 +/-). On page 56-57 he writes down a number (base 10) that he claims is the "denary" equivalent number of his U. All well and good to provide some literary pungency or a bit of constructive evidence (it's unclear what Penrose's point is otherwise), but Penrose has spent over 20 pages developing the notion of a (Post-)Turing machine and showing one encoding of a U [O.R. alert, he could cut his bit-count in half.] Bill Wvbailey (talk) 16:15, 12 December 2011 (UTC)

I removed the explicit polynomial, and just mentioned that it was given in a paper. VladimirReshetnikov (talk) 19:33, 12 December 2011 (UTC)

2012-1-14

Concerning this edit [1], I agree with David Eppstein's revert:

• The claim about Hilbert's program is in line with NPOV, and there is no problem with using primary sources there. There is a nice summary of the contemporary literature at the article Hilbert's program, and "widely but not universally" is a good NPOV summary of that. I think that removing the "but not universally" might give the false impression that the matter is resolved. For example, we say that the Church-Turing thesis is "widely" accepted in its article.
• I don't see any need for an additional source for the literal statement of the halting problem, in a paragraph that already has several sources where authors use the halting problem. At some point, we have to accept that standard terms like "halting problem", "computable function", "group", etc. do not need an extra source every time they are mentioned, any more than common terms in any other field would.

— Carl (CBM · talk) 20:41, 14 January 2012 (UTC)

I agree with both of the above. Someone already fixed "halting problem". I restored "but not universally" in the lede since I think it's sufficiently discussed and referenced toward the end of the section "Meaning of the first incompleteness theorem". I don't think there's any actual controversy over the statement, so leaving it uncited in the lede seems fine to me. The existing reference "Hilbert's program then and now" (Zach 2006) also discusses the issue. 67.122.210.96 (talk) 19:37, 22 January 2012 (UTC)

Arithmetically Incorrect does not mean Inconsistent

The section on the first theorem says If G were provable under the axioms and rules of inference of T, then G would be false but derivable, and thus the theory T would be inconsistent. This is a bit misleading, since omega inconsistency does not entail inconsistency and I don't see how we can conclude that T would be inconsistent without using the Rosser construction.--141.70.13.41 (talk) 18:41, 21 February 2012 (UTC)