Gödel, Escher, Bach: An Eternal Golden Braid (104 page)

There is no reason to believe that a. computer's faultlessly functioning hardware could not support high-level symbolic behavior which would represent such complex states as confusion, forgetting, or appreciation of beauty. It would require that there exist massive subsystems interacting with each other according to a complex "logic". The overt behavior could appear either rational or irrational; but underneath it would be the performance of reliable, logical hardware.

More Against Lucas

Incidentally, this kind of level distinction provides us with some new fuel in arguing against Lucas. The Lucas argument is based on the idea that Gödel’s Theorem is applicable, by definition, to machines. In fact, Lucas makes a most emphatic pronunciation:

Gödel’s theorem must apply to cybernetical machines, because it is of the essence of being a machine, that it should be a concrete instantiation of a formal system.°

This is, as we have seen, true on the hardware level-but since there may be higher levels, it is not the last word on the subject. Now Lucas gives the impression that in the mind-imitating machines he discusses, there is only one level on which manipulation of symbols takes place. For instance, the Rule of Detachment (called "Modus Ponens" in his article) would be wired into the hardware and would be an unchangeable feature of such a machine. He goes further and intimates that if Modus Ponens were not an immutable pillar of the machine's system, but could be overridden on occasion, then: The system will have ceased to be a formal logical system. and the machine will barely qualify for the title of a model for the mind.10

Now many programs which are being developed in At research have very little in common with programs for generating truths of number theory--programs with inflexible rules of inference and fixed sets of axioms. Yet they are certainly intended as "models for the mind". On their top level the "informal" level-there may be manipulation of images, formulation of analogies, forgetting of ideas, confusing of concepts, blurring of distinctions, and so forth. But this does not contradict the fact that they rely on the correct functioning of their underlying hardware as much as brains rely on the correct functioning of their neurons. So At programs are still "concrete instantiations of formal systems"-but they are not machines to which Lucas' transmogrification of Gödel’s proof can be applied. Lucas' argument applies merely to their bottom level, on which their intelligence-however great or small it may be-does not lie.

There is one other way in which Lucas betrays his oversimplified vision of how mental processes would have to be represented inside computer programs. In discussing the matter of consistency, he writes

If we really were inconsistent machines, we should remain content with our inconsistencies, and would happily affirm both halves of a contradiction. Moreover, we would be prepared to say absolutely anything-which we are not. It is easily shown that in an inconsistent formal system everything is provable."

This last sentence shows that Lucas assumes that the Propositional Calculus must of necessity be built into any formal system which carries out reasoning. In particular, he is thinking of the theorem <<
PA-P>DQ>
of the Propositional Calculus; evidently he has the erroneous belief that it is an inevitable feature of mechanized reasoning. However, it is perfectly plausible that logical thought processes, such as propositional reasoning, will emerge as
consequences
of the general intelligence of an At program, rather than being
preprogrammed
. This is what happens in humans! And there is no particular reason to assume that the strict Propositional Calculus, with its rigid rules and the rather silly definition of consistency that they entail, would emerge from such a program.

An Underpinning of Al

We can summarize this excursion into level distinctions and come away with one final, strongest version of the Church-Turing Thesis:

CHURCH-TURING THESIS, At VERSION: Mental processes of any sort can be simulated by a computer program whose underlying language is of

power equal to that of FlooP-that is, in which all partial recursive functions can be programmed.

It should also be pointed out that in practice, many AI researchers rely on another article of faith which is closely related to the CT-Thesis, and which I call the AI
Thesis
. It runs something like this:

AI THESIS:

As the intelligence of machines evolves, its underlying

mechanisms will gradually converge to the mechanisms underlying human intelligence.

In other words, all intelligences are just variations on a single theme; to create true intelligence, At workers will just have to keep pushing to ever lower levels, closer and closer to brain mechanisms, if they wish their machines to attain the capabilities which we have.

Church's Theorem

Now let us come back to the Crab and to the question of whether his decision procedure for theoremhood (which is presented in the guise of a filter for musical beauty) is compatible with reality. Actually, from the events which occur in the Dialogue, we have no way of deducing whether the Crab's gift is an ability to tell theorems from nontheorems, or alternatively, an ability to tell true statements from false ones. Of course in many cases this amounts to the same thing but Gödel’s Theorem shows that it doesn't always. But no matter: both of these alternatives are impossible, if you believe the At Version of the Church-Turing Thesis. The proposition that it is impossible to have a decision procedure for theoremhood in any formal system with the power of TNT is known as Church's Theorem. The proposition that it is impossible to have a decision procedure for number theoretical truth-if such truth exists, which one can well doubt after meeting up with all the bifurcations of TNT-follows quickly from Tarski's Theorem (published in 1933, although the ideas were known to Tarski considerably earlier).

The proofs of these two highly important results of metamathematics are very similar. Both of them follow quite quickly from self-referential constructions. Let us first consider the question of a decision procedure for TNT-theoremhood. If there were a uniform way by which people could decide which of the classes "theorem" and

"nontheorem" any given formula X fell into, then, by the CT-Thesis (Standard Version), there would exist a terminating FlooP program (a general recursive function) which could make the same decision, when given as input the Gödel number of formula X. The crucial step is to recall that any property that can be tested for by a terminating FlooP

program is represented in TNT. This means that the property of TNT-theoremhood would be represented (as distinguished from merely expressed) inside TNT. But as we shall see in a moment, this,

would put us in hot water, for if theoremhood is a representable attribute, then Gödel’s formula G becomes as vicious as the Epimenides paradox.

