10

I've heard a lot of people say that Gödel's proof shows that human intelligence somehow goes beyond what a computer could ever do. It's only ever been articulated to me very badly, though not for want of trying. I agree with the conclusion for other reasons, but I just don't get what the argument pertaining to Gödel's proof is supposed to be.

  • The argument can't be that Gödel was capable of actually performing the nitty-gritty of proof where a computer cannot, because it has been proved algorithmically multiple times over the last 30 years.
  • The argument can't be that there are statements entailed in the proof that the computer wouldn't be able to also prove, because any statements entailed by Gödel's proof would be entailed by the computers.
  • The argument can't be that we can spontaneously use new true-but-unprovable statements as axioms because there's also nothing stopping us adopt any set of axioms we like, whether or not they are true or provable in any given system. The capacity for spontaneity, whilst interesting and no doubt significant for differentiating man from machine, does not seem at all specific to Gödel's proof.
  • The argument can't be that an algorithm couldn't think of the idea to attempt the proof, because this also isn't specific to Gödel's proof.

So what is it supposed to be?

Edit: Another way of asking this could be: What is the specific quality of Gödel's very complicated proof that is important for understanding cognition and that can't be demonstrated in another, simpler, way. The answer might be that there is nothing, but so many people insist there is something specific about Gödel's proof that has bearing on cognition that I feel the need to put this question out there.

Improve this question

3 Answers 3

Reset to default
7

About Gödel's incompleteness theorem, we need first to understand with reasonable precision what it states; see Torkel Franzén, Gödel's theorem An incomplete guide to its use and abuse (2005) :

First incompleteness theorem (Gödel-Rosser). Any consistent formal system S within which a certain amount of elementary arithmetic can be carried out is incomplete with regard to statements of elementary arithmetic: there are such statements which can neither be proved, nor disproved in S.

Key concepts are : formal system , consistency and "certain amount of elementary arithmetic".

About the first one :

In popular formulations of Gödel's theorem, a condition of this kind (as far as the axioms are concerned) [about the "mechanizability of reasoning in a formal system] is sometimes included in the form of a stipulation that the axioms of a formal system are finite in number. This implies that an axiom can ("in principle") be recognized as such by looking through a finite table. But this condition is not in fact satisfied by many of the formal systems studied in logic, such as PA and ZF. These systems have an infinite number of axioms, but it is still a mechanical matter to check whether or not a particular sentence is an axiom.

About "certain amount of elementary arithmetic", this idea can be made precise; roughly :

Any system whose language includes the language of elementary arithmetic, and whose theorems include some basic facts about the natural numbers, is certainly one that satisfies the condition.

What the theorem proves is that, under the above assumptions, we can "effectively" build up a formula G in the language of the formal system S (i.e. a formula "made of" numbers and operations on them, i.e. + and x) such that neither the above formula is provable in the system (i.e. derivable with the usual rules of inference from the axioms of the system), nor its negation not-G.

This "strange" formula is manufactured in a way that its "interpretation" is a true statement, because the formula "says of itself" that it is unprovable, and it is really unprovable; thus, if the system does work as we want, the formula must be true.

So what ? Gödel did not "made a calculation" that our algorithms are not able to perform. He made a mathematical proof, with the usual technique of mathematics : insight and reasoning.

What his theorem implies, about the topic we are discussing, is that the capability of mathematical logic of "reproducing" into a single formal system S working algorithmically the usual reasoning that the mathematical (i.e. human) mind is able to perform cannot be "zipped" into a single formal system.

In order to formalize the construction of Gödel's proof into a formal system, we have to build up a new (more powerful) system S'; but then, we may reproduce the construction of the above formula producing a new formula G' of S', and so on.

May we conclude about the inexhaustibility of our mathematical knowledge ? It seems so [see Franzén, page 56].

