Does Gödel's argument that minds are more powerful than computers have the inconsistency loophole?

Question

In "Raatikainen, P., 2005, “On the Philosophical Relevance of Gödel's Incompleteness Theorems,” , the author argues that Penrose's and others use of Gödel's theorem as an argument against mechanism (and presumably strong AI) - that minds are more powerful than computers because of human's ability to recognize the truth of Gödel sentences - are all flawed.

The basic error of such an argument is actually rather simply pointed out. The argument assumes that for any formalized system, or a finite machine, there exists the Gödel sentence (saying that it is not provable in that system) which is unprovable in that system, but which the human mind can see to be true. Yet Gödel’s theorem has in reality the conditional form, and the alleged truth of the Gödel sentence of a system depends on the assumption of the consistency of the system. That is, all that Gödel’s theorem allows us humans to prove with mathematical certainty, of an arbitrary given formalized theory F, is: F is consistent -> GF.

What he is saying here is that there is no guarantee that a formal system realized by a computer is consistent. Hence there's no guarantee that the Gödel sentences that humans recognize but computers don't are indeed themselves true, and human's aren't necessarily pulling off anything that a computer can't do.

My questions:

1. How could we possibly construct a computer that isn't consistent? It seems to me that any computer we build would be based on Turing Machines, which are themselves limited by Gödel theorem (via the halting problem).
2. Can a Turing machine generate an inconsistent formal system? Isn't anything generated by a Turing consistent by definition, since it's rules are contained in the Turing machine's memory?
3. And if this is the case, that Turing Machines can only generate consistent systems, then is Raatikainen's refutation of Penrose's and similar arguments false?

Answer 1

As such, Turing machines are not consistent or inconsistent - formalized systems are. However, once we fix a coding of (e.g.) the syntax of the language of arithmetic, we can view some Turing machines as enumerating the theorems of some formal systems (and every formalized system (its theorems) is enumerated by some machine). Then, when the coding kept fixed, it makes sense to call a machine, derivatively, "consistent" or "inconsistent".

Constructing an inconsistent Turing machine is then strikingly easy: define a machine which simply enumerates all sentences of the language: in particular, it lists a sentence and its negation (for every sentence).

Answer 2

For detailed discussions of the so-called Lucas-Penrose arguments, see :

• Torkel Franzén, Gödel's theorem : An incomplete guide to its use and abuse (2005), Ch.6 Gödel, Minds, and Computers, page 115-on

and

• Francesco Berto, There's Something about Gödel : The Complete Guide to the Incompleteness Theorem (2009), Ch.11 Mind versus Computer: Gödel and Artificial Intelligence, page 174-on.

Particularly relevant are the comments Gödel gave one of the prestigious Gibbs Lectures at the American Mathematical Society in 1951.

Gödel claimed that what the Theorems do entail (specifically, the Second Theorem) is that mathematics is inexhaustible:

It is this theorem [i.e., the Second Theorem] which makes the incompletability of mathematics particularly evident. For, it makes it impossible that someone should set up a certain well-defined system of axioms and rules and consistently make the following assertion about it: All of these axioms and rules I perceive (with mathematical certitude) to be correct, and moreover I believe that they contain all of mathematics. If someone makes such a statement he contradicts himself.

In the Gibbs Lecture, thus, Gödel acknowledged that [his theorems] do not rule out the existence of an algorithmic procedure (a computing machine, an automated theorem prover) equivalent to the mind in the relevant sense [...]. However, if such a procedure existed “we could never know with mathematical certainty that all the propositions it produce[d were] correct.” Consequently, it may well be the case that “the human mind (in the realm of pure mathematics) [is] equivalent to a finite machine that … is unable to understand completely its own functioning”: a machine too complex to analyze itself up to the point of establishing the correctness of its own procedures. Gödel inferred that what follows from the incompleteness results is, at most, a disjunctive conclusion:

Either mathematics is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the real of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable Diophantine problems of the type specified… It is this mathematically established fact which seems to me of great philosophical interest.

