A Computer Proving
All Mathematical Truths :
Supporting the AI Thesis⁽¹⁾

As the main findings this paper establishes the following claims:

1. Gödel's Incompleteness Theorems cannot prove the existence or the non-existence of a machine proving all mathematical truths.

2. There exists a machine proving all mathematical truths.

3. The AI thesis is correct.

1. Introduction

Fundamental to the ambitions of Artificial Intelligence (AI) as a typical example of the step from logical foundations to technology is a thesis of Computational sufficiency, the view that Searle[5] calls "Strong AI": that there exists a class of abstract computations (programs, algorithms, automata) such that implementation of any computation in that class suffices for mentality.

There is another version of article of faith on which many AI researchers rely. It is the so called AI thesis, running like this.

AI THESIS As the intelligence of machines evolves, its underlying mechanisms will gradually converge to the mechanisms underlying human intelligence.

Even though over the last three or four decades AI has produced some practically useful machines, it is generally conceded that the ultimate goal is still distant. Is the goal of AI, which relies on what real time computers can do. Some people, like Penrose, seem to think that Gödel's result counts as evidence that Strong AI is impossible.

I am suspicious of many claims made in this area. There is a long literature on this beginning with a paper J. R. Lucas [3]. Many responses to Lucas argument (that Gödel showeed that mechanism about the mind is false) have appeared but the matter has never been fully cleared up as far as I know.

In this paper I consider the question whether minds can do more than computers, mostly using the realm of logic and mathematics as the test case. Specifically, my topic will be centered around the following question: Can there exist a computer proving all mathematical truths?

This problem is important because of its relevance to the relation between the two conceptual schemes of mind, thought and reasoning on the one hand, and of computers, programs and computation on the other.

next page

contents

In establishing an affirmative answer to this question, I will be justified in arguing that the AI thesis is correct and is neither supported nor precluded by the limitative Gödel's Theorems, and this leads to the central point of the present paper.

2. Preliminaries

First, I comment on notations. For the most part, my notation will be that commonly employed in mathematical logic.

We write F Ă S to mean that "S is the theorem of F". w-con( S) stands for " S is w-consistent".

In 1931 Gödel proved that a set of sentences containing Peano Arithmetic (PA) is incomplete [2]. Formally stated,

Gödel's First Incompleteness Theorem (G1): " G ( G: w-consistent axiomatizable extension of PA ® $ j( G ŘĂ j Ů G Ř Ă Ř j)).

G1 does not by itself say that some unprovable truths of arithmetic exist. Let me call the latter claim G1'. G1' can be derived as follows

Proof (just for reference) m is self-applicable ş m = g (A(x)) Ů G Ă A(m*), where A(x) a formula and g is Gödel numbering. B(x) ş x is not self-applicable. Assume n ş g (B(x)) is self-applicable. Then B(n*) false Ů G Ă B(n*), a contradiction. Thus n is not self-applicable. Hence B(n*) true Ů G  ŘĂ B(n*).

G1 predicates a simple syntactic property and is separable from the question of truth of arithmetic as in G1'. This is one of the beautiful aspects G1 has. G1' in its turn means that we cannot fully formalize our own mathematical capacity because it is part of that mathematical capacity itself that it can go beyond whatever it can formalize. I.e. it suggests the so-called mechanical inexhausitibility of mathematics.

Next,

Gödel's Second Incompleteness Theorem (G2): Let S be any consistent formal system adequate for recursive number theory. Then S cannot prove its own consistency.

previous page

next page

contents

Now let me consider the question: What connection is there between G1/G2 and the nature of mind and computer?

Throughout his life Gödel looked for good reasons which would justify the most spectacular conclusion that has been drawn from G1: Minds are not Computers.

In Gödel s opinion (as set forth in unpublished 25th Josiah Willard Gibbs Lecture delivered by him at Providence on December 26,1951) the following disjunction D holds:

D Either the human mind surpasses all machines (to be more precise: it can decide more number theoretical questions than any machine) or else there exist number theoretical questions undecidable for the human mind.