Improve this answer
4
  • Nice simple explanation after 'So what?' here. There seems to be a lot of wild talk around the incompleteness theorems, like what Lucas is skeptical about, or how Gödel would lead to 'post-Newtonian' views and whatnot. All I can see is a curiosity of logic, which looks relevant to maths, computer science, linguistics etc., but is 'fair enough' in itself. Yes: humans must make use of S' to parse the curious sentence G, and do. And so must artificial intelligences, and they do if you build them to do it? Is there more to it?
    – Diploria
    Mar 31, 2014 at 11:16
  • @Diploria - I strobgly agree with you; in general, it is a "dangerous" task trying to extract philosophical lessons form technical scientific results; often we obtain "wild" ideas taht are only sugegstions without scientific support.
    – Mauro ALLEGRANZA
    Mar 31, 2014 at 11:19
  • 1
    That book exists! Awesome title. I think following (So what?) you have managed to articulate the strongest possible valid claim that Godel's theorem makes about human intelligence. I don't think I should expect anything more. I do think some people want to say something even stronger, but I realise (in hindsight) that if it is indeed invalid to say anything stronger I don't have much chance of it being concretely expressed as an answer.
    – Lucas
    Mar 31, 2014 at 18:48
  • 1
    @Lucas - I agree with you: for me Franzén's book is the best book on this topic. Is a "divulgative" one, trying to be less technical as possible, but is complete at the same time avoiding errors and simplifications.
    – Mauro ALLEGRANZA
    Mar 31, 2014 at 19:26
2

Gödel's incompleteness theorem is often grossly misinterpreted when the subject of intelligence and artificial intelligence are discussed.

His theorem states that there are mathematical statements that cannot be either proven or disproven. A computer looking for a proof would fail to find one. A computer looking for a proof and not giving up would be stuck. But a brilliant mathematician looking for a proof would also fail to find one. And if that mathematician didn't give up, he or she would also be stuck forever.

He found that are problems that are impossible for any computer to solve. The same problems, however, are impossible for a human to solve as well. Some people seem to think that an unsolvable problem would cause problems for an artificial intelligence. But surely any artificial intelligence worth the name would be capable of figuring out that a problem is hard, too hard for it to solve, and then like humans would do the only recourse is to give up.

Improve this answer
1

You're right, that's not the best expression of Godel's result. His result is that there is no finitely axiomatizable theory of arithmetic. To unpack that some (but not all, because unpacking it all will make us be here a while an I haven't a Snickers), a "theory of arithmetic" is any set of sentences entailed by a first-order language together with a set of non-logical axioms which entail exactly the true arithmetic equalities. A "finitely axiomatizable" theory of arithmetic is any theory of arithmetic for which the set of non-logical axioms is finite in size.

If I were to put it in my own, near-as-I-can-to-natural-language expression, I would say: "If a computer were given any program designed to produce all and only the true arithmetic equalities, there would always be some true equality which it will systematically miss."

Improve this answer
5
  • I like your expression of the incompleteness theorem, and I think it is correct. I was however trying to get someone to give me a good version of the argument that gets bounced around about how humans are not restricted in this way. Phrased like that, it seems that saying "if I wrote an algorithm to enumerate all the natural numbers it would never give me a negative number" has exactly the same import.
    – Lucas
    Mar 31, 2014 at 2:57
  • Ah, that argument is harder. But the idea is: If you go through the proof, you actually construct the sentence that is not provable in the theory. And when you, as a human, look at that sentence, you can see that it is true. How? Can you discern (in principle) the truth of any godel-sentence? They can be very long and complex if you start looking for others down the line, but they all trade on the same "this sentence is not provable in this language," trick so it seems like we can. If so, then it seems like humans are not hardwired in some finitely-axiomatized way.
    – Addem
    Mar 31, 2014 at 3:00
  • 1
    But a computer can do the proof too. Although I could look at (a construction for) a Godel number and say, "that looks true", it's not proving it. If an experience of truthiness - being able to think something is true without proving it - is all that it's about, then you don't need Godels theorem, it's just obvious fact that you could demonstrate in many other simple ways.
    – Lucas
    Mar 31, 2014 at 3:24
  • Well, I suppose the point depends on you accepting that the ultimate test of a computer's "understanding" is printing statements, while the ultimate test of a human's understanding is exhibiting some conviction and capacity to explain. You may think that's a silly set of standards to accept--that it's nearly question-begging--but that is the argument as I understand it. (Not endorsing it.)
    – Addem
    Mar 31, 2014 at 3:53
  • I think you may be right about that being the argument. Put the way you did there's no nearly about it's question begging.
    – Lucas
    Mar 31, 2014 at 4:11

You must log in to answer this question.

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