In other words, either the mind actually has a non-algorithmic and not fully “mechanizable” nature, or else there exist absolutely undecidable mathematical problems. But [Gödel's Theorems] don’t allow us to go further and conclude that the true disjunct is the first one. According to Gödel, then, what follows from [them], and especially from [the Second one], is that if our mind is a computing machine, it is one such that it “is unable to understand completely its own functioning.”

---

For further discussions, see :

• Solomon Feferman, Gödel, Nagel, minds and machines

and :

• Stewart Shapiro, Incompleteness, mechanism, and optimism.

---

Comment

I do not agree on statements like :

there exists the Gödel sentence (saying that it is not provable in that system) which is unprovable in that system, but which the human mind can see to be true.

Let assume some "technical" facts regarding Gödel's Incompleteness Theorems :

Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F

The unprovable statement is built-up in such a way that :

F ⊢ G ↔ ¬ProvF(⌈G⌉)

and the proof amounts to : :

if F is consistent, then F ⊬ G,

ff F is 1-consistent [or other condition, strictly "stronger" than consistency], then F ⊬ ¬G.

Up to now, we have only a "syntactical" result, about provability in a (suitable) formal system.

In order to speak of truth, we have to add the "semantical" side [see : Daniel Isaacson, Sufficient conditions undecidability of the Gödel sentence and its truth (2007)].

Assuming that the system F is sound with respect to truth in the structure of the natural numbers (called N), we have that :

F ⊬ G, G is true, and F ⊬ ¬G.

Proof

Assume F ⊢ G; then ProvF(⌈G⌉) and, by the condition F ⊢ G ↔ ¬ProvF(⌈G⌉), we have that G is false. Then, by soundness of F (i.e. F proves only true sentences) : F ⊬ G, contradicting our assumption that F ⊢ G. Thus, by propositional logic : F ⊬ G.

Again by the condition F ⊢ G ↔ ¬ProvF(⌈G⌉), we have that ¬ProvF(⌈G⌉) is true. But G ↔ ¬ProvF(⌈G⌉), and thus G is true

Then ¬G is false; so, by soundness of F : F ⊬ ¬G.

Conclusion : it is not a question of "seeing the truth of ...". We have a strict mathematical proof of a conditional :

"if F is sound, then the Gödel's sentence G (for F) is true".

Thus, the mathematical proof regarding the truth of G relies on assumptions. The basic assumption of the above proof is the soundness of the system F with regards to the natural numbers : a condition that is stronger than consistency.

In fact :

soundness implies consistency, while consistency is strictly weaker than soundness.

There are theories that are consistent but unsound; a simple example is : F ∪ {¬G}.

Answer 3

We can construct a computer that implements an inconsistent formal theory to which Gödel theorem does not apply just like we can construct a computer that implements Peano arithmetic. A simple example is Meyer's relevant arithmetic R# that allows some contradictions, but uses paraconsistent logic (without the law of explosion) to limit their effect. In R# Meyer was able to prove by finitary means that arithmetical calculations never produce contradictory results despite the presence of more abstract contradictions, not quite what Hilbert wanted, but more than consistent Peano arithmetic allows. Recently McKubre-Jordens and Weber extended R# to inconsistent analysis, there are other interesting inconsistent formal theories that can be implemented just like consistent ones.

However, one does not need inconsistency to question Gödelian arguments. Human "superpower" to recognize the truth of Gödel sentences derives from the non-mystical fact that they are provable in meta-theory, e.g. Gödel sentence for Peano arithmetic is provable in second order arithmetic. Of course, any effective proof theory for second order arithmetic will have its own Gödel sentence, provable in the next one, etc., and none of them can prove them all. But neither can any human. Constructing a Gödel sentence for an effectively axiomatized theory is also a perfectly algorithmic process (after Gödel).

So what this comes down to is the historically attested human ability to find new axioms and new forms of reasoning that were not formalized in advance. As humans "find" them however they disagree about their truth and validity. According to humans called intuitionists, Gödel sentences are not true (or false), and neither is the axiom of choice or even the law of excluded middle. The parallel postulate is only "approximately true" these days. "True" axioms are not so much "recognized" as picked up and adopted because they come handy. But why can't a fancy AI attached to a random number generator and with robotic parts to interact with "reality" do the same? There are already computer programs that generate conjectures, like Graffitti, and something like Prolog can already be used to find proofs for them too. Neural networks, simulated on computers, can "induce" new patterns by "learning", what's to stop them from "inducing" the parallel postulate?

What Gödelian arguments demonstrated so far is that their authors make presuppositions that imply their conclusions without any mediation from Gödel. We might as well say it straight: "history shows that humans can do what no computer can do in principle". Either you believe it or you don't, no theorem can prove or disprove it.

Franzen's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse is a canonical reference for dispelling the mythology surrounding Gödel's result.

Answer 4

Inconsistent systems are trivial to develop. The issue regarding inconsistent systems and strong AIs is that it is difficult for us to make a proof statement to prove that any specific AI is "strong," by whatever metric we choose. Mathematical consistency is important for all of our existing proving systems.

Accordingly, if the AI was developed using an inconsistent system, we have few tools available to intentionally make it "strong."

Making an inconsistent system is trivial. Simply create rules which conflict. For example, in programming, there is a very real issue that arises during the end of a process regarding reachable memory. Many languages (java, python, C#, to name a few, plus C++'s shared_ptr) have objects that give lifespan guarantees: as long as you hold a reference to the object, it has to stay around. However, you can come across situations where object A refers to object B and object B refers to object A -- a "reference cycle." If neither object stops referring to the other, they are provably eternal.

At least, they're eternal until the end of a process comes along, which came with its own consistency guarantees: "Processes can be terminated in a finite period of time" and "processes free all of their memory when they are terminated." So we have to break our own rule. There's a period of time at the end of a process where you can't guarantee that you're still pointing at something that's alive. In C++ in particular, this can result in situations that crash because you were promised one invariant (this object will outlive me), while another invariant conflicted (the process ended).

If you needed to adapt it into a Turing machine, simply seek to implement a Turing machine within a system which cannot actually implement all Turing machines "perfectly." The system is inconsistent, because it claims to be a Turing machine, while axioms defining the implementation contradict these claims.

Answer 5

You misunderstand consistency. Consistency is a concept defined for formal systems, which consists of both rules and strings of symbols. The rules govern exactly what strings belong to the formal system, which are said to be derivable within the formal system. Consistency just means that the formal system does not derive a contradiction, where contradiction is defined as some fixed string such as "0 ≠ 0". That's all.

A interpretation for a formal system is a mapping of each derived string in an unambiguous way to a truth value, which is in classical logic either "true" or "false". Also, a contradiction must be mapped to "false". A model is an interpretation that maps every derived string to "true". Necessarily, if a model exists for a formal system, then the formal system must be consistent.

Formal systems are commonly based on classical first-order logic, which specifies what strings are well-formed formulae, assertions that involve function symbols, predicate symbols, constant symbols, boolean operations and quantifiers. For any formal system obeying classical first-order logic whose rules are mechanically checkable and includes enough arithmetic (for example Robinson's arithmetic), there is some well-formed formula such that neither it nor its negation is derived by the formal system. This sort of formula is called independent.

The question is whether the human mind follows the rules of some formal system. If so, and the formal system includes enough arithmetic, and the formal system is consistent, then humans can prove that there is an independent sentence for it, specifically the Godel sentence for it (within a meta-system that proves the consistency of Peano Arithmetic), but can easily deduce in the meta-system that the sentence is true, which contradicts the assumption that the human mind is modeled by a formal system that does not derive the Godel sentence. There are various other independent sentences, but the reason for looking at the Godel sentence is that it is true in the meta-system (which can only be formalized by a formal system stronger than the one in question).

The issue here is whether the human mind follows the rules of some consistent formal system that includes enough arithmetic or not. The main problem is that consistency of a formal system is defined as whether a string is derivable, but human minds are not static, so it's not even clear how one should interpret consistency. I've not seen a very careful definition of this so far, but this seems to be the ultimate flaw in the argument, even if we accept consistency of PA.

Answer 6

Strong AI as people understand it today (that is, as emulating the same type of intelligence as a human being on our usual computers) is a hoax. It presupposes that our theories about nature (should I say existence itself?) are complete enough to describe what intelligence is and how to emulate it.

This is a big misunderstanding of physics and mathematics. For example, our theories of physics never presuppose that matter is more than just some bunch of inert things interacting without any form of consciousness or intelligence. This means that strong AI people strongly believe that consciousness and intelligence is an emerging thing. Yet, how could non-inert things like feelings, consciousness, and intelligence emerge out of something without any form of perceptions or life? That is, how could any form of perception exist in an inert world?

The physics we understand and use everyday would stay unchanged in a world without any perceptions: things would change purposelessly, without anybody (or even anything) noticing it.

Moreover, even without being a dualist, one has to notice that the very act of understanding (ideas, concepts, theories, or even each other) is part of nature. How could the very act of understanding be an inert thing? What about free will? Why would the universe exist at all if it were just some bunch of inert things, free from any form of perception or free will, evolving purposelessly and in an unnoticed way?

So, either "life" is part of every piece of matter (one could suppose that consciousness or perceptions are as fundamental as their inert counterparts) and therefore our scientific theories are highly incomplete to describe and understand what those things are, or strong AI people have to explain to us how perception could emerge from nothing at all. Good luck with the latter.

Now, even if there exists some "fundamental bit of consciousness or perception", this does not mean at all that we are able to understand it (that is, to theorize about it in a relevant way). Life is a pretty mysterious thing, and no biologist succeeded in creating it out of a non-living thing (with the usual definition of life here). That is, why would it even be possible to understand what life, consciousness, and perceptions are?

Being able to describe how they interact with the physical world and its inert part seems plausible, but a description is not an explanation. There are really good reasons to believe that it is forbidden to understand everything: if it were possible to understand everything, then it would also be possible to understand why it is so, up to infinity. Hence, it is much more humble and mature to believe that mysteries are all around us, and stop being that arrogant.

Obviously, one can still be able to achieve something by pure phenomenology without being able to explain why it works. That's very true, but then, why are strong AI people believing so strongly that life is nothing but a classical thing one can emulate with 0 and 1 when biologists have discovered a dynamical code inside every living thing called DNA? Isn't DNA the "true code" of consciousness and intelligence? In this respect, shouldn't strong AI people experiment manipulating DNA instead of wasting their time with classical logic and our classical theories of computation?

To finish, let me recall that strong AI people have been claiming for 50 years already that computers surpassing human beings are going to be here in the next decade. Their predictions keep failing, and I'm betting my life that they will keep failing if they don't change their paradigm: they are now-a-days not even able to emulate the brain of a bee or an ant.