Reading on <em> Godel, Escher, Bach</em>: Chapter 1 – The MU Puzzle

This chapter opens up with the MU puzzle as a prototype for us to better understand the underlying structure of formal systems. The MU puzzle is in essence about attempting to produce the string “MU” from an initially given string “MI” as one follows a certain set of rules that can be applied given some conditions. Here are the four rules of the puzzle (rephrased for further clarity):

1. If you possess a string whose last letter is I, you can add on a U at the end.
2. Suppose you have Mx, where x is at any point, the whole set of strings following M, then you may add Mxx to your collection.
3. If III occurs in one of the strings in your collection, you may make a new string with U in place of III.
4. If UU occurs inside one of your strings, you can drop it and link the two sides where the string was cut.

What’s the most efficient way of finding a MU within this scheme? Well first one tries all the allowed permutations of MI with the given rules then repeats the process for the newly produced strings, i.e. one inspects all the allowed manipulations for all the strings in every level of the collection where the MI string lies at the bottom-most level. As one proceeds doing this, it is then checked if given a finite amount of levels or steps, we arrive at MU somewhere within the collection. This process of trying out all the possible ways of manipulating the objects of a system using all its rules, starting from its axiom/s, is called a decision procedure. Ultimately, the answer to the question “Can you produce MU?” is “No, you can’t”. We shall see the profound implications of this answer as we dwell more into formal systems.

The point of this exercise is to get a gist of how formal systems function given the example of the puzzle above. From an earlier post , I have mentioned about axioms, theorems and proofs as more or less the elements that make up a formal system. In this context, the starting MI string in the puzzle is the axiom. It is where all the other strings will originate from, just as how all the mathematical theorems start from the primitive axioms and definitions. One does not question the truthfulness of the axioms, they are considered to be true right from the start. All the other strings that follow from the four rules and the MI string are called the theorems of the puzzle.

In any formal system, there are two types of theorems: 1.) Theorems that are produced within the system’s rules. 2.) Theorems about the formal system itself, usually statements about the system’s statements. DH makes a distinction between these two types. The former can be proven by derivation, a process of producing a theorem by merely following the rules by mechanical manipulation, through a decision procedure. For example, the string MUIIU can be shown to be a theorem within the puzzle by invoking a sequence of steps from the MI axiom. As for the proof of the latter, it is more insightful in such a way that intelligence is needed to supply both the theorem and its proof. What do we mean by this? Let us take as an example, the following theorem of the second kind: “All the theorems in the system start with the string M.” One cannot prove this by checking if each of the infinitely many theorems does start with an M. That would take an infinite amount of time and would be utterly inconvenient. Any decision procedure would fail to prove the theorem, giving us no choice but to finally invoke some form of intelligence to resolve the issue. Such intelligence would be able to interpret the puzzle from a meta-game perspective. The statement “Each of the derived theorems of the puzzle start with an M” is irrevocably a meta-statement, one that is beyond the framework of the puzzle but is nevertheless true. This leads us back to the consequence of Godel’s incomplete theorem, that provability is a weaker notion than truth.

Clearly, the two theorem types above are telling us something about the advantage of intelligent intervention over any mechanical mode of working within systems. Yet in the manner of proving a theorem of the second type, we must initially accept the statements of logical deduction to be true. It is here that we come to the dialogue “Two Part Invention” where the Tortoise opened a discussion to Achilles regarding three statements, these are (rephrased for clarity)

A.) If , and are any three things and if is equal to , and is also equal to , then is equal to . (Mathematically, if and , then
B.) Let M and N be the two sides of a triangle. Let O be a certain line segment. The two sides M and N are both equal to O.
Z.) M and N are equal to each other.

Achilles readily embraces the logical deduction that if M and N are both equal to O, then those two sides of the triangle are equal to each other. But the Tortoise dissected the argument further by saying that in order to make the necessary logical deduction, then one must believe the statement (denoted by the symbol C) “if A and B are true, then Z must be true”. The Tortoise goes beyond by noting that in order to believe C, one must again believe a meta-statement of C (denoted by D) given by “if A, B, and C are true, then Z must be true”. In other words, D literally means that if one assumes that A and B are true, and that the logical induction “if A and B are true, then Z must be true” is also believed to be true, then Z must be true. Yet one can still peel further the meta-logical induction by going to the metameta-logical induction that is needed to deem the statements of those on the lower levels to be true. There is no end to this. Here we see a concept that is called an infinite recursion. Fields that are grounded on logic have rarely considered this when they operate or understand things since an inquiry into such a recursion does not provide us with new knowledge per se. They have proceeded unhindered in their operations without the need to get through the inductions that lie at the bottom of it all. But it is this actual mechanism that will be employed over and over again throughout the book for within it might (I say this because I haven’t read the whole book yet) lie the power to understand how inanimate objects can form themselves into self-conscious entities such as the one who wrote this article and the one who is reading it now.

References:
Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books.

Advertisement