Metamagical Themas, page 58
Lisp; it would have made the proof of his theorem much easier." I knew exactly what Minsky meant by that, I could see a grain of truth in it, and moreover I knew it had been made with tongue semi in cheek. Still, something about this remark drove me crazy. It made me itch to say a million things at once, and thus left me practically speechless. Finally today, after my seven-year itch, I will say some of the things I would have loved to say then.
What Minsky meant, paraphrased, is this: "Probably the hardest part of Godel's proof was to figure out how to get a mathematical system to talk about itself. This took several strokes of genius. But Lisp can talk about itself, at least in the sense Gödel needed, directly. So why didn't he just invent Lisp? Then the rest would have been a piece of cake." An obvious retort is that to invent Lisp out of the blue would have taken a larger number of strokes of genius. Minsky, of course, knew this, and at bottom, his remark was clearly just a way of making this very point in a facetious way.
Still, it was clear that Minsky felt there was some serious content to the remark, as well. (And I have heard him make the same remark since then, so I know it was not just a throwaway quip.) There was the implicit question, "Why didn't Gödel invent the idea of direct self-reference, as in Lisp?" And this, it seemed to me, missed a crucial point about Gödel’s work, which is that it showed that self-reference can crop up even where it is totally unexpected and unwelcome. The power of Gödel’s result was that it obliterated the hopes for completeness of an already known system, namely Russell and Whitehead's Principia Mathematica; to have destroyed similar hopes for some newly concocted system, Lisp-like or not, would have been far less significant (or, to be more accurate, such a result's significance would have been far harder for people to grasp, even if it were equally significant).
Moreover, Godel's construction revealed in a crystal-clear way that the line between "direct" and "indirect" self-reference (indeed, between direct and indirect reference, and that's even more important!) is completely blurry, because his construction pinpoints the essential role played by isomorphism (another name for coding) in the establishment of reference and meaning. Gödel’s work is, to me, the most beautiful possible demonstration of how meaning emerges from and only from isomorphism, and of how any notion of "direct" meaning (i.e., codeless meaning) is incoherent. In brief, it shows that semantics is an emergent quality of complex syntax, which harks back to my earlier remark in the Post Scriptum to Chapter 1, namely: "Content is fancy form." So the serious question implicit in Minsky's joke seemed to me to rest on a confusion about this aspect of the nature of meaning.
* * *
Now let me explain this in more detail. Part I of Gödel’s insight was to realize that via a code, a number can represent a mathematical symbol 11 e.g., the integer eleven can represent the left parenthesis, and the integer thirteen the right parenthesis 13. The analogue of this in human languages is the recognition that certain orally produced screeches or manually produced scratches (such as "word", "say", "language", "sentence", "reference", "grammar", "meaning", and so on) can stand for elements of language itself (as distinguished from screeches or scratches such as "cow" and "splash", which stand for extralinguistic parts of the universe). Here we have pieces of language talking about language. Maybe it doesn't seem strange to you, but put yourself, if you can, back in the shoes of barefoot cave people who had barely gotten out of the grunt stage. How amazingly magical it must have felt to the beings in whose minds such powerful concepts as words about words first sparked! In some sense, human consciousness began then and there.
But a language can't get very far in terms of self-reference if it can talk only about isolated symbols. Part II of Gödel’s insight was to figure out how the system (and here I mean Principia Mathematica "and", as Gödel’s paper's title says, "related systems") could talk about lists of symbols, and even lists of lists of symbols, and so on. In the analogy to human language, making this step is like the jump from an ability to talk about people's one-word utterances ("Paul Revere said `Land!'.") to the ability to talk about arbitrarily long utterances, and nested ones at that ("`Douglas Hofstadter wrote, "Paul Revere said, `Land!'."."').
Gödel found a way to have some integers stand for single symbols and others stand for lists of symbols, usually called strings. An example will help. Suppose the integer 1 stands for the symbol '0', and as I mentioned earlier, 11 and 13 for parentheses. Thus to encode the string "(0)" would require you to combine the integers 11, 1, and 13 somehow into a single integer. Gödel chose the integer 7500000000000-not capriciously, of course! This integer can be viewed as the product of the three integers 2048, 3, and 1220703125, which in turn are, respectively: 2", 3', and 5's. In other words, the three-symbol string whose symbols individually are coded for by 11 and 1 and 13 is coded for in toto by the single integer 2"3'5'3. Now 2, 3, and 5 are of course the first three primes, and if you want to encode a longer string, you use as many primes as you need, in increasing order. This simple scheme allows you to code strings of arbitrary length into large integers, and moreover-since large integers can be exponents just as easily as small ones can-it allows for recursive coding. In other words, strings can contain the integer codes for other strings, and this can go on indefinitely. An example: the list of strings "0", "(0)", and "((0))" is coded into the stupendously large integer
2213211315135211311517131113
The proverbial "astute reader" might well have noticed a possible ambiguity: How can you tell if an integer is to be decomposed via prime factorization into other integers or to be left alone and interpreted as a code for an atomic symbol? Gödel’s simple but ingenious solution was to have all atomic symbols be represented by odd integers. How does that solve the matter? Easy: You know you should not factorize odd integers, and conversely, you should factorize even ones, and then do the same with all the exponents you get when you do so. Eventually, you will bottom out in a bunch of odd integers representing atomic symbols, and you will know which ones are grouped together to form larger chunks and how those chunks are nested.
With this beautifully polished scheme for encoding strings inside integers and thereby inside mathematical systems, Gödel had discovered a way of getting such a system to talk-in code-about itself. He had snuck self-reference into systems that were presumed to be as incapable of self-reference as are pencils of writing on themselves or garbage cans of containing themselves, and he had done so as wittily as the Greeks snuck a boatload of unacceptable soldiers into Troy, "encoded" as one single large acceptable structure.
Historically, the importance of Godel's work was that it revealed a plethora of unexpected self-references (via his code, to be sure, but that fact in no way diminishes their effect) within the supposedly impregnable walls of Russell and Whitehead's Troy, Principia Mathematica. Now in Lisp, it's possible to construct and manipulate pieces of Lisp programs. The idea of quoted code is one of those deep ideas that make Lisp so appealing to Al people. Okay, but-when you have a system constructed expressly to have self-referential potential, the fact that it has self-referential structures will amaze no one. What is amazing and wonderful is when self-reference pops up inside the very fortress constructed expressly to keep it out! The repercussions of that are enormous.
One of the clear consequences of Gödel’s revelation of this self-referential potential inside mathematical systems was that the same potential exists within any similar formalism, including computer languages. That is simply because computers can do all the standard arithmetic operations-at least in theory-with integers of unlimited size, and so coded representations of programs are being manipulated any time you are manipulating certain large integers. Of course, which program is being manipulated depends on what code you use. It was only after Gödel’s work had been absorbed by a couple of generations of mathematicians, logicians, and computer people that the desirability of inserting the concept of quotation directly into a formal language became obvious. To be quite emphatic about it, however, this does not enhance the language's potential in any way, except that it makes certain constructions easier and more transparent. It was for this reason of transparency that Minsky made his remark.
Oh yes, I agree, Gödel’s proof would have been easier, but by the time Gödel dreamt it up, it would have long since been discovered (and called "Snoddberger's proof") had Gödel been in a mindset where inventing Lisp was natural. I'm all for counterfactuals, but I think one should be careful to slip things realistically.
* * *
After this diatribe, you will think I am crazy when I turn around and tell you: Gödel did invent Lisp! I am not trying to take anything away from John McCarthy, but if you look carefully at what Gödel did in his 1931 article, written roughly 15 years before the birth of computers and 27 years before the official birth of Lisp, you will see that he anticipated nearly all the central ideas of Lisp. We have already been through the fact that the central data structure of Lisp, the list, was at the core of Gödel’s work. The crucial need to be able to distinguish between atoms and lists-something that modern-day implementors of Lisp systems have to worry about-was recognized and cleverly resolved by Gödel, in his odd-even distinction. The idea of quoting is, in essence, that of the Gödel code. And finally, what about recursive functions, the heart and soul of Lisp programming technique? That idea, too, is an indispensable part of Gödel’s paper! This is the astounding truth.
The heart of Gödel’s construction is a chain of 46 definitions of functions, each new one building on previous ones in a dizzying spire ascending toward one celestial goal: the definition of one very complex function of a single integer, which, given any input, either returns the value 1 or goes into an infinite loop. It returns 1 whenever the input integer is the Gödel number -the code number-of a theorem of Principia Mathematica, and it loops otherwise. This is Gödel’s 46th function, which he named "Bew", short for "beweisbar", meaning "provable" in German.
If we could calculate the value of function 46 swiftly for any input, it would resolve for us any true-false question of mathematics that a full axiomatic system could resolve. All we would need to do is to write down the statement in question in the language of Principia Mathematica, code the resulting formula into its Godel number (the most mechanical of tasks), and then call function 46 on that number. A result of 1 means true, looping forever means false. Do I hear the astute reader protesting again? All right, then: If we want to avoid any chance of having to wait forever to find out the answer, we can encode the negation of the statement in question into its Gödel number as well, and also call function 46 on this second number. We'll let the two calculations proceed simultaneously, and see which one says `1'. Now, as long as Principia Mathematica has either the statement or its negation as a theorem, one of the two calls on function 46 will return 1, while the other will presumably spin on unto eternity.
How does function 46 work? Oh, easy-by calling function 45 many times. And how does function 45 work? Well, it calls functions 44 and others, and they call previously defined functions, some of which call themselves (recursion!), and so on and so forth-all of these complex calls eventually bottoming out in calls to absolutely trivial functions such as "S", the successor function, which returns the value 18 when you feed it the integer 17. In short, the evaluation of a high-numbered function in Gödel’s paper sets in motion the calling of one subroutine after another in a hierarchical chain of command, in precisely the same way as my function expand called numerous lower-level functions which called others, and so on. Gödel’s remarkable series of 46 function definitions is, in my book, the world's first serious computer program-and it is in Lisp. (The Norwegian mathematician Thoralf Skolem was the inventor of the study of recursive functions theoretically, but Gödel was the first person to use recursive functions practically, to build up functions of great complexity.)
It was for all these reasons that Minsky's pseudo joke struck my intellectual funnybone. One answer I wanted to make was: "I disagree: Gödel shouldn't have and couldn't have invented Lisp, because his work was a necessary precursor to the invention of Lisp, and anyway, he was out to destroy PM, not Lisp." Another answer was: "Your innuendo is wrong, because any type of reference has to be grounded in a code, and Godel's way of doing it involved no more coding machinery grounding its referential capacity than any other efficient way would have." The final answer I badly wanted to blurt out was: "No, no, no-Gödel did invent Lisp!" You see why I was tongue-tied?
* * *
One reason I mention all this about Gödel is that I wish to make some historical and philosophical points. There is another reason, however, and that is to point out that the ideas in Lisp are intimately related to the basic questions of metamathematics and metalogic, and these, translated into a more machine-oriented perspective, are none other than the basic questions of computability-perhaps the deepest questions of computer science. Michael Levin has even written an introduction to mathematical logic using Lisp, rather than a more traditional system, as its underlying formal system. For this type of reason, Lisp occupies a very special place inside computer science, and is not likely to go away for a very long time.
However ... (you were waiting for this, weren't you?), there is a vast gulf between the issues that Lisp makes clear and easy, and the issues that confront one who would try to understand and model the human mind. The way I see it is in terms of grain size. To me, the thought that Lisp itself might be "more conducive" to good Al ideas than any other computer language is quite preposterous. In fact, such claims remind me of certain wonderfully romantic but woefully antic claims I have heard about the Hopi language. The typical one runs something like this: "Einstein should just have invented Hopi; then the discovery of his theory of relativity would have been much easier." The basis for this viewpoint is that Hopi, it is said, lacks terms for "absolute time" in it. Supposedly, Hopi (or a language with similar properties) would therefore be the ideal language in which to speak of relativity, since absolute time is abandoned in relativity.
This kind of claim was first put forth by the outstanding American linguist Edward Sapir, was later polished by his student Benjamin Whorf, and is usually known these days as the Sapir-Whorf hypothesis. (I have already made reference to this view in Chapters 7 and 8 on sexist language and imagery.) To state the Sapir-Whorf thesis explicitly: Language controls thought. A milder version of it would say: Language exerts a powerful influence upon thought.
In the case of computer languages, the Sapir-Whorf thesis would have to be interpreted as asserting that programmers in language X can think only in terms that language X furnishes them, and no others. Therefore, they are strapped in to certain ways of seeing the "world", and are prevented from seeing many ideas that programmers in language L can easily see. At least this is what Sapir-Whorf would have you believe. I will have none of it!
I do use Lisp, I do think it is very convenient and natural in many ways, I do advocate that anyone seriously interested in AI learn Lisp well; all this is true, but I do not think that deep study of Lisp is the royal road to AI any more than I think that deep study of bricks is the royal road to understanding architecture. Indeed, I would suggest that the raw materials to be found in Lisp are to AI what raw materials are to architecture: convenient building blocks out of which far larger structures are made.
It would be ridiculous for anyone to hope to acquire a deep understanding of what Al is all about without first having a clear, precise understanding of what computers are all about. I know of no shorter cut to that latter goal than the study of Lisp, and that is one reason Lisp is so good for AI students. Beginners in Lisp encounter, and are in a good position to understand, fundamental issues in computer science that even some advanced programmers in other languages may not have encountered or thought about. Such concepts as lists, recursion, side effects, quoting and evaluating pieces of code, and many others that I did not have the space to present in my three columns, are truly central to the understanding of the potential of computing machinery. Moreover, without languages that allow people to deal with such concepts directly, it would be next to impossible to make programs of subtlety, grace, and multi-level complexity. Therefore I advocate Lisp very strongly.
It would similarly be next to impossible to build structures of subtlety, grace, and multi-level complexity such as the Golden Gate Bridge and the Empire State Building out of bricks or stone. Until the use of steel as an architectural substrate was established, such constructions were unthinkable. Now we are in a position to erect buildings that use steel in even more sophisticated ways. But steel itself is not the source of great architects' inspiration; it is simply a liberator. Being a super-expert on steel may be of some use to an architect, but I would guess that being quite knowledgeable will suffice. After all, buildings are not just scaled-up girders. And so it is with Lisp and Al. Lisp is not the "language of thought" or the `language of the brain"-not by any stretch of the imagination. Lisp is, however, a liberator. Being a super-expert on Lisp may be of some use to a person interested in computer models of mentality, but being quite knowledgeable will suffice. After all, minds are not just scaled-up Lisp functions.
Let me switch analogies. Is it possible for a novelist to conceive of plot ideas, characters, intrigues, emotions, and so on, without being channelled by her own or his own native language? Are the events that take place in, say, Anna Karenina specifically determined by the nature of the Russian language and the words that it furnished to Tolstoy? If that were the case, then of course the novel would be incomprehensible to people who do not know the Russian language. It would simply make no sense at all. But that is not even remotely the case. English-language readers have read that novel with great pleasure and have just as fully fathomed its psychological twists and turns as have Russian-language readers. The reason is that Tolstoy's mind was concerned with concepts that float far above the grain size of any human language. To think otherwise is to reduce Tolstoy to a mere syntactician, is to see Tolstoy as pushed around by low-level quirks and local flukes of his own language.
