# 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:** 13
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 1, 2003, 3:41pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/241 "2003-05-01T15:41:37Z")
Perhaps. It isn’t really a “debate” either (it’s merely a factual statement that some people would claim is false), and I’d hate to contaminate the boards more than these threads already have. In any case, since even the relatively simple and straightforward claims of the OP have been so incredibly difficult to convince certain StraightDopers of, I’m not sure there’d be a point. Ignoring the supposedly wise and knowledgeable **Superfriends** for the moment: what parts of my argument do you, **erislover** , disagree with? ---
**Author:** ![SentientMeat](https://avatars.discourse-cdn.com/v4/letter/s/43a26b/32.png) [@SentientMeat](https://boards.straightdope.com/u/SentientMeat)\ **Post date:** [May 1, 2003, 4:13pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/242 "2003-05-01T16:13:16Z")
Having watched this debate go on for a while, learning a lot but not fully understanding all the points herein, it appears that a standoff regarding whether a program and the hardware it runs on are equivalent. Might I suggest we take a single XOR gate and begin from there? ---
**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:** [May 1, 2003, 5:37pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/243 "2003-05-01T17:37:09Z")
Actually, this particular issue is more of a difference in terminology. I use program as an abstract term related to algorithm (it is the expression of an algorithm in a particular programming language). **TVAA** is apparently using it to mean: the pattern of bits on a particular machine. I have no idea what word **TVAA** would use to describe a high-level, assembler, or machine language construct that would encode a functionally identical series of instructions on more than one machine. But I’m pretty sure that whatever word he chose he would use it poorly and then call others stupid for not agreeing with his usage. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 1, 2003, 10:41pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/244 "2003-05-01T22:41:06Z")
First, I must not be misunderstood. The claim I made was that programs and computers are not distinguishable; the concepts are often useful when considered to be separate, but they aren’t truly separate. A program that duplicates the properties of the computer _is_ the computer, in the same way that the program can’t be said to exist without an embodiment. _Things are what they do._ That’s why any UTM can emulate any other UTM: because all the emulating UTM needs to do is simulate the workings of the emulated UTM. Consider the example of logic gates: all that’s required to generate the whole set of logic gates is the negation operation and either AND or OR. With those, everything else can be built. From their outputs, can you distinguish between OR and a group of NOT and AND put together in the proper way? Can you distinguish between AND and a group of NOT and OR put together in the proper way? Of course not. A group of NOT and AND put together in the proper way **is** an OR. A group of NOT and OR put together in the proper way **is** an AND. ---
**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:** [May 2, 2003, 1:10am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/245 "2003-05-02T01:10:45Z")
> [@](#): > > The claim I made was that programs and computers are not distinguishable; the concepts are often useful when considered to be separate, but they aren’t truly separate. That, of course, assumes that every program duplicates the properties of every computer, which is a pretty limited subset of the things we call programs. Then again, it has become quite clear that you much prefer to treat limited subsets as if they characterized the larger set. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 1:22am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/246 "2003-05-02T01:22:49Z")
No, stupid. My statement does not require all programs to be able to emulate all computers. What it means is that the conceptual categories of ‘program’ and ‘computer’ are not genuinely distinct. Every program capable of running can be run on an unlimited number of computers, and every computer can be emulated by an unlimited number of programs. The question of whether any particular system is a “computer” or a “program” is entirely arbitrary: nothing is implied by one conclusion that isn’t implied by the other. ---
**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:** [May 2, 2003, 5:16am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/247 "2003-05-02T05:16:58Z")
> [@](#): > > What it means is that the conceptual categories of ‘program’ and ‘computer’ are not genuinely distinct. > > Every program capable of running can be run on an unlimited number of computers, and every computer can be emulated by an unlimited number of programs. These two statements are not necessarily equivalent. The intersection of two infinitely large sets may be infinite without implying that the sets are identical. For instance: infinitely many positive integers are even, and an infinite number of even numbers are positive integers. Nevertheless, the set of positive integers is distinct from the set of even numbers. I suspect, though, that the real issue is that you map both “program” and “computer” to “Turing Machine”. If that is the case, then the two would be equivalent. The issue then becomes whether such a dual mapping is either “correct” or “useful”. ---
**Author:** ![MEBuckner](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mebuckner/32/2896_2.png) [@MEBuckner](https://boards.straightdope.com/u/MEBuckner)\ **Post date:** [May 2, 2003, 7:43am UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/248 "2003-05-02T07:43:38Z")
> [@](#): > > \*Originally posted by TVAA \* > No, you idiot > [@](#): > > \*Originally posted by TVAA \* > No, stupid. **Moderator’s Note:** **TVAA** , do not post personal insults in Great Debates. It’s against the rules, you _know_ it’s against the rules, now cut it out. ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [May 2, 2003, 12:54pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/249 "2003-05-02T12:54:49Z")
Given that a program is a set of instructions, something needs to be instruct_ed_. That something is the “computer.” It doesn’t matter if the “computer” is another program or not. The running program necessarily has to treat it as if it were a computer. If we have a case where computer A is running UTM B which is running TM C, then for program C, the “computer” is B. For program B, the computer is A, and C is just data to be manipulated. It’s quite obvious that computers sit idle without programs, and programs don’t execute without being in a computer. The fact that computers can be emulated by programs doesn’t change that, because the emulations have to also run on computers. Or on top of other emulations which are running on computers. Or on top of other emulations which are running on other emulations which are running on computers. Etc. If, for any given set of executing programs, you trace up the “emulation chain” far enough, you’ll necessarily find the hardware (the “real” computer: that which is not being emulated). Ah, there’s the issue: programs and computers are indistinguishable from each other from the point of view of a _program_. A program cannot ‘probe’ the computer it’s running on to see if it’s a real computer or another program emulating a computer (if the emulation is as precise as possible). But computers certainly can’t execute other hardware, and humans can easily tell the difference between hardware and software when looking into the systems from the outside. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 12:55pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/250 "2003-05-02T12:55:48Z")
_Yes_, **MEBuckner**. [grumble] We don’t need to go about comparing infinite sets, we just need to examine the meaning of “program” and “computer”. If the behavior of the components of the computer can be described, it can be duplicated by an infinitely large number of programs. If the behavior can’t be described, there’s no way it can be considered a computer: there’s no set of relationships between input and output. The suggestion that I’m claiming every program can emulate every computer, while not of a form that will raise a Moderator’s ire, is a significant insult to myself and my argument. It’s trivially obvious to show that isn’t the case: any arbitarily chosen program will not result in the same output as any arbitrarily chosen computer. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 12:58pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/251 "2003-05-02T12:58:13Z")
But you can’t find the “real” computer. That device can be considered to be the emulation of an arbitrary number of other computers. What we _can_ do is find the link in the computer-program chain that’s on our “level” of reality. That’s what we think of as real. It’s no more or less “real” than any other level of the chain… ---
**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:** [May 2, 2003, 1:50pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/252 "2003-05-02T13:50:35Z")
> [@](#): > > If the behavior of the components of the computer can be described, it can be duplicated by an infinitely large number of programs. If the behavior can’t be described, there’s no way it can be considered a computer: there’s no set of relationships between input and output. So what? It is also true that an arbitrarily large number of programs cannot emulate any compuer. When you say that “there is no difference between the two” you are placing arbitrary constraints upon those things we call “programs” or “algorithms”. It is not necessary that a program either accept external input or generate output. The standard for “computer” is usually a bit different, though I don’t believe that you have offered your definition for either “program” or “computer” and I have learned that it is unwarranted to assume that you use terms in an expected way. > [@](#): > > But you can’t find the “real” computer. That device can be considered to be the emulation of an arbitrary number of other computers. You have yet to demonstrate this claim. You have repeated it frequently, but that is not the same thing. > [@](#): > > What we can do is find the link in the computer-program chain that’s on our “level” of reality. That’s what we think of as real. It’s no more or less “real” than any other level of the chain… Likewise, this may be your favorite metaphysical model, but that does not mean it is so. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 1:58pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/253 "2003-05-02T13:58:00Z")
> [@](#): > > \*Originally posted by Spiritus Mundi \* > \*\*It is also true that an arbitrarily large number of programs cannot emulate any compuer. When you say that “there is no difference between the two” you are placing arbitrary constraints upon those things we call “programs” or “algorithms”. It is not necessary that a program either accept external input or generate output. \*\* Yuh huh. Just like a computer doesn’t need to generate external input or generate output, right **SM**? I don’t know which is more pathetic… that **SM** doesn’t understand the definition of “computer” or that his arguments directly contradict the arguments made earlier in these threads. Make up your mind, **Spiritus**. Does a computer need to either accept input or generate output? Does a program need to either accept input or generate output? > [@](#): > > \*\*The standard for “computer” is usually a bit different, though I don’t believe that you have offered your definition for either “program” or “computer” and I have learned that it is unwarranted to assume that you use terms in an expected way. \*\* And I’ve learned you can’t use the general definitions of words consistently. (Ah, but you think “consistently” allows for contradictions, so you’ll claim you _are_ being consistent, right?) Take the computer you suggest cannot be represent by a program. What is it doing? Describe its workings. We can now write a program to do exactly the same thing – all the program must do is carry out the same operations that we’ve described. It’s not a difficult concept to grasp… ---
**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:** [May 2, 2003, 2:33pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/254 "2003-05-02T14:33:36Z")
I never said that some computer could not be represented by a program. I have said two things: [ul][li]Some programs do not represent any computer.[/li][li]“represent” does not mean “is indistinguishable from”.[/ul][/li]Those statements are not particularly controversial. > [@](#): > > Yuh huh. Just like a computer doesn’t need to generate external input or generate output, right SM? No. Please read my words again paying attention to the statement: **The standard for “computer” is usually a bit different.** You see, in English “different” does not mean “just like”. > [@](#): > > I don’t know which is more pathetic… that SM doesn’t understand the definition of “computer” or that his arguments directly contradict the arguments made earlier in these threads. I understand the word computer quite well. It can have different meaning in different contexts, but you have studiously avoided actually offering the working definition for computer that allows you to say it is entirely independent of a physical expression (though you have also talked about “crashing” computers with a hammer, so it really isn’t clear exactly what you mean by the word.) > [@](#): > > Make up your mind, Spiritus. Does a computer need to either accept input or generate output? Does a program need to either accept input or generate output? Yes. No. > [@](#): > > And I’ve learned you can’t use the general definitions of words consistently. This claim is pretty absurd from someone who is arguing that the general understanding of “computer” is indistinguishable from the general understanding of “program”. > [@](#): > > Ah, but you think “consistently” allows for contradictions, so you’ll claim you are being consistent, right? Mathematical consistency _ **can** _ allow for inconcistency, depending upon the rules of inferencen that make up the grammar for teh system undee consideration. It really doesn’t matter whether you find that to be “intuitive” or “logical” or “appropriate”, that is the definition of mathematical consistency. > [@](#): > > Take the computer you suggest cannot be represent by a program. What is it doing? Describe its workings. Here’s a suggestion that I have actually made: you need to read more carefully. The things that you claim I say have little relationship to the things that I actually say. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [May 2, 2003, 2:37pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/255 "2003-05-02T14:37:29Z")
> [@](#): > > \*Originally posted by TVAA \* > I don’t know which is more pathetic… that **SM** doesn’t understand the definition of “computer” or that his arguments directly contradict the arguments made earlier in these threads. I can think of a third option. What contradiction? ---
**Author:** ![SentientMeat](https://avatars.discourse-cdn.com/v4/letter/s/43a26b/32.png) [@SentientMeat](https://boards.straightdope.com/u/SentientMeat)\ **Post date:** [May 2, 2003, 2:59pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/256 "2003-05-02T14:59:35Z")
If I may run in and ask what may be a stupid question like a child interrupting a serious meeting of adults: In this array of programs, surely _at least one_ of them must be a computer? If they are _all_ programs, nothing would run? Does this show that programs and computers are _not_ equivalent? ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 3:02pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/257 "2003-05-02T15:02:00Z")
> [@](#): > > \*Originally posted by Spiritus Mundi \* > \*\*I never said that some computer could not be represented by a program. I have said two things: > [ul][li]Some programs do not represent any computer.[/li][li]“represent” does not mean “is indistinguishable from”.[/ul][/li]Those statements are not particularly controversial. \*\* [sigh] “Represent” does not refer to empty symbolism. We’ve discussed this before: you have difficulty understanding that the the representation of the thing _is_ the thing. Does a set of NOT and AND gates “represent” an OR, or “is” it an OR? And you’re suggesting that programs are not algorithms? Strange… I seem to remember finding ways to force programs to enter infinite loops, preventing them from ever reaching an end state… No, that’s nothing like crashing the program. Nothing at all. And, of course, since a computer must be able to generate output as **SM** has said, giving the computer a program that doesn’t have any output (as **SM** has said is possible) makes it not a computer anymore. Not that the computer can be said to have crashed. Huh. > [@](#): > > \*\*I understand the word computer quite well. It can have different meaning in different contexts, but you have studiously avoided actually offering the working definition for computer that allows you to say it is entirely independent of a physical expression (though you have also talked about “crashing” computers with a hammer, so it really isn’t clear exactly what you mean by the word.) \*\* No, it’s independent of specific physical expressions. It’s not independent of physical expression, which is the whole point. The hammer is the input that the program emulating the computer can’t handle. > [@](#): > > [This claim is pretty absurd from someone who is arguing that the general understanding of “computer” is indistinguishable from the general understanding of “program”. \*\* Not at all. They’re simply different ways of describing the same thing. > [@](#): > > \*\*Mathematical consistency _ **can** _ allow for inconcistency, depending upon the rules of inferencen that make up the grammar for teh system undee consideration. \*\* We’ve had this argument before. First, you haven’t discussed “mathematical consistency”, you’ve discussed “consistency”. If you’re claiming “mathematical consistency” is a fundamentally different concept, you shouldn’t have removed ‘mathematical’ from the phrase. Secondly, you have yet to demonstrate a single cite that shows that is indeed what “mathematical consistency” can do. Every statement about consistency in mathematics I’ve been able to locate contradicts your claim. It really doesn’t matter whether you find that to be “intuitive” or “logical” or “appropriate”, that is the definition of mathematical consistency. > [@](#): > > \*\*Here’s a suggestion that I have actually made: you need to read more carefully. The things that you claim I say have little relationship to the things that I actually say. \*\* The things you claim I say have virtually nothing to do with the things I actually say. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 3:04pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/258 "2003-05-02T15:04:21Z")
> [@](#): > > \*Originally posted by erislover \* > \*\*I can think of a third option. What contradiction? \*\* Remember all that fuss about whether a “computer” necessarily needs to be able to accept input or generate output? Remember all that fuss about Turing machines that only generated output? Are those devices computers or not? ---
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [May 2, 2003, 3:17pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/259 "2003-05-02T15:17:15Z")
**TVAA** wrote: > [@](#): > > Take the computer you suggest cannot be represent by a program. What is it doing? Describe its workings. We can now write a program to do exactly the same thing – all the program must do is carry out the same operations that we’ve described. Not at all. A program _cannot_ read a symbol off a paper tape. It can read a _simulated_ symbol off a _simulated_ paper tape, but that is not “exactly the same thing” as reading an _actual_ symbol off an _actual_ paper tape. To interact with what we usually define as “the real world,” programs require an interface to that reality, and hardware is that interface. The program may not know whether it’s reading an actual or simulated paper tape, but so what? That doesn’t make the simulation and the reality “exactly the same thing.” I’m sure you might object that we all may be within a big simulation, and thus everything we think of as hardware is actually software, but that’s hardly logical or scientific, since the possibility can’t be tested. Might as well say we’re all thoughts in the mind of God, and that GIT implies that angels cannot take certain states. It’d make about as much sense. > [@](#): > > …you have difficulty understanding that the the representation of the thing _is_ the thing. _Ceci n’est pas un message-board post._ ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [May 2, 2003, 4:54pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/260 "2003-05-02T16:54:27Z")
> [@](#): > > \*Originally posted by DaveW \* > \*\ ***TVAA** wrote:Not at all. A program _cannot_ read a symbol off a paper tape. It can read a _simulated_ symbol off a _simulated_ paper tape, but that is not “exactly the same thing” as reading an _actual_ symbol off an _actual_ paper tape. \*\* But the simulated symbol is an actual symbol. > [@](#): > > \*\*To interact with what we usually define as “the real world,” programs require an interface to that reality, and hardware is that interface. The program may not know whether it’s reading an actual or simulated paper tape, but so what? That doesn’t make the simulation and the reality “exactly the same thing.” \*\* But the hardware is the program. An actual computer can’t do anything with input if it doesn’t have a program. (Put another way, the program is whatever the computer does with the input.) The “program” is whatever the internal workings of the computer are set to do. The devices we use for computation are reconfigurable, which is a large part of what makes them useful. But whenever we “run a program” on the computer, we’re really rearranging the components to produce a new computational system. That’s why ‘computer’ and ‘program’ aren’t formal terms, and why terms like “finite state machine” are used instead. A finite state machine is _both_ computer and program. A truly inconsistent set of instructions wont’ be able to emulate a computer; **Spiritus** is right about that. He’s wrong in that such a set is NOT a program. > [@](#): > > \*\*I’m sure you might object that we all may be within a big simulation, and thus everything we think of as hardware is actually software, but that’s hardly logical or scientific, since the possibility can’t be tested. \*\* It’s not a possibility, it’s a fact. If I said that there’s no difference between pie a la mode with ice cream on top of the pie or pie beneath the ice cream, would you say that’s not scientific? Logically, the hardware and the software are equivalent. The only “proof” needed is logical proof. The question then becomes whether the world we see if sufficiently powerful, and it certainly is. > [@](#): > > \*\* Might as well say we’re all thoughts in the mind of God, and that GIT implies that angels cannot take certain states. It’d make about as much sense. \*\* We **are** all thoughts in the mind of God. _Ceci n’est pas un message-board post._ \*\* [/QUOTE] [Previous page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=12) [Next page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=14)