Typically, Godel's Incompleteness theorems have been used to argue against the possibility that the human mind is essentially equivalent to a formal system. However, in Daniel Dennett's book "Darwin's Dangerous Idea", Dennett says "Hofstadter's classic 'Godel Escher Bach' can be read as the demonstration that Godel is an unwilling champion of AI, providing essential insights about the paths to follow to strong AI, not showing the futility of the field."

My question concerns the arguments that Hofstadter uses. Would someone be able to give me a brief description of one or two of Hofstadter's ideas about how to harness the Incompleteness theorems in order to support AI? I have seen a lot of (rather poor) arguments that invoke the theorems in order to oppose AI (e.g., Penrose's second argument), so it seems strange that someone could manage to use the same theorems for the opposite purpose.

  • doesn't Denney justify his statement with a note or a reference?
    – nir
    Apr 11, 2015 at 22:11
  • As far as I can tell, he just gives a reference to GEB as a whole. Apr 11, 2015 at 22:13
  • 3
    that would seem unfair; it's a 700 pages book...
    – nir
    Apr 11, 2015 at 22:18

2 Answers 2


Much of Gödel, Escher, Bach concerns the limitations of formal systems, the inherent difficulty of determining the locus of meaning, and the emergence of complex behaviours from simple components.

In Chapter XV, anti-mechanical arguments for human intelligence based on Gödel's Incompleteness Theorem are rejected, on the basis that humans are not special in being able to "Jump out of the system": not only are machines not incapable in principle, humans are given undue credit for their alleged ability to transcend any limitation. For if humans are not necessarily fixed to any one formal system that we are capable of percieving, this does not mean that we are not fixed to any system at all. Hofstadter argues that human intelligence and complexity of behaviour can be seen as an emergent consequences of the iteration and interaction of simple rules; of which, deciding membership of a point in a fractal, deciding theoremhood in a formal system, and the Halting Problem (the computational face of Gödel's Incompleteness Theorem) are also examples.

The other ideas on GEB make clear that Hofstadter does not believe that there is anything essential about human intelligence; that our behaviour may also be understood as complex consequences of the behaviour of simple components, much as the boundaries of provability are in formal systems themselves. His view on intelligence (human and otherwise) are entwined in a broader viewpoint about mathematics, knowledge, and complex systems — most pertinently in this case, that even the best and most celebrated fruits of human cognition are imperfect (and provably so!) from some inaccessible and imagined Platonic viewpoint; and that meaning and intelligence, if you assume they exist at all, may be inextricably a question of the interpreter, even (or especially!) from the most ardent physicalist standpoint.

Quoting from Chapter XV (excerpted for at least a degree of brevity):

The baffling repeatability of the Gödel argument has been used by various people — notably J. R. Lucas — as ammunition in the battle to show that there is some elusive and ineffable quality to human intelligence, which makes it unattainable by "mechanical automata" — that is, computers. Lucas begins his article "Minds, Machines, and Gödel" with these words:

Gödel’s theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines.

Then he proceeds to give an argument which, paraphrased, runs like this. For a computer to be considered as intelligent as a person is, it must be able to do every intellectual task which a person can do. Now Lucas claims that no computer can do "Gödelization" (one of his amusingly irreverent terms) in the manner that people can. Why not? Well, think of any particular formal system [...] One can write a computer program rather easily which will systematically generate theorems of that system, and in such a manner that eventually, any preselected theorem will be printed out. [...] We can anthropomorphically say that this program "knows" some facts of number theory-namely, it knows those facts which it prints out. If it fails to print out some true fact of number theory, then of course it doesn't "know" that fact. Therefore, a computer program will be inferior to human beings if it can be shown that humans know something which the program cannot know. Now here is where Lucas starts rolling. He says that we humans can always do the Gödel trick on any formal system as powerful as [number theory] — and hence no matter what the formal system, we know more than it does. Now this may only sound like an argument about formal systems, but it can also be slightly modified so that it becomes, seemingly, an invincible argument against the possibility of Artificial Intelligence ever reproducing the human level of intelligence. [...]

We must try to understand more deeply why Lucas says the computer cannot be programmed to "know" as much as we do. Basically the idea is :hat we are always outside the system, and from out there we can always perform the "Gödelizing" operation, which yields something which the program, from within, can't see is true. But why can't the "Gödelizing operator", as Lucas calls it, be programmed and added to the program as a third major component [of a computerized reasoning system], Lucas explains:

The procedure whereby the Gödelian formula is constructed is a standard procedure-only so could we be sure that a Gödelian formula can be constructed for every formal system. But if it is a standard procedure, then a machine should be able to be programmed to carry it out too [...] We might expect a mind, faced with a machine that possessed a Gödelizing operator, to take this into account, and out-Gödel the new machine, Gödelizing operator and all. [...] In a sense, just because the mind has the last word, it can always pick a hole in any formal system presented to it as a model of its own workings. The mechanical model must be, in some sense, finite and definite: and then the mind can always go one better.

