# What does the Incompleteness Theorem imply? **URL:** \ **Category:** Great Debates\ **Created:** [April 12, 2003, 1:16am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157 "2003-04-12T01:16:08Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![The\_Great\_Unwashed](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/the_great_unwashed/32/4791_2.png) [@The\_Great\_Unwashed](https://boards.straightdope.com/u/The_Great_Unwashed)\ **Post date:** [April 12, 2003, 3:58pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/21 "2003-04-12T15:58:40Z")
> [@](#): > > \*Originally posted by Sofis \* > \*\*That’s not correct, is it? I was under the impression that whether GIT applies or not is dependant on the _expressive power_ of the system, not the axioms used, the axioms only deciding if the system is incomplete, contradictory, or both. Or did I completely misunderstand that? \*\* I am sure that it is correct – the assertion **0 = 1** yields the trivial arithmetic containing the single element _ **0** _ (or _ **1** _ if you prefer), thus losing the required _expressive power_. ---
**Author:** ![The\_Great\_Unwashed](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/the_great_unwashed/32/4791_2.png) [@The\_Great\_Unwashed](https://boards.straightdope.com/u/The_Great_Unwashed)\ **Post date:** [April 12, 2003, 4:18pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/22 "2003-04-12T16:18:11Z")
> [@](#): > > \*Originally posted by TVAA \* > \*\ ***Ultrafilter** : How can we consider AI without considering systems capable of representing the natural numbers? If the AI couldn’t understand arithmetic _in any form or manifestation_, it would seem rather odd to consider it an intelligence. Pocket calculators would be more sophisticated. > > Regarding voting: It’s not directly related to GIT per se, but there is a proof that any voting system used to indicate rational preferences (“rationality” being a technical term that indicates the preferences meet certain qualifications) between options will always have a set of circumstances where the outcome is counter-intuitive and “wrong”. No “perfect” voting system is possible. > > I’ll see if I can find the article discussing it. \*\* Ha! Beat you to it – I claim my £5. But on your first point, there is no _requirement_ on an AI machine to instantiate a formal arithmetic to “represent the natural numbers”, nor to “understand arithmetic”, in the common-or-garden ways we’d expect from a merely “intelligent” agent. That is, there is no reason to consider that an AI machine would be subject to GIT any more than you or I are (we’re both capable of representing the natural numbers and understanding arithmetic, right?) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 12, 2003, 4:23pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/23 "2003-04-12T16:23:13Z")
GIT talks only about the formal systems that talk about arithmetic. If there’s a connection between those and AI, I’ve never seen it. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 12, 2003, 4:27pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/24 "2003-04-12T16:27:12Z")
All right, I found the [earlier thread](http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=120915&highlight=inconsistent+incomplete). On the bottom of the second page is a sequence of five or six posts stating the theorem and explaining what the conditions mean. The 0 = 1 thing is a bit of an oversimplification. For a consistent theory to have an undecidable sentence by GIT, it’s necessary that you can prove that 0 != 1. If you can do that and you can prove that 0 = 1, you’ve got an inconsistent theory. On the other hand, if you can only prove that 0 = 1, GIT doesn’t apply. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 12, 2003, 4:28pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/25 "2003-04-12T16:28:49Z")
But how can you have an AI without a formal system generating it that’s sufficiently complex to be able to represent the natural numbers? A number of people here are discussing the limitations of systems that have no obvious, direct link to GIT, then saying that GIT has no relationship with those systems. I think this is just a bit premature; we shouldn’t take for granted that the Theorem applies, but shouldn’t be consider a bit more carefully before saying that it doesn’t? For example: does GIT apply to the human brain? Clearly the brain can manufacture models of the world that are inconsistent (although it might be more accurate to say that it can construct multiple models that are mutually inconsistent; I doubt very much that the brain can “run” a model that’s fundamentally inconsistent), but are the workings of the brain itself equivalent to a formal system? ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [April 12, 2003, 4:59pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/26 "2003-04-12T16:59:57Z")
I always thought the Incompleteness Theorem meant that all the elements of a set cannot be expressed and/or defined by a rule or law which is an element of that set…you must go outside the box and use an element of a much larger super-set to define the original set. This leads to the need to define the elements of this superset by an even LARGER super-superset. This means there will always be something new to discover. ---
**Author:** ![Spiritus\_Mundi](https://avatars.discourse-cdn.com/v4/letter/s/c68b51/32.png) [@Spiritus\_Mundi](https://boards.straightdope.com/u/Spiritus_Mundi)\ **Post date:** [April 12, 2003, 7:04pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/27 "2003-04-12T19:04:52Z")
> [@](#): > > I believe this refers to Arrow’s Paradox (AKA Arrow’s Impossibility Theorem) that “demonstrates the impossibility of designing rules for social decision making that obey a number of ‘reasonable’ criteria.” Thanks for the link. I had run across Condorcet’s method before, but hadn’t seen his one. With the caveat that Wikipedia admits to presenting a somewhat simplified version, I can’t say that I think much of it. The assumptions of “reasonable systems” do not strike me as reasonable at all. In particular, when one is arguing that a weighted preference system should be used in evaluating citizen desires, it is not at all reasonalbe to expect that extracting a selected sample of options would preserve the relative positions of preference, sinc ethe act of selecting a sample will almost always distort the weighted preference values that you have built into your choice function. Duh. If it actually matter that one person loves A above all and hates B more than any (as a method of weighted preference describes), then it is not unreasonalbe for that strength of preference to override 2 other people who value B just a hair above A. Frankly, (as Condorcet demonstrated long before Arrow) weighted preference is simply a poor way to evaluate social desires if what you really want to do is preserve pair-waise relative relationships. Of course, even if one likes the “reasonable” systems bounded by Arrow, it does not say anything about voting as a method. Weighted preference among multiple options is hardly teh only way to vote. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 12, 2003, 7:11pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/28 "2003-04-12T19:11:53Z")
> [@](#): > > \*Originally posted by The Great Unwashed \* > \*\*But on your first point, there is no _requirement_ on an AI machine to instantiate a formal arithmetic to “represent the natural numbers”, nor to “understand arithmetic”, in the common-or-garden ways we’d expect from a merely “intelligent” agent. > > That is, there is no reason to consider that an AI machine would be subject to GIT any more than you or I are (we’re both capable of representing the natural numbers and understanding arithmetic, right?) \*\* What makes you think we’re **not**? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 12, 2003, 7:16pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/29 "2003-04-12T19:16:22Z")
I found the article I was looking for. Unfortunately, I only have a MSWord copy, so it’s probably not appropriate to post it here. Still, maybe someone can find it on the Net. It was written by John Barnes to the Science Fiction and Fantasy Writers of America to clarify issues brought up during discussion of the best ways to choose Nebula award winners. It’s titled “A Very Brief and Utterly Incomplete Guide to the Mechanics of Voting Systems”. ---
**Author:** ![Spiritus\_Mundi](https://avatars.discourse-cdn.com/v4/letter/s/c68b51/32.png) [@Spiritus\_Mundi](https://boards.straightdope.com/u/Spiritus_Mundi)\ **Post date:** [April 12, 2003, 7:17pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/30 "2003-04-12T19:17:56Z")
**TVAA** > [@](#): > > How can we consider AI without considering systems capable of representing the natural numbers? If the AI couldn’t understand arithmetic in any form or manifestation, it would seem rather odd to consider it an intelligence. Pocket calculators would be more sophisticated. Why would “axiomatizing arithmetic” be considered a good litmus for AI? You may not like the Turing Test (I have some problems with it myself), but if you want to propose susceptibility to GIT as the necessary and sufficient condition for intelligence then you are going to have to provide a pretty convincing argument. As **TGU** pointed out above, it does not require a formal system capable of axiomatizing arithmetic in order to use teh natural numbers. Your own example of the pocket calculator proves this. Being able to perform calculations is a different thing from meeting the requirements for GIT. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 12, 2003, 7:30pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/31 "2003-04-12T19:30:47Z")
But the calculator _does_ meet the requirements for GIT. It performs arithmetic. While I’m posting, here are some interesting links: [link](http://www-db.stanford.edu/~burback/water_sluice/sluice6.25.97/ws/node14.html) [Informal, but interesting](http://www.myrkul.org/recent/godel.htm) [Much more formalistic](http://www.cs.auckland.ac.nz/CDMTCS/chaitin/georgia.html) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 12, 2003, 9:03pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/32 "2003-04-12T21:03:28Z")
> [@](#): > > \*Originally posted by TVAA \* > \*\*But the calculator _does_ meet the requirements for GIT. It performs arithmetic. > > While I’m posting, here are some interesting links: > [link](http://www-db.stanford.edu/~burback/water_sluice/sluice6.25.97/ws/node14.html) > [Informal, but interesting](http://www.myrkul.org/recent/godel.htm) > [Much more formalistic](http://www.cs.auckland.ac.nz/CDMTCS/chaitin/georgia.html) \*\* Performing arithmetic has **nothing** to do with GIT. We’re talking about _modelling_ arithmetic, which is something completely different. If you don’t know the difference, you need to do more reading. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 12, 2003, 9:07pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/33 "2003-04-12T21:07:27Z")
I checked your links. The first two are oversimplified to the point that I wouldn’t want to rely on them. The third might be good, but it’s kinda tangential to the discussion here. See the thread I linked to earlier for an exact discussion of GIT. ---
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [April 12, 2003, 9:20pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/34 "2003-04-12T21:20:38Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*Performing arithmetic has **nothing** to do with GIT. We’re talking about _modelling_ arithmetic, which is something completely different. If you don’t know the difference, you need to do more reading. \*\* I had a nice long post prepared, then **ultrafilter** comes by and sums it up in those three sentances. _sigh_… Anyway, let me just say two things: First, the game of life is turing complete in the sense that it can be used to compute anything that is computable by any other turing machine (provided the board is infinite in size…we’re talking abstractions, here). And yet, it can’t be “crashed”, in the sense that there is no state in the game of life which doesn’t lead to a well-defined successor state. Secondly, > [@](#): > > _Originally posted by Spiritus Mundi:_ > Being able to perform calculations is a different thing from meeting the requirements for GIT. > [@](#): > > _Originally posted by TVAA:_ > But the calculator does meet the requirements for GIT. It performs arithmetic. I sense a lack of communication. ---
**Author:** ![lucwarm](https://avatars.discourse-cdn.com/v4/letter/l/e19adc/32.png) [@lucwarm](https://boards.straightdope.com/u/lucwarm)\ **Post date:** [April 12, 2003, 9:52pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/35 "2003-04-12T21:52:33Z")
Here is a GD thread where I debated with someone over the significance of GIT to AI: [http://boards.straightdope.com/sdmb/showthread.php?threadid=115009&perpage=50&pagenumber=3](http://boards.straightdope.com/sdmb/showthread.php?threadid=115009&perpage=50&pagenumber=3) It seems to me that the argument basically boils down to the following: (1) GIT shows that some formal systems have limitations; (2) A working AI program is kinda like a formal system because it’s a computer program; (3) So AI programs probably have limitations; (4) Human intelligence is not a formal system and therefore not constrained by GIT; (5) Therefore humans can do stuff that AI programs will never do; (6) therefore working AI is impossible. The above argument is so wrong in so many ways, it’s hard to know where to begin. ---
**Author:** ![Spiritus\_Mundi](https://avatars.discourse-cdn.com/v4/letter/s/c68b51/32.png) [@Spiritus\_Mundi](https://boards.straightdope.com/u/Spiritus_Mundi)\ **Post date:** [April 13, 2003, 3:05am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/36 "2003-04-13T03:05:16Z")
An abacus can perform arithmetic calculations. Do you think that beads on a wire are limited by GIT? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 13, 2003, 6:00am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/37 "2003-04-13T06:00:20Z")
An abacus, by itself, does nothing. The beads on the wire are a method of notation only. On the other hand, as Einstein once said, pencil and paper are smarter than I am. And Conway’s Game of Life cannot itself be disrupted, by the structures generated in Life that would actually carry out the computation certainly can be. (I’ve never heard of anyone managing to pose a question that caused electrons to fail, but it can be done to electronic computers…) Would anyone care to explain the difference between modeling arithmetic and performing it? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 13, 2003, 5:03pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/38 "2003-04-13T17:03:53Z")
> [@](#): > > \*Originally posted by TVAA \* > \*\*Would anyone care to explain the difference between modeling arithmetic and performing it? \*\* It’s a little tough to discuss the difference, because they have nothing in common. Performing arithmetic is taking two numbers and returning the results of some arithmetic operation on them. Modeling arithmetic is saying “Here are these things called numbers, and these are their properties, and here are some operations on them, and here are the properties of those”. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 13, 2003, 5:17pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/39 "2003-04-13T17:17:14Z")
But how can arithmetic be performed without an underlying model of mathematics? Any system capable of accepting numbers in symbolic form and performing arithmatical operations on them _is_ a model of arithmetic – it’s the embodiment of the principles. A pocket calculator can be constructed only because the substances it’s made of obey certain physical laws, which are fundamentally mathematical in nature. If the laws of mathematics somehow changed, the entire world as we know it would be altered in ways we probably can’t imagine. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 13, 2003, 5:22pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/40 "2003-04-13T17:22:55Z")
> [@](#): > > \*Originally posted by TVAA \* > **But how can arithmetic be performed without an underlying model of mathematics?** Very easily. I give you two strings of 1’s and 0’s, and you operate on those by the rules described in your circuits and return another string of 1’s and 0’s. You don’t even know what it means. A model of arithmetic is a language which can express statements about arithmetic. No implementation is a model. And physics has nothing to do with this. We are concerned only with the logic. That’s why there are uncrashable computers–we don’t need to model that feature. [Previous page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=1) [Next page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=3)