Kurt Gödel’s incompleteness theorem came up in a debate the other night.  I usually react by hanging my head and groaning in anticipation of the chaos that eventually ensues. But on an impulse made a statement about the narrowness of its applicability in a vain attempt to avoid the conversation. It was futile. Chaos ensued.

The conversation really troubled me. Because I couldn’t defend it from memory. I couldn’t reconstruct the argument in my head.  I’ve spent time with the problem in computer science. So much so that it’s intuitive. But I could not remember how to reconstruct the salient part of the problem — the arithmetic requirement — so I couldn’t argue it. I had to go look it up again. And in doing so remembered why I can’t remember it: it’s complicated, and difficult if not impossible to reduce it to something more accessible. That’s why no one does it. 🙂 That’s why no one has done it.

Gödel’s theory is one of the most abused concepts referred to by people outside of professional mathematics. And when it is used, it’s almost guaranteed that it’s being used incorrectly. I suspect that’s because of the popularization of the idea by way of the liars paradox, which is then inappropriately applied elsewhere by analogy. But mostly it’s abused as an excuse to create arguments to defend mysticism in religion and avoidance in philosophy, and to justify any state of skepticism. Instead, it is in fact, a fairly narrow argument, related to axioms and number theory. ie: questions within axiomatic systems that are testable by the rules of arithmetic.

I do no better. I usually express it as “given any fixed axiomatic system, there are statements that are expressible that are contradictory to the claim of completeness.” Which itself is incomplete because the difficulty with Gödel’s theory is in describing its arithmetic requirements — and that description is complicated, which is why it’s never included in any definition, and by that omission leads to its spread by erroneous analogy.

This simplified definition is useful within computer science, because computers themselves are bound by Gödel’s arithmetic constraint in the first place — unlike mathematics, wherein he discussion of Gödel’s theorem must specifically address the arithmetic requirement in order for it to be narrow enough to be true.

So we have three categories of problems that help us understand Gödel’s theorem in the abstract even if the mathematical concepts are difficult to convey other than by examples that are difficult to construct: 1) the computational problem set which is by definition constrained, 2) the mathematical problem set which must be constrained, and 3) the linguistic problem which cannot be constrained. And philosophical questions are part of set 3 – impossible to constrain to arithmetic limits which are the reason incompleteness is imposed by the theorem.

The net result is that Godel’s theorem is, for all intents and purposes, never applicable to non-mathematical, non-computational propositions. Ever. But since, in casual debate, we break Godwin’s law in any conversation by mentioning Nazis about once an hour, then even if we created a new law: “The inclusion of Gödel in any philosophical discourse is sufficient proof that the argument is faulty”, we would still break it once a week. Because in the end, people of philosophical bent, are actually searching to fulfill their un-sated desire for mystical release from our inescapable requirement to reason and adapt to a constantly changing, and entirely kaleidic reality. 🙂

Here is a wonderful little criticism by From Cosma Shalizi, Assistant Professor, Carnegie Mellon University. And as such it is only an appeal to authority – again, because the proof is burdensome and inaccessible.

“There are two very common but fallacious conclusions people make from this, and an immense number of uncommon but equally fallacious errors I shan’t bother with. The first is that Gödel’s theorem imposes some some of profound limitation on knowledge, science, mathematics.

Now, as to science, this ignores in the first place that Gödel’s theorem applies to deduction from axioms, a useful and important sort of reasoning, but one so far from being our only source of knowledge it’s not even funny. It’s not even a very common mode of reasoning in the sciences, though there are axiomatic formulations of some parts of physics.

Even within this comparatively small circle, we have at most established that there are some propositions about numbers which we can’t prove formally. As Hintikka says, “Gödel’s incompleteness result does not touch directly on the most important sense of completeness and incompleteness, namely, descriptive completeness and incompleteness,” the sense in which an axiom system describes a given field.

In particular, the result “casts absolutely no shadow on the notion of truth. All that it says is that the whole set of arithmetical truths cannot be listed, one by one, by a Turing machine.” Equivalently, there is no algorithm which can decide the truth of all arithmetical propositions. And that is all.

This brings us to the other, and possibly even more common fallacy, that Gödel’s theorem says artificial intelligence is impossible, or that machines cannot think. The argument, so far as there is one, usually runs as follows. Axiomatic systems are equivalent to abstract computers, to Turing machines, of which our computers are (approximate) realizations. (True.) Since there are true propositions which cannot be deduced by interesting axiomatic systems, there are results which cannot be obtained by computers, either. (True.) But we can obtain those results, so our thinking cannot be adequately represented by a computer, or an axiomatic system. Therefore, we are not computational machines, and none of them could be as intelligent as we are; quod erat demonstrandum.

This would actually be a valid demonstration, were only the penultimate sentence true; but no one has ever presented any evidence that it is true, only vigorous hand-waving and the occasional heartfelt assertion.”

WEB

Recommended by Shalizi

  • Michael Arbib, Brains, Machines and Mathematics A
  • George S. Boolos and Richard C. Jeffrey, Computability and Logic [Textbook, with a good discussion of incompleteness results, along with many other things. Intended more for those interested in the logical than the computational aspects of the subject — they do more with model theory than with different notions of computation, for instance — but very strong all around.]
  • Torkel Franzen, Gödel’s on the net [Gentle debunking of many of the more common fallacies and misunderstandings]
  • Jaakko Hintikka, The Principles of Mathematics Revisited [Does a nice job of defusing Gödel’s theorem, independently of some interesting ideas about logical truth and the like, about which I remain agnostic. My quotations above are from p. 95]
  • Dale Myers, Gödel’s Incompleteness Theorem A
  • Roger Penrose, The Emperor’s New Mind [Does a marvelous job of explaining what goes into the proof — his presentation could be understood by a bright high school student, or even an MBA — but then degenerates into an unusually awful specimen of the standard argument against artificial intelligence]
  • Willard Van Orman Quine, Mathematical Logic [Proves a result which is actually somewhat stronger than the usual version of Gödel’s theorem in the last chapter, which however adds no philosophical profundity; review]
  • Raymond Smullyan, Gödel’s Incompleteness Theorems A
  • To read:
  • John C. Collins, “On the Compatibility Between Physics and Intelligent Organisms,” physics/0102024 [Claims to have a truly elegant refutation of Penrose]
  • Rebecca Goldstein, Incompleteness [Biography of Gödel, which seems to actually understand the math]
  • Ernest Nagel and James R. Newman, Gödel’s Proof [Thanks to S. T. Smith for the recommendation]
  • Mario Rabinowitz, “Do the Laws of Nature and Physics Agree About What is Allowed and Forbidden?” physics/0104001