For a rigorous justification of D, I start with:

Notation 1 (1) M: The human mind

(2) C: Computer

(3) M ş C means "M is equivalent to C"

(4) Cm: a particular computer

(5) C Ł M means "computer cannot decide more number theoretical questions than the human mind"

Proof of D ( "C,C<M) Ú ( $Cm (MŁCm)) « ( " C, C<M) Ú ((i) $ Cm(M ş Cm Ú
(ii) M<Cm))

case(i): M ş Cm ŘĂ con(Cm), by G2

Thus, there exists a number theoretical question undecidable for M.

case(ii): Obviously,the same conclusion follows as in case (i).

Remark 2 (1) To formalize D and its proof more precisely, it is worthwhile to work towards an exact definition or theory of M. Note that if M is to mean the collection of minds of all human beings in the past, present, and future, M is not finitely describable.

(2) D can be restated roughly in two ways:

(i) "either the human mind is more than a machine or mathematics greater than the human mind."

(ii) "either mind or mathematics is incomplete."

previous page

next page

contents

(3) Wang is critical of Webb's argument that G1/G2 are for rather than against mechanism [6].

(4) Gödel finds Turing's attempted proofs for the equivalence of mind and machine to be fallacious. In particular, Gödel is critical of Turing's assumption that we do not have enough room in our heads for our mental processes to be governed by an unbounded operator. This neglects growth of our intellectual equipment.

(5) Turing invented the imitation game only as a way of asking the question `Can machines think?' But it turns out to be so powerful that it is really asking: `Can machines think exactly like human beings?' The Turing Test provides a sufficient condition for human intelligence but does not address the more important issue of intelligence in general. Further research for its descendants to test for true artificial intelligence,and perhaps even consciousness is needed.

3. A Machine Proving All Mathematical Truths

As D shows that humans are good at mathematizing things which Turing machines can't accomplish, it is natural to ask: Can there exist a computer to rival mathematicians? This is answered by:

Proposition 3 If a computer proving all mathematical truths exists, its existence is unprovable in a system in question.

Proof Let C exist as such a finitely describable computer that is equivalent to human consistent mathematical intuition (mind) M. Then M ş C ŘĂ con(C), by G2.

Since in mathematics consistency ensures existence, the existence of such a computer is unprovable in C(or M) (Otherwise, con(C) would be provable in C, a contradiction.)

Corollary 4 (1) Gl/G2 cannnot prove the existence or the non-existence of a computer proving all mathematical truths.

(2) As a process of mathematical intuition can be thought of as a process of perception, G1/G2 do not preclude the possibility or the impossibility that computers will be able to reason as well as humans.

previous page

next page

contents

Finally, the question arises: Can one ever build such a computer?

Further to Remark 2 (4) which is independent of G1 or G2, any

sequence of subsequent (conscious or unconscious) states of mind can grow if the capacity of the mind grows.

Despite Proposition 3, this motivates and inspires me to present:

Proposition 5 There exists a machine proving all mathematical truths.

Reason I can present two reasons as evidence for the truth of Proposition 5 as follows:

(1) As mind M can be assumed - for all the statements below - to be infinite species as an evolving society of human mathematicians one can by invoking von Neumann's theory self-reproducing automata [4], build a society of machines C_i (i: natural numbers), each C_i capable of producing factories to build other machines,such that C_i<C_i+1 for each i.

Now define: M' = { j | M can ever perceive j as truths }

C_i' = { j | C_i Ă j}

And recall Berry's Paradox: Consider the expression "the least natural number not nameable in fewer than twenty-two syllables. "This expression names a definite natural number, say n, since each non-empty set of natural numbers (in this case, the set of natural numbers not nameable in fewer than twenty-two syllables) has a least element. Thus n is not nameable in fewer than twenty-two syllables. But our expression naming n has in fact exactly twenty one syllables!

Invoking this n, the proof of the first case of D can be based on the following argument:

" i(i<n Ů C'_i Í M' ® con(C_i) Î M') but con(C_i) Ď C_i , by G2.

i.e., M' ą C'_i, " i<n.

However as one can reason that the limitative G2 concerns only C_i with (i<n) and the sequence {C_i} is monotonically growing in terms of capacity, the infinitely describable C_i with (i łn) can eventually have the property C'_i = M' and thus can prove all truths that M can perceive through M's mathematical intuitions.

previous page

next page

contents

(2) To provide as analogy additional evidence for Proposition 5, if might seem worth modifiying the definition of "formally undecidable" as follows.

Definition j is absolutely undecidable « [ " G ( G: w-consistent axiomatizable extension
of PA ® G ŘĂ j Ů G ŘĂ Ř j)]

Then one obtains

Theorem There exists no absolutely undecidable sentence j.

Proof Let us take as a definition of w-inconsistency the following: G is w-inconsistent, if $ j with G Ă j(n), " n Î N Ů G Ă $ x, Ř j(x). Note that if G is w-consistent and

N Ć j, then G Č { j} is w-consistent. Hence, suppose j is absolutely undecidable, i.e. for all G Ę PA, G: w-consistent, have G ŘĂ j and G ŘĂ Ř j. Without loss, take j with N Ć j and consider G:=PA Č { j}. Then, G is w-consistent, G Ę PA, and G Ă j. Thus there are no absolutely undecidable j unless PA is not w-consistent.

Remark 6 (1) This Theorem is reminiscent of Hilbert's optimism expressed in his words at the Second International Congress of Mathematicians in Paris, August 8,1900, "In Mathematics there is no ignorabimus",in fact, it is consistent to assume that any problem is solvable.

(2) In view of Propositions 3 and 5, such a machine's existence as an unprovable truth is also reminiscent of the Gödel sentence, true but unprovable in a system in question.

(3) Regarding questions about consciousness of central importance to AI, I share some ideas with Chalmers [1] and Hofstadter. In his Ph.D thesis, Chalmers proposed to introduce the notion of a combinatorial state automaton (CSA),a very general abstract computational object, and give an account of the conditions under which a given CSA is implemented. Roughly, the idea is that a physical system implements a computation if the causal state-transitional structure of the system mirrors the formal state-transitional structure of the computation.

previous page

next page

contents

This account of computation and implementatin combines naturally with the functional invariance thesis to support the strong AI thesis.

4. Conclusions

The consequences of the present research are:

First, the chasm between the two conceptual schemes of mind and of computer will have been bridged.

Second, the AI-ers can work more comfortably and simply continue to push to ever lower levels, getting closer and closer to mechanisms underlying the human mind.

Ceteris paribus, the mind can eventually be presented mechanically.

Chuang Tzu wrote, there is a limit to our life, but to knowledge there is no limit. I may rephrase it this way:

There is a limit to our brains, but to AI there is no limit.

REFERENCES

[1] Chalmers,D.J. "A Computational foundation for the study of Cognition", Minds and Machines(1994), forthcoming.

[2] Gödel,K. "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monash. Math. Phys.38 (1931), 173-198, transl.in Collected works, volume I, Oxford University Press(1986) 145-195.

[3] Lucas,J.R. "Minds, Machines and Gödel", Philosophy,36 (1961), 112-127.

[4] Von Neumann,J. "Theory of Self-Reproducing Automata", Urbana: University of Illinois Press(1966).

[5] Searle, J.R. "Minds, Brains, and Programs", Behavioral and Brain Sciences 3 (1980) 417-457.

[6] Wang,H. "Computer Theorem proving and Artificial Intelligence", reproduced in Computation, Logic, Philosophy, Kluwer Academic Pub.(1990).

NOTES:

1. Presented at the Institute of Robotics, ETH Zürich. I would like to acknowledge DAAD grant. I also would like to thank the logicians at the University of Bonn as well as Selmer Bringsjord and Otto Wilhelms Carls for discussions that inspired me to write this paper.

AMS Subject Classifications: 03B35, 03D10

previous page

contents