# 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:** 7
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 4:31pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/121 "2003-04-16T16:31:25Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*These statements (along with many others you’ve made) all require proof. Please prove them, or stop asserting them. \*\* We already know that physics is sufficiently complex to model arithmetic because we’ve built physical systems capable of doing so! You’re not looking for proof, you’re looking for a long series of known mathematical symbols. Logical arguments do not need to be presented in a specific notation to be either valid or correct. > [@](#): > > _Originally posted by Orbifold_\*\*Even if we assume the above statement is true, the succeeding statement: [edit] does not follow, for reasons that I’ve already explained. GIT does not constrain the configurations of electrons any more than it constrains the configuration of a pencil and paper; all GIT does is constrain the meanings which we can attribute to those configurations. \*\* **Yes it _does_**. If we build a little robot that examines marks on paper and makes additional marks according to certain rules, we’ve developed a system. GIT shows us that there are certain configurations of marks on paper that this system will never generate. Making marks on paper with a soft graphite rod stuck in a hollow wooden shaft can also be considered to be a system – the laws that govern the behavior of the materials are subject to GIT too. The interactions of their component parts follow certain laws, and the Theorem guarantees that there are possible configurations that these laws cannot generate on their own – a larger system is necessary. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 4:39pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/122 "2003-04-16T16:39:40Z")
> [@](#): > > \*Originally posted by Spiritus Mundi \* > \*\*Complexity theory in computer science addresses the resources required to solve a problem. It has nothing to do with how much information is contained within a system. The standard notation for his is the [big O notation](http://www.wikipedia.org/wiki/Big_O_notation). Life and “meta life” have identical complexity under standard usage. \*\* Incorrect. There are always ways to make the computation more complex – if complexity were merely the resources required to solve a problem, it would be undefined, as any solution implies the existence of a more complex solution with unnecessary steps. Complexity theory concerns itself with the _minimum_ required resources to solve a problem, and this is directly concerned with the amount of information contained within the system. A “perfect” model of a system requires that the system be reproduced perfectly. Running an L-glider in a life grid takes fewer resources than running it in a life meta-grid. This is trivially obvious: merely representing the five on-units of the glider in the meta-grid requires representing thousands of squares, while representing the five on-units of the glider takes only five grid squares. ---
**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\ **Post date:** [April 16, 2003, 5:03pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/123 "2003-04-16T17:03:08Z")
> [@](#): > > \*Originally posted by TVAA \* > You’re not looking for proof, you’re looking for a long series of known mathematical symbols. Logical arguments do not need to be presented in a specific notation to be either valid or correct. It’s not a question of notation as much as it is a question of rigour, as I see it. GIT is a statement originally expressed in mathematical notation. As such, it is a very precise, abstract statement. Attempting to argue from GIT in English rather than in mathematical notation (unless you go into an obscene amount of detail) introduces imprecision. It does so by taking mathematical symbols with well-defined abstract meanings and attempting to make them correspond with real-world phenomena. It is essentially no different from an analogy. These analogies are often very good, just as the analogy between observed planetary motion and F = GmM/R^2 is very good. But such analogies are not automatically justified. They require corroborating observational data that shows the physical phenomenon accurately mimics the behaviour of the abstract system. The only observational data of this type that you’ve presented so far that is not speculative effectively boils down to the observation that computers can be crashed by extreme physical stimulus, for example a hammer. This does not mimic the behaviour of formal arithmetic systems described by GIT, in the opinion of myself and other posters in this thread. In short you haven’t convinced us. But I imagine you guessed that. > [@](#): > > **Yes it _does_**. > > If we build a little robot that examines marks on paper and makes additional marks according to certain rules, we’ve developed a system. GIT shows us that there are certain configurations of marks on paper that this system will never generate. > > Making marks on paper with a soft graphite rod stuck in a hollow wooden shaft can also be considered to be a system – the laws that govern the behavior of the materials are subject to GIT too. The interactions of their component parts follow certain laws, and the Theorem guarantees that there are possible configurations that these laws cannot generate on their own – a larger system is necessary. In the robot scenario, the question merely shifts from the meaning of the marks to the meaning of the robot’s internal states. If I constrain myself to only put marks on the paper according to certain rules then the question shifts from the meaning of the marks to the meaning of the rules, i.e. the meaning of _my_ internal state. GIT says nothing until the _meaning_ of the marks or the states or the rules comes into the picture. ---
**Author:** ![scotandrsn](https://avatars.discourse-cdn.com/v4/letter/s/a4c791/32.png) [@scotandrsn](https://boards.straightdope.com/u/scotandrsn)\ **Post date:** [April 16, 2003, 5:21pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/124 "2003-04-16T17:21:26Z")
> [@](#): > > A good definition of terms, but this statement is simply wrong. As I mentioned earlier: > [@](#): > > By the way, you need to check your history. Hilbert made his call for theorems long before Godel or Turing published anything, and Godel’s paper was published ten years before Turing wrote his dissertation. My source (Cohen, “Automata Theory”) presents these matters in such a way as to emphasize that the concepts form part of a continuum, to the point of suggesting a concurrent timeline involving Goedel and Turing. I claim to be no expert in the historyof mathematical study, so I will concede the historical point. However, as TMs can be used to generate statements of number theory, they do relate strongly to Goedel’s work. > [@](#): > > That’s not standard usage. The machine is said to reject the input, not crash. My source uses the terms interchangeably. You can construct a TM that has a specific REJECT state, or you can simply let it die in a non-accepting state, which my source refers to as crashing. > [@](#): > > This isn’t clear. Are you saying that by tracing through the code you can determine whether a given program will halt for a given input? That’s not correct. You are correct. I did not mean to state my case in such a way as to imply that this could be done. Hey, it was 1:00AM. The point is, the undecidability of the halting problem says there is not way to know ahead of time how a given string will cause a given TM to behave. Some earlier posts seemed to me (again, it was 1 AM) to be trying to suggest that you could construct a physical machine that would accept every string, and only crash due a hardware failure. The undecidability of the Halting Problem says to me that you could never prove that such a machine performs in such a way. > [@](#): > > Calculating sums is not the same as generating statements of number theory. True. BUT! Calculating sums, is in essence simply a matter of substitution of symbols: If I have “3 + 5” in front of me, I can substitute “8”, and mathematics says I am correct in doing this. I can then take this to the abstract case. If I have proven that a+b=c, where a, b, and c are numbers, functions on ‘z’, or whatever, then anytime I generate ‘c’ in my explorations of number theory, I am correct in substituting ‘a + b’, which I might wish to do if that helps my proof. Since this is simply a question of symbol manipulation, I can create a Turing Machine that performs the substitutions in one or the other direction across the equality. I can then, if I so wish, incorporate the states that make up that TM into a larger machine in such a way that, if the machine generates f(a+b) where f is some function, I can substitute for it f©. This is what makes TMs such good tools for exploring number theory. > [@](#): > > GIT places absolutely no restrictions on the behavior of any program that is not generating statements of number theory Here’s how I think this all came about. TMs accept languages called recursively enumerable (r.e.)languages. Let’s say I’ve built a UTM, “M”, that reads a certain set of symbols (its alphabet), and I wish to create TMs to run on M. I develop a Code Word Language (CWL), a consistent set of algorithms that takes definitions of TMs and their inputs and turns them into sets of symbols in M’s alphabet. So if I want to run string “a” through TM “T”, I create CWL(T) and CWL(a) and put them one after the other into M. CWL(T) sets up M in such a way that when I give it CWL(a), the resultant behavior of M EXACTLY simluates the behavior "T "would exhibit if it were fed “a”. NOW: As long as it is a string of symbols in M’s alphabet, I can feed any old string into M’s simulation of T. Well, CWL(T) is a string in M’s alphabet, so what happens if I feed T to its own simulation? It will either accept the string or not (loop or crash). It turns out that the set of strings that are CWL translations of TMs that accept their own CWL translations as input form an r.e. language. That means you can build a TM that will accept this language. What about the strings of CWL translations that represent TMs that can NOT accept their own CWL translations as input? It has been proven mathematically that the collection (language) of such strings is NOT r.e. It has also been shown that this language is NOT empty. Therefore, there is a class of languages that you CAN NOT build a TM (or by extension a UTM/computer) to accept. Because our brains CAN accept these languages, this seems to place an upper limit on the processing power of computers that will always be less than that of the brain. Each string in one of these languages essentially states: “I am a TM that can not accept myself as input” My inderstanding of GIT is that Goedel’s statement was of the nature of Zeno’s paradox, essentially saying: “I am a statement of number theory that is unprovable within the axiomatic system of mathematics”. If proveable, it’s a false statement generated by the system, but if it’s not proveable, it’s true. There is a certain shared nature about these two quoted statements, that leads to the thinking mentioned in the OP (and other places where I have seen similar assertions. Whether or not someone has ever proven a connection, I’m afriad I do not know. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 16, 2003, 5:46pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/125 "2003-04-16T17:46:15Z")
> [@](#): > > \*Originally posted by TVAA \* > **We already know that physics is sufficiently complex to model arithmetic because we’ve built physical systems capable of doing so!** One more time, these types of models are not the types of models that are discussed in GIT. If you think they are, you must demonstrate so. Please use the statement of GIT that I posted on page 2. \*\* > [@](#): > > You’re not looking for proof, you’re looking for a long series of known mathematical symbols. Logical arguments do not need to be presented in a specific notation to be either valid or correct.\*\* No, but it does need to start with the correct definitions. You’re defining a sheep’s tail to be a leg and claiming its got five legs. \*\* > [@](#): > > Complexity theory concerns itself with the minimum required resources to solve a problem, and this is directly concerned with the amount of information contained within the system. A “perfect” model of a system requires that the system be reproduced perfectly.\*\* A “perfect” model in this sense may be less complex than the system it models. Are you familiar with Kolmogorov’s work? Also, when you jump from discussing problems to systems, what systems are you talking about? \*\* > [@](#): > > Running an L-glider in a life grid takes fewer resources than running it in a life meta-grid. This is trivially obvious: merely representing the five on-units of the glider in the meta-grid requires representing thousands of squares, while representing the five on-units of the glider takes only five grid squares.\*\* However, relative to the models of computation, the complexity is the same. The grid and the meta-grid are isomorphic. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 16, 2003, 6:04pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/126 "2003-04-16T18:04:02Z")
> [@](#): > > \*Originally posted by scotandrsn \* > **My source uses the terms interchangeably. You can construct a TM that has a specific REJECT state, or you can simply let it die in a non-accepting state, which my source refers to as crashing.** OK, I’ve seen something like that before. Calling it crashing is unusual, though–everything I’ve seen refers to that kind of behavior as rejecting. In this discussion, the sense of crashing is that we have a machine with two final states, q[sub]accept[/sub] and q[sub]reject[/sub]. An input crashes a TM if it causes it to halt in some non-final state. That’s not possible with a properly designed TM. \*\* > [@](#): > > You are correct. I did not mean to state my case in such a way as to imply that this could be done. Hey, it was 1:00AM. The point is, the undecidability of the halting problem says there is not way to know ahead of time how a given string will cause a given TM to behave. Some earlier posts seemed to me (again, it was 1 AM) to be trying to suggest that you could construct a physical machine that would accept every string, and only crash due a hardware failure. The undecidability of the Halting Problem says to me that you could never prove that such a machine performs in such a way.\*\* I have a TM with two states, q[sub]0[/sub] and q[sub]accept[/sub]. On running, it examines the first cell of the input tape, writes the same character, transitions to q[sub]accept[/sub], and moves the head one cell right. This machines halts in an accepting state on every input, and it’s rather easy to prove that. \*\* > [@](#): > > True. BUT! Calculating sums, is in essence simply a matter of substitution of symbols: If I have “3 + 5” in front of me, I can substitute “8”, and mathematics says I am correct in doing this. > > I can then take this to the abstract case. If I have proven that a+b=c, where a, b, and c are numbers, functions on ‘z’, or whatever, then anytime I generate ‘c’ in my explorations of number theory, I am correct in substituting ‘a + b’, which I might wish to do if that helps my proof. Since this is simply a question of symbol manipulation, I can create a Turing Machine that performs the substitutions in one or the other direction across the equality. I can then, if I so wish, incorporate the states that make up that TM into a larger machine in such a way that, if the machine generates f(a+b) where f is some function, I can substitute for it f©. This is what makes TMs such good tools for exploring number theory.\*\* That’s still not connected to proving statements about number theory. I don’t think it’s the important part of your argument, though. \*\* > [@](#): > > Here’s how I think this all came about. > > TMs accept languages called recursively enumerable (r.e.)languages. Let’s say I’ve built a UTM, “M”, that reads a certain set of symbols (its alphabet), and I wish to create TMs to run on M. I develop a Code Word Language (CWL), a consistent set of algorithms that takes definitions of TMs and their inputs and turns them into sets of symbols in M’s alphabet. So if I want to run string “a” through TM “T”, I create CWL(T) and CWL(a) and put them one after the other into M. CWL(T) sets up M in such a way that when I give it CWL(a), the resultant behavior of M EXACTLY simluates the behavior "T "would exhibit if it were fed “a”. > > NOW: As long as it is a string of symbols in M’s alphabet, I can feed any old string into M’s simulation of T. Well, CWL(T) is a string in M’s alphabet, so what happens if I feed T to its own simulation? It will either accept the string or not (loop or crash). It turns out that the set of strings that are CWL translations of TMs that accept their own CWL translations as input form an r.e. language. That means you can build a TM that will accept this language. > > What about the strings of CWL translations that represent TMs that can NOT accept their own CWL translations as input? It has been proven mathematically that the collection (language) of such strings is NOT r.e. It has also been shown that this language is NOT empty. Therefore, there is a class of languages that you CAN NOT build a TM (or by extension a UTM/computer) to accept. Because our brains CAN accept these languages, this seems to place an upper limit on the processing power of computers that will always be less than that of the brain. > > Each string in one of these languages essentially states: > > “I am a TM that can not accept myself as input” > > My inderstanding of GIT is that Goedel’s statement was of the nature of Zeno’s paradox, essentially saying: > > “I am a statement of number theory that is unprovable within the axiomatic system of mathematics”. > > If proveable, it’s a false statement generated by the system, but if it’s not proveable, it’s true. > > There is a certain shared nature about these two quoted statements, that leads to the thinking mentioned in the OP (and other places where I have seen similar assertions. > > Whether or not someone has ever proven a connection, I’m afriad I do not know. \*\* I discussed the connection earlier in this thread, I believe. If I haven’t, let me know, and I’ll describe it. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 6:04pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/127 "2003-04-16T18:04:29Z")
> [@](#): > > \*Originally posted by Orbifold \* > \*\*In the robot scenario, the question merely shifts from the meaning of the marks to the meaning of the robot’s internal states. If I constrain myself to only put marks on the paper according to certain rules then the question shifts from the meaning of the marks to the meaning of the rules, i.e. the meaning of _my_ internal state. GIT says nothing until the _meaning_ of the marks or the states or the rules comes into the picture. \*\* It has nothing to do with “meaning” as you’re using the word. It’s not the _meaning_ of the rules but their _behavior_ that is important. I told you before: these symbols aren’t empty. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 16, 2003, 6:07pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/128 "2003-04-16T18:07:54Z")
> [@](#): > > \*Originally posted by TVAA \* > \*\*It has nothing to do with “meaning” as you’re using the word. > > It’s not the _meaning_ of the rules but their _behavior_ that is important. I told you before: these symbols aren’t empty. \*\* The symbols _are_ empty. That’s the whole point of model theory. That’s why you can have non-standard reals. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 6:14pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/129 "2003-04-16T18:14:32Z")
The modeling convention is arbitrary. For example, there are other ways to represent numbers that binary electric pulses. However, once we’ve established that convention, the configuration of the system is non-arbitrary. For a specific convention, a set of logic gates **is** addition: it does everything addition does. The behavior of the gates is consistent with the concept of addition. Symbols can be empty only if they’re used as memory for a system in which they’re actually significant. ---
**Author:** ![scotandrsn](https://avatars.discourse-cdn.com/v4/letter/s/a4c791/32.png) [@scotandrsn](https://boards.straightdope.com/u/scotandrsn)\ **Post date:** [April 16, 2003, 6:18pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/130 "2003-04-16T18:18:26Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\* > I have a TM with two states, q[sub]0[/sub] and q[sub]accept[/sub]. On running, it examines the first cell of the input tape, writes the same character, transitions to q[sub]accept[/sub], and moves the head one cell right. This machines halts in an accepting state on every input, and it’s rather easy to prove that. > \*\* What about the situation where the input tape contains the empty string (i.e., there is no input?)? If you tell me that this input, too, causes the transition, then the input is irrelevant, and your case is a trivial one. You have shown nothing but that I should have restricted my discussion to non-trivial cases. \*\* > [@](#): > > That’s still not connected to proving statements about number theory. Your trying to tell me that proving mathematical theorems never involves symbol manipulation. You’ll have to back that one up for me. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 16, 2003, 6:32pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/131 "2003-04-16T18:32:44Z")
> [@](#): > > \*Originally posted by scotandrsn \* > **What about the situation where the input tape contains the empty string (i.e., there is no input?)? If you tell me that this input, too, causes the transition, then the input is irrelevant, and your case is a trivial one. You have shown nothing but that I should have restricted my discussion to non-trivial cases.** What about any TM that visits each state exactly once? Or a machine that never writes to the input tape and only moves its head to the right? There are many special cases for which the halting problem is decidable. If you ignore those, then yes, the halting problem describes all instances, but that doesn’t seem like much of a victory for you. \*\* > [@](#): > > Your trying to tell me that proving mathematical theorems never involves symbol manipulation. You’ll have to back that one up for me. \*\* No, actually I’m claiming that being able to perform calculations is never important for theorem-proving. ---
**Author:** ![GOM](https://avatars.discourse-cdn.com/v4/letter/g/5f9b8f/32.png) [@GOM](https://boards.straightdope.com/u/GOM)\ **Post date:** [April 16, 2003, 6:57pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/132 "2003-04-16T18:57:46Z")
I’m sor\_y. Yo\_r q\_est\_on do\_s n\_t c\_mp\_t\_. Pl\_as\_ rest\_t\_ y\_ur q\_ \_ st\_ \_n us\_ng hyp\_rdim\_s\_on\_l ph\_s\_ics. Th\_nk y\_u. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [April 16, 2003, 6:58pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/133 "2003-04-16T18:58:01Z")
> [@](#): > > \*Originally posted by TVAA \* > **If we build a little robot that examines marks on paper and makes additional marks according to certain rules, we’ve developed a system. GIT shows us that there are certain configurations of marks on paper that this system will never generate.** This is either sloppy or wrong. I don’t understand your little robot very well, so I’m going to go back to Turing Machines. Are you saying the there are certain strings that cannot ever be found on a Turing Machine’s tape, and that this is required by GIT? That is wrong. A TM can be built that accepts every string (remember that the string on the tape when the machine starts is finitely long). A TM can be built that enumerates all finite strings. > [@](#): > > \*Originally posted by scotandrsn \* > **My source (Cohen, “Automata Theory”) presents these matters in such a way as to emphasize that the concepts form part of a continuum, to the point of suggesting a concurrent timeline involving Goedel and Turing.** I imagine you could suggest that a lot of people doing work in this field in the '30s and '40s were on a “concurrent timeline involving Goedel”. > [@](#): > > **My source uses the terms [reject and crash] interchangeably.** I think that is sloppy, and unfortunate, too. A TM can halt or not. It does not “crash”. If it hasn’t halted yet, it just hasn’t halted (shades of the halting problem, here). If it never halts, it does not halt. If it halts and it’s not in an accept state, it rejected the input. It did not crash. Neither of the only two references I have on hand, Papadimitriou’s _Computational Complexity_ nor Hopcroft and Ullman’s _Introduction to Automata Theory, Languages, and Computation_ use “crash” to describe failure to halt on an input or rejecting an input. > [@](#): > > **The point is, the undecidability of the halting problem says there is not way to know ahead of time how a given string will cause a given TM to behave.** More pedantry from me. If you are talking about a given string and a given TM, then you have a single instance of the halting problem. It is trivial to build a TM to decide that instance: There is a TM, call it M1, that rejects every string. There is a TM, M2, that accepts every string. For a given Turing Machine and a given string, the machine will either halt or not halt on that string as input. One of the machines M1 or M2 decides this problem correctly. This is because, as **Spiritus** has said (three times? four?) decidability and completeness are not the same thing! That is, we might have some statement of number theory that cannot be proven, and whose negation cannot be proven, and there still exists a TM that “decides” it. > [@](#): > > Some earlier posts seemed to me (again, it was 1 AM) to be trying to suggest that you could construct a physical machine that would accept every string, and only crash due a hardware failure. Sure you can. It’s easy. Read to the end of the tape. Accept. If you don’t require me to read all the tape, I’ll just enter an accept state from the start state. I don’t know how that machine will fail, other than some “hardware failure”. > [@](#): > > **The undecidability of the Halting Problem says to me that you could never prove that such a machine performs in such a way.** Nothing says that it is necessarily hard for a particular machine to prove that it halts for a particular input, or even all inputs. Your challenge is to _construct_ such a machine, that’s easy. > [@](#): > > **TMs accept languages called recursively enumerable (r.e.)languages.** True. They can also decide recursive languages, and compute primitive recursive functions… > [@](#): > > **Therefore, there is a class of languages that you CAN NOT build a TM (or by extension a UTM/computer) to accept. Because our brains CAN accept these languages, this seems to place an upper limit on the processing power of computers that will always be less than that of the brain.** Yes, there are languages that are not recursively enumerable. If a language and its complement are both r.e., then the language is recursive. The existence of a language that is r.e. but not recursive implies the existence of a language that is not r.e. (namely, its complement). But I’m puzzled how you think that your brain is able to “accept” a language that is not r.e.–take the complement of _H_ (the language whose strings are descriptions of TM’s _M_ and inputs _x_ such that _M_ halts on _x_)? I’m serious. It would be a cool party trick, and a real boon for my work. When posed with an undecidable problem I could just pop up a GUI window and ask the user to tell me the answer. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [April 16, 2003, 7:03pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/134 "2003-04-16T19:03:28Z")
> [@](#): > > \*Originally posted by scotandrsn \* > **What about the situation where the input tape contains the empty string (i.e., there is no input?)?** Well, the tape is infinite to the right. And there is a distinguished blank symbol, call it **B**. “The input tape contains the empty string” means that the first (and indeed, all) symbol is **B**. **ultrafilter** ’s machine works just fine in that case. > [@](#): > > **If you tell me that this input, too, causes the transition, then the input is irrelevant, and your case is a trivial one.** It computes the identity function. You might call that trivial, but I call it fundamental. ---
**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 16, 2003, 8:05pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/135 "2003-04-16T20:05:43Z")
TVAA I have already said that I see no point in repeating an endless process of “No, it doesn’t” “Yes it does” statements with you. You are making statements in this htread that are factually incorrect. You are using terminology in a manner that is inconsistent with standard usage in the fields of computer science and mathematics. > [@](#): > > Does the algorithm for the Game of Life has a consciousness? If it doesn’t, haven’t I just presented an example of a non-conscious system modeling another? That depends upon what you mean by “model”, which is the question I have been asking you to answer. Apparently, you mean “can be described by the same mathematical equations”. Is that accurate? > [@](#): > > But human interpretation isn’t required. The movements of electrons are sufficiently complex that they “contain” arithmetic – as a result, GIT shows that there are configurations of electrons that can never be reached. This is an unspported assertion on your part. Actually, it is two unsupported assertiond. **IN EXACTLY WHAT MANNER DO YOU MEAN “electrons contain arithmetic” TO BE INTERPRETED?** [ Really. It is very important for you to answer specific questions if you expect anybody who understands GIT to think that your position is anything other than a SWAG without the S. > [@](#): > > They do fail to move in certain manners because of GIT. You have provided no reasonable suport for that assertion. > [@](#): > > Define your term, please. Element: a member of a set. In this case, an irreducible component part of a system. (What is irereducibvle, of course, alters with the level of analysis.) See, it isn’t so hard. Now please define “model” and “complexity” as you use the terms. > [@](#): > > It’s a mathematical fact [that “meta life” is far less complex than the life grid on which it is instantiated."] No, it is not. In mathematics, as in computer science, complexity has a specific meaning. You are using the term improperly. Did you even bother to follow the link I provided? An order N algorithm with 2 pieces of input has exactly the same complexity as an order N algorithm with 2 million pieces of input. It serves no useful purpose for you to misuse terminology and then make pronouncements of fact based upon your variant meanings for words. > [@](#): > > If we build a little robot that examines marks on paper and makes additional marks according to certain rules, we’ve developed a system. GIT shows us that there are certain configurations of marks on paper that this system will never generate. Yes, but that is because of the rules we have encoded in the robot, not some fantasy that there is a limitation on what marks can ever be placed on a piece of paper because of GIT. The only thing GIT tells us about marks on a paper is that there is no way to ever interpret marks on paper to be a proof of certain valid number theoretic statements **because no such proofs can exist.** This is a limitation of math, not a limitation of pencil and paper. What you are saying is analagous to: **It’s impossible to write down the method for squaring a circle using geometric construction because the electrons are can’t move in a certain way.** > [@](#): > > Incorrect. There are always ways to make the computation more complex – if complexity were merely the resources required to solve a problem, it would be undefined, as any solution implies the existence of a more complex solution with unnecessary steps. No, the statement was correct. Your statement is confused. Perhaps this is because you are using terms in a non-standard manner. Perhaps it is because you do not understand the concepts. I cannot tell which. In computational theory, a problem is simply a set of strings representing input and a set of strings representing output. An algorithm is a method for mapping input strings to output strings. Complexity is a measure of algorithms, (the things that “solve” problems). Sometimes a problem is discussed as including both the sets of strings **and** a mapping algorithm. In such contexts, you might see the unrigorous phrase “complexity of the problem”, but the meaning is always “complexity of the algorithm included in the problem definition”. Changing the algorithm can certainly result in a new algorithm with different complexity, and it is certainly correct that problems can be solved by more than one algorithm. Saying that this changes the complexity of a problem, though, betrays a deep misunderstanding of the standard terminology. Complexity is a measure of algorithms. By the way, “minimum” adds no meaning to the statement “resources required”. Anything that could be removed to “minimize” the set was obviously not required. _N’est ce pas?_ > [@](#): > > Complexity theory concerns itself with the minimum required resources to solve a problem That is what I said, though I did not include superfluous modifiers. > [@](#): > > this is directly concerned with the amount of information contained within the system. This statement is simply and unambiguously false. Complexity is not a measure of information within a system. Outputing an input string is an algorithm of order N, no matter how many characters are in the string. Complexity is expressed as **a function of** the size of input. Please pay attention to the bolded part of that statemnet. Complexity==the function, not some value for the function given a specified input string. scotandrsn > [@](#): > > However, as TMs can be used to generate statements of number theory, they do relate strongly to Goedel’s work. Only in the very specific manner that I explained above. A TM **that is generating statements of number theory** is constrained by GIT so that it may not generate all true statements. GIT has no general implication for TMs that are **not** generating statements of number theory. Really, this should not be that ahrd a concept to grasp. > [@](#): > > The point is, the undecidability of the halting problem says there is not way to know ahead of time how a given string will cause a given TM to behave. This is incorrect. The halting problem unsolveable for every specific case. The halting problem is a statemeng about generic halting algorithms. > [@](#): > > Some earlier posts seemed to me (again, it was 1 AM) to be trying to suggest that you could construct a physical machine that would accept every string, and only crash due a hardware failure This is correct. It is simple to conceive such a machine. [ul][li]Given any input: output 0 and halt[/ul][/li] > [@](#): > > The undecidability of the Halting Problem says to me that you could never prove that such a machine performs in such a way. You are not hearing what the halting problem is actually saying. > [@](#): > > [A good discussion of recursively enumerable languages] > . > . > . > Therefore, there is a class of languages that you CAN NOT build a TM (or by extension a UTM/computer) to accept. Because our brains CAN accept these languages, this seems to place an upper limit on the processing power of computers that will always be less than that of the brain. Well, it is a side issue, but one would first have to prove that human brains can “accept” these languages in a manner that is sufficiently similar to the CLW translation before that statement could be taken as correct. Then, of course, there are the implications of the fact that each language can, in fact, be accepted as input by “M” so merely showing that a human brain can acept the language does not actually provide a hard distinction form the class of UTMs. It is an interesting side discussion, though. > [@](#): > > There is a certain shared nature about these two quoted statements, that leads to the thinking mentioned in the OP (and other places where I have seen similar assertions. Similarity in method does not imply logical equivalence. The same is true of GIT and the halting problem. newton meter I compose replies as I read, so I just got to your post and see you have said everything that I am about to with far less “tape”. (Actually, **ultrafilter** covered many of the high points already, too.) Oh well. My algorithm says I should hit “submit” now regardless of input. 😃 ---
**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 16, 2003, 8:19pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/136 "2003-04-16T20:19:30Z")
I make plenty of typos, but this time I left out a rather important string: > [@](#): > > This is incorrect. The halting problem unsolveable for every specific case. The halting problem is a statemeng about generic halting algorithms. The halting problem _ **IS NOT** _ unsolveable for every specific case. The halting problem is a statemeng about generic halting algorithms. :smack: ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 9:08pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/137 "2003-04-16T21:08:57Z")
> [@](#): > > \*Originally posted by Spiritus Mundi \* > \*\*I have already said that I see no point in repeating an endless process of “No, it doesn’t” “Yes it does” statements with you. You are making statements in this htread that are factually incorrect. You are using terminology in a manner that is inconsistent with standard usage in the fields of computer science and mathematics. \*\* You’re not pointing out what statements you think are wrong and then demonstrating that they _are_ wrong – you’re simply denying my argument over and over again. My position is wrong because the statements I use to describe it are wrong, and the statements are wrong because my position is wrong. For example, you claim that the meta-grid that can be constructed with the standard grid of Life is as complex as the grid itself. This is not only incorrect, it’s **stupid**. However many resources are necessary to simulate a basic square, the resources for a meta-square are necessarily greater. I don’t know what the simplest possible pattern that emulates the unit square is, but at an absolute minimum, it cannot be less than two. Therefore the meta-grid takes at least twice as much memory to implement as the grid itself. The words I’m using all have well-defined meanings in standard English. If you can’t handle that, get off the boards. I’m quite serious – if you can’t rationally consider arguments made in everyday language, you have no place on boards where the arguments are presented in that format. > [@](#): > > **That depends upon what you mean by “model”, which is the question I have been asking you to answer.** A model is a system – a set of interactions – that manifests properties similar to those of another system. This is inherent in the dictionary definition of the word. > [@](#): > > **Apparently, you mean “can be described by the same mathematical equations”. Is that accurate?** I’m saying that, although the two systems exist on different level of implementation, their high-level behavior is the same. _They do the same things._ > [@](#): > > **This is an unspported assertion on your part. Actually, it is two unsupported assertiond.** It is not an assertion. It’s a consequence. If I say “A equals B, B equals C, so A equals C”, this is not an assertion either. It’s a consequence of the definition of equality; verifying this requires only substituting across equivalencies. The behavior of electrons is such that they can be used as the foundation of a system, on a higher level of implementation, that can perform arithmetic. Therefore their behavior necessarily can demonstrate statements about arithmetic. > [@](#): > > **Really. It is very important for you to answer specific questions if you expect anybody who understands GIT to think that your position is anything other than a SWAG without the S.** I have shown you the dots. You _should_ be sufficiently intelligent to be able to connect them yourself. > [@](#): > > **Element: a member of a set. In this case, an irreducible component part of a system. (What is irereducibvle, of course, alters with the level of analysis.)** Element: a basic component of a system. > [@](#): > > **See, it isn’t so hard. Now please define “model” and “complexity” as you use the terms.** Complexity: the amount of data required to perfectly define a system. This is a greatly condensed version of the general language definition of “complex”. > [@](#): > > \*\*An order N algorithm with 2 pieces of input has exactly the same complexity as an order N algorithm with 2 million pieces of input. \*\* The implementation of the algorithm is not equally complex in both cases! > [@](#): > > \*\*It serves no useful purpose for you to misuse terminology and then make pronouncements of fact based upon your variant meanings for words. \*\* I informed you quite a while ago that I’m communicating in the standard language. You’re the one that applies field-specific terminology inappropriately. > [@](#): > > \*\*Yes, but that is because of the rules we have encoded in the robot, not some fantasy that there is a limitation on what marks can ever be placed on a piece of paper because of GIT. \*\* \*The interaction between the writing implement and the piece of paper can be described by a system of basic rules. There will always be statements allowed by the grammar of the components of those rules that the rule system cannot reach. As a result, there will necessarily be possibilities that the implement-paper system cannot manifest on its own. No system designed to generate “new” statements according to a finite set of axioms will ever produce Godel’s famous statement. If it could do so, that set of steps would be a proof of the statement. The workings of the universe generate configurations according to basic axioms. Connect the dots. > [@](#): > > \*\*The only thing GIT tells us about marks on a paper is that there is no way to ever interpret marks on paper to be a proof of certain valid number theoretic statements **because no such proofs can exist.** This is a limitation of math, not a limitation of pencil and paper. \*\* The pencil and paper are being emulated by a deeper level of reality in the same way that a meta-grid is emulated by a grid in Life. They are necessarily limited! > [@](#): > > \*\*What you are saying is analagous to: **It’s impossible to write down the method for squaring a circle using geometric construction because the electrons are can’t move in a certain way.** No. > [@](#): > > \*\*By the way, “minimum” adds no meaning to the statement “resources required”. Anything that could be removed to “minimize” the set was obviously not required. _N’est ce pas?_ \*\* [sigh] The resources required to represent a specific pattern with the meta-grid are necessarily greater than the resources needed to represent that pattern with the basic grid. By the (inappropriate) definitions you’ve already offered, I conclude that you’re mistaken. > [@](#): > > \*\*This statement is simply and unambiguously false. > > Complexity is not a measure of information within a system. Outputing an input string is an algorithm of order N, no matter how many characters are in the string. Complexity is expressed as **a function of** the size of input. Please pay attention to the bolded part of that statemnet. Complexity==the function, not some value for the function given a specified input string. \*\* For the last time, **I AM NOT USING COMPUTER SCIENCE TERMINIOLOGY!** ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 9:13pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/138 "2003-04-16T21:13:24Z")
> [@](#): > > \*Originally posted by Newton meter \* > \*\*I don’t understand your little robot very well, so I’m going to go back to Turing Machines. Are you saying the there are certain strings that cannot ever be found on a Turing Machine’s tape, and that this is required by GIT? \*\* I’m saying that if the Turing Machine operates according to set rules, and those rules are sufficiently complex, there will be possible symbol configurations that the TM will never be able to reach. Different notations will result in different configurations of symbols, but the relationship between the notation and the configurations will be constant. ---
**Author:** ![TVAA](https://avatars.discourse-cdn.com/v4/letter/t/c57346/32.png) [@TVAA](https://boards.straightdope.com/u/TVAA)\ **Post date:** [April 16, 2003, 9:16pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/139 "2003-04-16T21:16:02Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*No, actually I’m claiming that being able to perform calculations is never important for theorem-proving. \*\* And this is where you err. Computers have been built to generate and verify theorems. Therefore, even if we don’t agree on the logic behind the incorrectness of your statement, we are forced to accept that you are incorrect. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [April 16, 2003, 9:22pm UTC](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157/140 "2003-04-16T21:22:38Z")
Wow, I would have never have suspected that Merriam Webster would resolve the problems I had understanding mathematics. Thanks, **Aide**! 😛 [Previous page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=6) [Next page](https://boards.straightdope.com/t/what-does-the-incompleteness-theorem-imply/168157.md?page=8)