It all hinges on what G says: "G is not a theorem of TNT". Assume that G were a theorem. Then, since theoremhood is supposedly represented, the TNT-formula which asserts "G is a theorem" would be a theorem of TNT. But this formula is -G, the negation of G, so that TNT is inconsistent. On the other hand, assume G were not a theorem. Then once again by the supposed representability of theoremhood, the formula which asserts

"G is not a theorem" would be a theorem of TNT. But this formula is G, and once again we get into paradox. Unlike the situation before, there is no resolution of the paradox.

The problem is created by the assumption that theorernhood is represented by some formula of TNT, and therefore we must backtrack and erase that assumption. This forces us also to conclude that no FlooP program can tell the Gödel numbers of theorems from those of nontheorems. Finally, if we accept the Al Version of the CT-Thesis, then we must backtrack further, and conclude that no method whatsoever could exist by which humans could reliably tell theorems from nontheorems-and this includes determinations based on beauty. Those who subscribe only to the Public-Processes Version might still think the Crab's performance is possible; but of all the versions, that one is perhaps the hardest one to find any justification for.

Tarski's Theorem

Now let us proceed to Tarski's result. Tarski asked whether there could be a way of expressing in TNT the concept of number-theoretical truth. That theoremhood is expressible (though not representable) we have seen; Tarski was interested in the analogous question regarding the notion of truth. More specifically, he wished to determine whether there is any TNT-formula with a single free variable
a
which can be translated thus:

"The formula whose Gödel number is a expresses a truth."

Let us suppose, with Tarski, that there is one-which we'll abbreviate as TRUE{a}. Now what we'll do is use the diagonalization method to produce a sentence which asserts about itself that it is untrue. We copy the Godel method exactly, beginning with an "uncle": 3a:<-TRUE{a}nARITHMOQUINE{a",a}>

Let us say the Gödel number of the uncle is t. We arithmoquine this very uncle, and produce the Tarski formula T:

3a:<--TRUE{a}AARITHMOQUINE{SSS ... SSSO/a",a}>

t S's

When interpreted, it says:

"The arithmoquinification of t is the

Gödel number of a false statement."

But since the arithmoquinification of t is T's own Gödel number, Tarski's formula T

reproduces the Epimenides paradox to a tee inside TNT, saying of itself, "I am a falsity".

Of course, this leads to the conclusion that it must be simultaneously true and false (or simultaneously neither). There arises now an interesting matter: What is so bad about reproducing the Epimenides paradox? Is it of any consequence? After all, we already have it in English, and the English language has not gone up in smoke.

The Impossibility of the Magnificrab

The answer lies in remembering that there are two levels of meaning involved here. One level is the level we have just been using; the other is as a statement of number theory. If the Tarski formula T actually existed, then it would be a statement about natural numbers that is both true and false at once! There is the rub. While we can always just sweep the English-language Epimenides paradox under the rug, saying that its subect matter (its own truth) is abstract, this is' not so when it becomes a concrete statement about numbers! If we believe this is a ridiculous state of affairs, then we have to undo our assumption that the formula TRUE{a} exists. Thus, there is no way of expressing the notion of truth inside TNT. Notice that this makes truth a far more elusive property than theoremhood, for the latter is expressible. The same backtracking reasons as before (involving the Church-Turing Thesis, Al Version) lead us to the conclusion that The Crab's mind cannot be a truth-recognizer any more than it is a TNT-theorem-recognizer.

The former would violate the Tarski-Church-Turing Theorem ("There is no decision procedure for arithmetical truth"), while the latter would violate Church's Theorem.

Two Types of Form

It is extremely interesting, then, to think about the meaning of the word "form" as it applies to constructions of arbitrarily complex shapes. For instance, what is it that we respond to when we look at a painting and feel its beauty? Is it the "form" of the lines and dots on our retina? Evidently it must be, for that is how it gets passed along to the analyzing mechanisms in our heads-but the complexity of the processing makes us feel that we are not merely looking at a two-dimensional surface; we are responding to some sort of inner meaning inside the picture, a multidimensional aspect trapped somehow inside those two dimensions. It is the word "meaning" which is important here.

Our minds contain interpreters which accept

two-dimensional patterns and then "pull" from them high-dimensional notions which are so complex that we cannot consciously describe them. The same can be said about how we respond to music, incidentally.

It feels subjectively that the pulling-out mechanism of inner meaning is not at all akin to a decision procedure which checks for the presence or absence of some particular quality such as well-formedness in a string. Probably this is because inner meaning is something which reveals more of itself over a period of time. One can never be sure, as one can about well-formedness, that one has finished with the issue.

This suggests a distinction that could be drawn between two senses of "form" in patterns which we analyze. First, there are qualities such as well-formedness, which can be detected by predictably terminating tests, as in BlooP programs. These I propose to call syntactic qualities of form. One intuitively feels about the syntactic aspects of form that they lie close to the surface, and therefore they do not provoke the creation of multidimensional cognitive structures.

By contrast, the
semantic
aspects of form are those which cannot be tested for in predictable lengths of time: they require
open-ended tests
. Such an aspect is theoremhood of TNT-strings, as we have seen. You cannot just apply some standard test to a string and find out if it is a theorem. Somehow, the fact that its meaning is involved is crucially related to the difficulty of telling whether or not a string is a TNT-theorem. The act of pulling out a string's meaning involves, in essence, establishing all the implications of its connections to all other strings, and this leads, to be sure, down an open-ended trail. So