I interrupt this excerpt to note that this "last word" remark smacks of a sort of privilege — the argument is that because the machine is the object and we are the subject scrutinising it from our lofty position, and it in no position to respond (in particular as it is not present for the discussion), we find that we are able to win the argument by default. Hints of this reading of the question of artificial intelligence through the lens of civil rights and systems of power is present in Turing's own article Computing Machinery and Intelligence, but of course from the opposing camp. A similar analogy to civil rights with regards to AI is made much more baldly in Hofstadter's parable of "Loocus the Thinker" later in this same chapter.

[...] the very fact that we cannot write a program to do "Gödelizing" must make us somewhat suspicious that we ourselves could do it in every case. It is one thing to make the argument in the abstract that Gödelizing "can be done"; it is another thing to know how to do it in every particular case. In fact, as the formal systems (or programs) escalate in complexity, our own ability to "Gödelize" will eventually begin to waver. It must, since, as we have said above, we do not have any algorithmic way of describing how to perform it. If we can't tell explicitly what is involved in applying the Gödel method in all cases, then for each of us there will eventually come some case so complicated that we simply can't figure out how to apply it. Of course, this borderline of one's abilities will be somewhat ill-defined, just as is the borderline of weights which one can pick up off the ground. While on some days you may not be able to pick up a 250-pound object, on other days maybe you can. Nevertheless, there are no days whatsoever on which you can pick up a 250-ton object. And in this sense, though everyone's Gödelization threshold is vague, for each person, there are systems which lie far beyond his ability to Gödelize. [...]

Now this is only one way to argue against Lucas' position. There are others, possibly more powerful, which we shall present later. But this counterargument has special interest because it brings up the fascinating concept trying to create a computer program which can get outside of itself, see itself completely from the outside, and apply the Gödel zapping-trick to itself. Of course this is just as impossible as for a record player to be able to play records which would cause it to break. But-one should not consider [number theory] defective for that reason. If there a defect anywhere, it is not in [number theory], but in our expectations of what it should he able to do. Furthermore, it is helpful to realize that we are equally vulnerable to the word trick which Gödel transplanted into mathematical formalisms [...] It is still of great interest to ponder whether we humans ever can jump out of ourselves [...] One can step out of ruts on occasion. This is still due to the interaction of various subsystems of one’s brain, but it can feel very much like stepping entirely out of oneself. Similarly, it is entirely conceivable that a partial ability to "step outside of itself" could be embodied in a computer program.

In short: if you discard the assumption that there is something inherently magical about the human capacity to do mathematics, and accept the premise that humans have a bounded capacity to reason, you quickly arrive at the conclusion that there is nothing obvious in Gödel's results (or indeed in any mathematics) which would prevent an artificial intelligence from accomplishing the sorts of feats of reason that we can.

  • Addendum. The same reasoning which applies to intelligent agents and their ability to reason, extends also to philosophy of mathematics. Gödel was a Platonist, and believed that his Incompleteness Theorem demonstrated that formal systems cannot fully capture Mathematical Truth. But the 'truth' of a Gödel sentence for a system A can only be demonstrated by a proof in the formal system B in which the incompleteness of A is demonstrated: it is established only in another formal system. Thus mathematical truth is only shown to transcend human activity, if it is assumed to do so from the outset. Apr 12, 2015 at 0:22
  • Of course, to fully embrace this position (and that described in my recent edit, of abandoning the hypothesis of a magical mathematical faculty in humans), you may have to discard Platonism as well. Even if there is a timeless mathematical world, if we lack any fantastical access to it, we are only capable of doing that mathematics which we can imagine and decide is most useful for our own interests (academic or practical) — i.e. a fundamentally humanist or utilitarian mathematics in place of transcendentalist mathematics. (As a Platonist, Gödel would of course not have advocated this view.) Apr 12, 2015 at 7:06

In GEB (and later in "I am a Strange Loop"), Hostadter states that human consciousness is due to the fact that the human mind is capable of perceiving itself. This capacity for self reference is analogous to the way Gödel sentences refer to themselves.

By the same logic, any dynamic system capable of processing symbols and complex enough to be able to refer to itself (i.e capable of representing and processing formal logic sentences up to and including Gödel sentences) can eventually develop self perception and consciousness.

The mechanism he describes for consciousness and self perception is based purely on formal logic. There is no reason why this ability should be limited to biological brains. In chapter 17, he states that any symbol system isomorphic to the brain's higher symbolic levels should be able to implement (strong) AI.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .