 |
| Douglas R. Hofstadter's Gödel, Escher, Bach |
That odd phrase reflects Hofstadter's fascination with processes of thought that not only circle back on themselves ad infinitum, but do so in such a way as to create paradox. When Epimenides, a Cretan, said "All Cretans are liars," he introduced just such a strange loop into the human thought stream (see p. 17).
Under the assumption that Epimenides meant "All Cretans always lie," i.e., "No Cretan ever tells the truth," we extrapolate from the fact that Epimenides himself is a Cretan, and therefore presumably a perennial liar, that the truth is in fact that "All Cretans are truth-tellers," i.e., "No Cretan ever tells a lie."
But we're applying Epimenides's statement to Epimenides himself in such a way as to cast him as a lying Cretan from the get-go. Hence it's not true that no Cretan ever lies. Given that either all Cretans always lie or no Cretans ever lie — the fuzzy middle ground is excluded by the crisp rules of this particular game — then it must be the latter proposition which is correct. But that implies that Epimenides himself cannot lie, and so it must be so that he and all his fellow Cretans never lie.
But that makes Epimenides's original statement a lie ... and round and round the logic goes, neverendingly. This is the Epimenides paradox.
Maybe the problem which creates the paradox is that statements made in everyday language can be vague. We can try to strip the vagaries of human language away from this and like paradoxes by replacing statements like (a) "Epimenides is a Cretan" and (b) "Cretans always lie" and (c) "Epimenides said (b)" with symbol strings in formal systems.
Formal systems, says Hofstadter, are ways of producing nothing more than various strings of symbols. The symbols in themselves have no intrinsic meaning that might confuse us. You gin up a formal system by saying what symbols are allowed. In the first formal system Hofstadter introduces (pp. 33ff.), the only allowable symbols are M, I, and U.
The next thing you do is specify one or more starting strings (actually, to be perfectly precise, zero or more). These are axioms. The only axiom in the MIU-system is MI.
You next specify one or more rules of production, a.k.a. rules of inference. By applying one of these rules, some new string can be generated, based on a string you already have. For example, Rule 1 of the MIU-system is that any string ending in I can have U tacked on at the end. Thus, MI can be modified to MIU. Strings that can be generated by applying rules are called theorems.
Rule 2 in the MIU-system is that you may replicate whatever comes after the initial M. Thus, MIU can be altered to MIUIU, making another theorem.
Rule 3 is that III can be replaced with U anyplace it occurs. Thus, MI -> MII (by Rule 2) -> MIIII (by Rule 2, again) -> MUI or MIU (by Rule 3). MUI and MIU are also theorems in this system.
Rule 4 is that UU can be deleted wherever it occurs. Thus, MI -> MII (by Rule 2) -> MIIII (by Rule 2, again) -> MIIIIIIII (by Rule 2, yet again) -> MUIIIII (by Rule 4) -> MUUII (by Rule 4, again). MUUII is yet another theorem in this system.
This formal system is apparently incapable, given the four rules of production and the single axiom MI, of being manipulated to yield MU as one of its theorems! MU is well-formed, in that it begins with M, as all theorems in this system must, and that the remainder of the string is a mix of U's and I's (specifically, one U and zero I's). Yet MU cannot be derived in this particular formal system. (Or if it can, I have not come upon Hofstadter's solution yet.)
That may be a bit surprising: well-formed strings can sometimes fail to be theorems. It becomes not just surprising but downright significant when you consider that some formal systems have meaningful interpretations in terms of the correspondence of theorems with real-world truth.
The MIU-system, as it happens, isn't meaningfully interpretable, but one that is is Hofstadter's pq-system (pp. 46ff.). In the pq-system, the permissible symbols are p, q, and the hyphen. There are any number of axioms, one of which is -p-q--. Another is -p--q---. All of the axioms have the form xp-qx-. Here, x represents some number of hyphens: the same number of hyphens in both places where x occurs in the pattern. The pattern xp-qx- is called an axiom schema.
The only rule of production in the pq-system is that any string of the system, be it an axiom or a theorem, can be lengthened by adding exactly one hyphen to the group between p and q and exactly one hyphen to the group following the q. For example, by this rule -p----q----- can be turned into -p-----q------.
Hofstadter shows that this particular system is capable of meaningful interpretation. Basically, you can substitute the appropriate number for any quantity of successive hyphens — for example, 3 for --- — while p turns into "plus" and q becomes "equals." In that way, -p----q----- can be interpreted as "1 plus 4 equals 5."
Interpretation is the mapping of otherwise meaningless strings to statements that have a chance of being "true" externally to the system itself. In this particular interpretation of the pq-system — as having to do with real-world addition — all theorems map to true statements involving adding two numbers. Because the pq-system as a system is capable of at least one meaningful external interpretation along these lines, it differs from systems like the MIU-system which apparently have no meaningful interpretations.
The pq-system has at least one other meaningful interpretation, the one in which -p----q----- becomes "1 equals 4 taken from 5." The system itself and its two interpretations are isomorphisms. The mappings between the system and either of its interpretations, and also that between the two interpretations themselves, is perfect.
Isomorphisms are key. As Hofstadter shows (pp. 49ff.), they "induce" meaning whenever they are (somehow) discovered by human intelligence. In other words, they "create meanings in the minds of people" (p. 50). Stumbling upon a valid interpretive isomorphism between meaningless symbol strings like -p----q----- and true statements in the real world like "1 plus 4 equals 5" can be "cause for joy" and "a source of wonderment." It typically occurs as "a bolt from the blue": everything just "falls into place."
Discovering a symbol-truth isomorphism is a case of "jumping out of the system" (pp. 37ff), an act that allows you to learn something about the formal system that is not contained in the system itself.
There is nothing within the pq-system, for instance, which tells you it is isomorphic with something you already know: addition. There are no system-internal rules for the necessary interpretive mappings. Yet the likelihood is high that if you play around with the mechanics of the pq-system just a wee bit, you'll twig to the fact that it's really a stand-in for grade-school addition.
It's also likely that a bit of playing around with the MIU-system will convince you that MU simply cannot be derived, no matter what rule applications you try, in whatever order. Again, it helps to be able to jump out of the system here and notice (for instance) how you can apply Rule 2 to axiom MI to repeatedly double the number of I's following M — giving you some even number of I's.
Also, if any even number of I's following M is divisible by 6, you may divine that you can first apply Rule 1 to put a U at the end of the I's, and then you can apply Rule 3 however many times you need to to change every III into U. That will give you an odd number of U's, from which you can delete successive U-pairs by virtue of Rule 4 until you are left with just one U. Result: MU.
But, try as you might, you never seem to arrive at a number of I's following the M that is divisible by 6! Mixing in applications of Rules 1 and 4 doesn't seem to help the situation, either. There seems to be a hidden force in the system that keeps you from deriving something like, say, MIIIIII, with exactly 6 I's in a row, from which MIIIIII -> MIIIIIIU -> MUIIIU -> MUUU -> MU would finish the job for you.
Discovery of this negative hidden force may not be as satisfying as, say, noticing that the pq-system amounts to a stand-in for addition. Yet it can lead, albeit more indirectly, to recognizing the truth of a general statement, one that has to do with what mathematicians call number theory.
I do not yet know how best to couch this statement about the "hidden force" in its most general, hence useful, form. Perhaps it says something about the inability to generate every natural number — every non-negative integer, that is — by a procedure involving successive doublings starting from 1 and then some even number of divisions by 3 (which is what divisibility by 6 implies).
Or, perhaps it is something even more general than that. Call the statement at its most general Statement X. An excellent question is, is number theory itself a formal system that, locatable within itself, there is a theorem isomorphic to Statement X?
We know number theory is a formal system. So does it contain a theorem isomorphic to Statement X? I cannot answer that question yet, but I can say this: Hofstadter shows that not all true statements about a formal system such as number theory are necessarily isomorphisms of theorems within the system itself!
You can't discover all true statements about a formal system by using interpretive mappings from the theorems within the system to true external statements about the system. There are unreachable truths that lie outside the system proper. You can't reach them even if you have a "bolt from the blue" and notice a perfect isomorphism between all internal theorems and their corresponding external truths.
Provided the formal system is, by careful design, rendered immune to contradiction, inconsistency, and paradox, and provided it has a great deal of "power" (which the pq-system lacks, but which number theory as a whole possesses) it will necessarily have this characteristic of "incompleteness": some true statements about the system are not isomorphic to theorems within the system. This is basically what the mathematician Kurt Gödel demonstrated in 1931.
Now, this next part of the discussion brings back in the idea of paradoxes. I have to admit I am on shaky ground here — I don't quite understand what I am talking about yet. Perhaps as I continue to read, Hofstadter will clarify it for me. At this juncture, the best I can say is that there is some sort of weird correspondence between paradoxes such as that of Epimenides and theorems of formal systems that are "true" but unprovable within the system itself.
By "true" is meant that the theorem can be interpreted as corresponding to a demonstrably true statement in the world, real or imaginary, outside the formal system. By "unprovable," I mean that the theorem in question cannot be successfully generated within the system. It would be like MU: well-formed. Moreover, if the MIU-system were capable of external interpretation, which it isn't, it would indeed have such an interpretation, and that interpretation would be a demonstrably true statement. Yet there would be no way to get from axiom MI to nontheorem MU by the application of formal rules within the system itself.
There does seem to be (and I may be wrong about this; I feel I'm really on shaky ground here) one way around the unreachablilty of truth in formal systems of appreciable generative power, such as number theory or set theory. That way, if it exists, involves tolerating some degree of self-contradiction and paradox within the system itself.
Here is how that works out with respect to set theory: Basically, paradoxes spring from the possibility of self-reference in the theorems of the system and/or in the interpretively mapped statements derived from the system. For example, in mathematical set theory there is the idea that a set ought to be able to contain itself as a member. The set of all sets, for example, is a legal construction that contains itself. If that sort of thing is allowed, then (see p. 20) there can presumably be just two types of sets. Type A sets do not contain themselves. Type B sets do. Then, is "the set of all sets of Type A" itself of Type A, or is it of Type B? It is neither! Either choice tangles you up in paradox.
This sort of paradoxical tangle can be avoided, apparently, only by forcing set theory to dispense with sets of Type B entirely. That can make set theory entirely self-consistent ... but so much less useful and powerful as to deserve the epithet "ugly."
If you allow "self-swallowing" sets of Type B, you also admit the possibility of paradox into set theory. Now you must deal with external statements about set theory of which the truth or falsity is undecidable. "The set of all run-of-the-mill sets of Type A is itself of Type A" is one of these. You cannot decide whether it is true or not.
This fact seems to correspond to the theory-internal fact that, as a formal system, set theory cannot derive the symbol string whose external interpretive mapping is "The set of all run-of-the-mill sets of Type A is itself of Type A." Nor can it generate the symbolic equivalent of the external interpretive negation: "The set of all run-of-the-mill sets of Type A is not of Type A, i.e., it is of Type B."
Neither the positive theorem nor its negation is reachable within the confines of formal set theory. This unfortunate situation maps, in the larger ambit of external truth or falsity, to paradox.
With respect to number theory, apparently the situation is much the same as with set theory. The mathematical theory that concerns how the natural numbers — the nonnegative integers — behave is intended to be both consistent and complete. Consistency means basically that all theorems within a formalized rendition of the entirety of number theory — a sort of pq-system on steroids — are capable of being interpreted in such a way as to represent true statements such as "1 plus 1 equals 2."
Completeness means basically that all true statements of number theory correspond to theorems in the formalized rendition.
Hofstadter calls the formalized rendition "TNT," for typographical number theory — since formal systems are basically ways of "typing" particular strings of typographical symbols. Gödel found an extremely clever way to devise a typographical rendition of the statement, "TNT is consistent." Then he showed that constructing TNT so that this well-formed "sentence" is actually one of its theorems automatically makes TNT inconsistent!
Looked at another way, if TNT is consistent, then the theorem which means "TNT is consistent" cannot be part of it. On that view, TNT has to be incomplete. It cannot assert its own consistency!
It is sort of like the situation faced by Yossarian, the protagonist of Joseph Heller's Catch-22. Yossarian is a WWII bomber pilot who has flown too many perilous missions and now wants to be relieved of duty. The rules say this can happen if the pilot in question has gone insane. So Yossarian attempts to convince his superiors that that is indeed the case: he's crazy as a loon. The only catch is — and this is Catch-22 — if he's of sufficiently sound mind to campaign for a diagnosis of his own insanity, then he's obviously quite sane and cannot legitimately be relieved of duty.
Likewise, if number theory can assert it's own consistency, it's inconsistent. The only way for it to be consistent is to be unable to assert its own consistency — i.e., to be incomplete, in the sense of not being able to derive or prove every single true statement about itself. This is the mother of all paradoxes.
Just the fact that many a formal system can, upon successful interpretation, lead to paradox seems to require that you be able to (again) "jump outside the system" to see the paradox. At least, that is what I think Hofstadter is getting at. Whether you jump out to detect meaningful isomorphisms or you subsequently jump out to detect paradoxes, the ability to jump out of formal systems at all is a distinguishing mark of human intelligence.
A machine can in concept derive all the theorems of any formal system, even if for certain systems it would require an infinite amount of time to complete the derivation. Also, if a decision procedure is known by which any given symbol-string can be shown to be (or not to be) a theorem of a given system, a machine can be programmed to apply it. Machines can in some cases, as I understand it, even figure out what the decision procedure for a system happens to be.
But human intelligence goes well beyond these sorts of tasks. In fact, anything along the lines of figuring out the meaning of a theorem in a formal system is decidedly non-mechanical.
There is, moreover, a gray area in which it is not clear whether or not a mechanical process could avail. Could a machine come up with something like Euclid's Proof, for example?
Euclid proved that whatever number you pick, there exists a prime number greater than it (see pp. 58ff.) He did this by finding a pattern for a series of baby steps by means of which you can assure yourself, for every number 1, 2, 3, and on up, that that number plus 1 is either itself a prime or has a prime larger than it. His insightful discovery of the right pattern for the concatenated baby steps made for a compact and wholly convincing proof — and it may or may not be one a machine could ever discover.
That seems to be because you have to jump outside a formal system such as number theory to learn certain true statements about the system and figure out proofs for those statements.
Even if finding clever proofs, such as that of Euclid, is not absolutely machine-impossible, and even if finding correct isomorphisms is ultimately susceptible to artificial intelligence, locating and understanding implicit paradoxes seems to depend wholly on human smarts.
The human mind alone is capable of dealing meaningfully with "strange loops." The activity of neurons in the brain, itself presumably isomorphic with some rigidly formal system, can somehow miraculously jump out of the system and incorporate "bolts from the blue" into its own inner workings. It can find "unreachable" truths and detect paradoxes non-mechanically.
That, indeed, seems to be Hofstadter's overarching point: there exist officially "unreachable" truths and implicit Catch-22s within formal systems ... and the human mind, because it can deal with strange loops and paradoxes that flabbergast "intelligent" machines, can nonetheless find them.
1 comment:
Nevertheless, human minds manage to ask questions which may, in prinicple, be impossible to answer by ourselves...
Post a Comment