# 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:** 12
**Author:** ![Liberal](https://avatars.discourse-cdn.com/v4/letter/l/848f3c/32.png) [@Liberal](https://boards.straightdope.com/u/Liberal)\ **Post date:** [April 23, 2003, 11:39am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/221 "2003-04-23T11:39:02Z")
> [@](#): > > [Gratuitous expletive deleted], didn’t you see The Matrix? I thought that movie had managed to make even the dimmest individuals understand that a reality is whatever interacts with you. So, _Oh God!_ proved that God exists? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 23, 2003, 1:13pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/222 "2003-04-23T13:13:36Z")
It did about a good a job as you did, and was a lot more entertaining. I give up, **Spiritus**. You win. The Gods themselves could not contend against you. ---
**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 23, 2003, 1:18pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/223 "2003-04-23T13:18:19Z")
I did not win. You remain as ignorant as when you opened this thread. ---
**Author:** ![Liberal](https://avatars.discourse-cdn.com/v4/letter/l/848f3c/32.png) [@Liberal](https://boards.straightdope.com/u/Liberal)\ **Post date:** [April 24, 2003, 10:34am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/224 "2003-04-24T10:34:02Z")
😃 ---
**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 26, 2003, 12:52pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/225 "2003-04-26T12:52:19Z")
> [@](#): > > \*Originally posted by TVAA \* > **The computer will never reach it on its own – given only the input and the rules that govern the computer, there will be memory sequences it can never have.** Just in case you do reappear, you should know that, if anything, these unobtainable “memory sequences” correspond to the non-theorems of an arithmetical system, and not to the true but unprovable type Godel statements. You must have played with a _Rubiks Cube_? There are some configurations that are just not reachable, say a single corner cubie twisted on it’s own\*, does this make the cube subject to GIT? Much of your argument appears to hinge on “unreachable states” \<=\> GIT, and that is simply not true. \*Actually you can get there by “stepping outside the system” and (for want of a better word) physically twisting it, but not by valid twists of the cube’s faces. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 26, 2003, 5:23pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/226 "2003-04-26T17:23:35Z")
There are other configurations that just aren’t reachable. For example, there can’t be a memory sequence that corresponds to the proof of the statement “this system cannot say this statement is true”, because if the statement were false, there would necessarily be a way of proving it (and so the system isn’t consistent), and if it were true, it’s unprovable. ---
**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 27, 2003, 5:43am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/227 "2003-04-27T05:43:13Z")
> [@](#): > > For example, there can’t be a memory sequence that corresponds to the proof of the statement “this system cannot say this statement is true”, because if the statement were false, there would necessarily be a way of proving it (and so the system isn’t consistent), and if it were true, it’s unprovable. And yet, every possible memory configuration in a register machine can be set and tested during diagnostic runs. Nothing stops the machine from reaching any physical memory configuration. This is trivially obvious. Every bit in a register machine is addressable. Every bit may be set “on” or “off”. What does that mean? It means that not every set of configurations through which a computer can cycle can necessarily be placed in correspondence to a logical system of sufficient power to invoke GIT. In other words, **TVAA’s** basic premise is wrong. It also means that being able to express every possible finite sentence in a system still doesn’t allow you to prove things that cannot be proved within that system. But I think even **TVAA** might have known that already. ---
**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 27, 2003, 4:33pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/228 "2003-04-27T16:33:54Z")
> [@](#): > > \*Originally posted by TVAA \* > \*\*[sigh] Y’know, **The Great Unwashed** , there was a reason I didn’t bother to respond to your question the first time. > > The record player’s behavior must be consistent, or it couldn’t be said to “play” the records. The record player’s behavior is admittedly complex enough to generate arithmetic – its actions are consistent with them. Ergo… \*\* **TVAA** – I guess to continue this conversation in this thread’s bastard offspring in the pit would be to post off-topic, so I’ve brought it over here. I didn’t really understand your post in its entirety, but I notice that you latch onto the notion of consistency, again. From page one: > [@](#): > > _The Great Unwashed_ > \*\*there is no requirement on an AI machine to instantiate a formal arithmetic to “represent the natural numbers”, nor to “understand arithmetic”, in (more than) 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?)\*\* (The parenthetical “more than” was unintentionally missed from my first post, oops.) …That is to say, specifically, that there are no _a priori_ reasons (that I know of – please illuminate me if I am wrong) to insist that any AI machine will have to instantiate a formal, **consistent** arithmetic. I mention this because it seems your OP addresses AI directly: > [@](#): > > \*\*Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers. > > It does mean that no finite system can ever derive all truths. No computer can be made that cannot be crashed. Mathematics is necessarily incomplete: there will always be “true” statements that cannot be proven within a given system.\*\* **1.** _Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers_ I agree, as I suspect just about every other poster to the thread does. **2.** _It does mean that no finite system can ever derive all truths._ I believe it is true that no finite system could, but this is more readily seen as a consequence of its finiteness and not GIT. **3.** _No computer can be made that cannot be crashed._ This seems to me to be trivially false, and several examples of non-crashable computers have been given. Extending the definition of “crashable” to include “smashable by a sledgehammer” is asking too much of a reasonable definition, but even accepting such a broad definition, it does not then follow from GIT but more from the notion that everything can be broken. **4.** _Mathematics is necessarily incomplete: there will always be “true” statements that cannot be proven within a given system._ Indeed, this is a consequence of GIT, the truth of which nobody has denied. But I’m confused now, because if **3.** were true then wouldn’t that make **1.** false? Or do you know of methods to crash the human mind too? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 27, 2003, 4:37pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/229 "2003-04-27T16:37:08Z")
Point 3: The “computer” in question that would be smashed is a program being run by physical reality. In this program, the sledgehammer strike is merely input that the computer system can’t handle. There are more interactions possible in physical reality than the computer can cope with. There are indeed methods for crashing human brains. I presume you heard about the whole Pokemon-seizure problem? ---
**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 27, 2003, 6:06pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/230 "2003-04-27T18:06:32Z")
Fair enough (but that’s not what is usually understood by the word _crash_), and precisely what’s that got to do with GIT? **TVAA** , I really, _really_, believe that you have may some point, but I’m not following it. To the best of my understanding the universe does follow from one state to another according to deterministic rules (except the possibly minor hiccup of quantum-mechanical dice-throwing (but even then there are still “rules”)). Are you saying therefore that there are states the universe will/can never reach? I think that’s agreed – the universe will never be populated by nothing but overripe bananas, for instance – but again, what’s that got to do with GIT? This has got to be a whacky aside – if the universe is wholly deterministic then the past, the present, the future are really just illusions, right? There are no degrees of freedom, just a single unified, unmoving snap-shot of the whole of space-time? i.e. Exactly ONE state – all other states are trivially unreachable. Ah, for goodness sake just tell me what you mean, I’m clutching at straws here. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 27, 2003, 10:29pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/231 "2003-04-27T22:29:59Z")
> [@](#): > > \*Originally posted by The Great Unwashed \* > \*\*Fair enough (but that’s not what is usually understood by the word _crash_), and precisely what’s that got to do with GIT? \*\* Sending a program into an infinite loop, causing it to use up its available memory and catastrophically fail, or otherwise forcing a computational system into a configuration its design cannot accomodate can reasonably be called “crashing” the system. > [@](#): > > **TVAA, I really, _really_, believe that you have may some point, but I’m not following it.** Well, thank you for at least giving me the benefit of the doubt. > [@](#): > > **To the best of my understanding the universe does follow from one state to another according to deterministic rules (except the possibly minor hiccup of quantum-mechanical dice-throwing (but even then there are still “rules”)).** That does indeed seem to be the case; while there are those who would argue the question, their objections don’t seem particularly meaningful IMO. > [@](#): > > \*\*Are you saying therefore that there are states the universe will/can never reach? I think that’s agreed – the universe will never be populated by nothing but overripe bananas, for instance – but again, what’s that got to do with GIT? > > This has got to be a whacky aside – if the universe is wholly deterministic then the past, the present, the future are really just illusions, right? There are no degrees of freedom, just a single unified, unmoving snap-shot of the whole of space-time? \*\* Well, that’s trivially true if we consider the entirety of everything – it will always do the only thing it can do. But that’s not the point. The whole point of this argument is it’s not possible to make a system that can cope with any data it’s given because it’s not possible for such a system to exist. This has a variety of consequences, including the one that any pattern within the universe will always have vulnerabilities. For example, it’s not possible to make an immune system that always ignores the body it’s in but can react to every possible external substance. Very effective and accurate immune systems might well be possible, but there will always be a (hypothetical) interaction with the world that would cause the immune system to fail somehow, either by not reacting to a threat or overreacting to a harmless thing. Of course, if the universe if finite, then there might be systems for which the circumstances that would cause them to fail never actually arise within it. In that case, the system would indeed be “perfect” – but no one would ever be able to show that it was in fact perfect. If the universe is infinite, the possibility that any system will be confronted with its vulnerabilities is necessarily non-zero. Is that any clearer? ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 28, 2003, 1:52pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/232 "2003-04-28T13:52:07Z")
> [@](#): > > But that’s not the point. The whole point of this argument is it’s not possible to make a system that can cope with any data it’s given because it’s not possible for such a system to exist. So where does the universe get its data? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 28, 2003, 2:15pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/233 "2003-04-28T14:15:09Z")
It doesn’t. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 29, 2003, 3:08pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/234 "2003-04-29T15:08:19Z")
So what is the point of comparing the universe to a UTM? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 29, 2003, 4:04pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/235 "2003-04-29T16:04:31Z")
I’m not, exactly. I’m showing that, at least for the case of UTMs, there is no true difference between the program and the system running it. **SM** ’s general statement that the two are necessarily different is thus falsified. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 29, 2003, 4:22pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/236 "2003-04-29T16:22:49Z")
How in the hell was that falsified? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 29, 2003, 4:31pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/237 "2003-04-29T16:31:02Z")
**SM** says that there’s a fundamental difference between programs and computers. I show that, at least in one case, that’s clearly false. Since there’s an exception, the statement isn’t true. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 29, 2003, 4:39pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/238 "2003-04-29T16:39:25Z")
I missed the exposition, I’m sorry. If you mean this: > [@](#): > > Every UTM can be emulated by another, and that UTM can be emulated by another, and so on ad infinitum. Which is the hardware and which is the program? Then color me unimpressed. As ever, emulation and simulation are not indicators of the equivalence of existential identity. If they are, I don’t feel it is self-evident and I would request development of the point. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 29, 2003, 4:41pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/239 "2003-04-29T16:41:40Z")
[sigh] Fair enough. I’ll be back in a while to continue this point. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 29, 2003, 4:47pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/240 "2003-04-29T16:47:34Z")
It might be worth a seperate thread. Just MHO. [Previous page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=11) [Next page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=13)