The answer is "yes", but damn you for making me go there before my coffee.

The answer to "can U get to MU?" is certainly "no," however, since no rule provides for the introduction or elimination of "M".

So, now that we've had our coffee, is this system Turing-complete?

(Hint: Can it be described by a regular grammar? A context-free grammar? A context-sensitive grammar?)

Well, I'm flumoxed. I posted this last night, after four sheets from my legal pad and way too much time, the problem still unsolved. Hofstadter claims to reveal the solution later in the book. So, after reading, weez, and then Nick, I looked it up in the index and . . . Nick's right, it turns out to be a logical impossibility. Which leaves me with two questions: why does Hofstadter, who I admire greatly, pull such a lame move, and (weez), how did you manage to defy the laws of logic _before_ your morning coffee?

I don't know (or recall, rather) the explanation from Hofstadter's book - I have read the explanation at some point, but it's been a while. I think a reasonably short explanation would go like this, though:

Starting with "MI," you will always be stuck with an "I" somewhere after the "M."

There are two elimination rules: Rule 4 allows us to replace "UU" with "" (the empty string). That's no help in eliminating the "I" that comes right after the "M" (or any other "I" for that matter).

Rule 3 allows us to replace "III" with "U." Nice, but there is no way to build up three I's after the M without building up four, since the only way to introduce additional I's is with rule 2, which doubles the existing sequence that follows "M." E.g., MI -> MII -> MIIII. Now we can transform this to MUI, but we're still stuck with that pesky I at the end, and no way to eliminate it.

That's not the full explanation - we can build up not only "IIII" but any number of I's that is a power of two (2^x), but none of these powers of two help us. That's because while we can build up any power of two, we can only eliminate any multiple of three (3y). And no power of two is a multiple of three (there are no x, y that solve 2^x = 3y).

The way I thought about this was to consider the language that the elimination rules could "eliminate" (what strings those two rules could eventually transform to MU) and then note that MI can't be transformed into any of these.

And I'm not sure that ended up being reasonably short, but anyway.

I don't know (or recall, rather) the explanation from Hofstadter's book - I have read the explanation at some point, but it's been a while. I think a reasonably short explanation would go like this, though:

Starting with "MI," you will always be stuck with an "I" somewhere after the "M."

There are two elimination rules: Rule 4 allows us to replace "UU" with "" (the empty string). That's no help in eliminating the "I" that comes right after the "M" (or any other "I" for that matter).

Rule 3 allows us to replace "III" with "U." Nice, but there is no way to build up three I's after the M without building up four, since the only way to introduce additional I's is with rule 2, which doubles the existing sequence that follows "M." E.g., MI -> MII -> MIIII. Now we can transform this to MUI, but we're still stuck with that pesky I at the end, and no way to eliminate it.

That's not the full explanation - we can build up not only "IIII" but any number of I's that is a power of two (2^x), but none of these powers of two help us. That's because while we can build up any power of two, we can only eliminate any multiple of three (3y). And no power of two is a multiple of three (there are no x, y that solve 2^x = 3y).

The way I thought about this was to consider the language that the elimination rules could "eliminate" (what strings those two rules could eventually transform to MU) and then note that MI can't be transformed into any of these.

And I'm not sure that ended up being reasonably short, but anyway.

Also, after getting no reply from your blog, Matt, I seem to only be able to introduce pairs of comments and I don't seem to be able to eliminate comments at all.

Just testing . . .

I believe pairs of posts can be replaced with the letter E, and sometimes Y.

I'm glad I only used *one* piece of paper before I gave up and considered myself a miserable failure ( http://www.despair.com/fail24x30pri.html ).

Matt, I think what happened with my comment is just that the expected "confirmation" (the comment page updated with my comment) timed out and never made it back to my browser, but, as it happened, I had succeeded in posting my comment, so a second click ended up posting it again.

Ah, the pre-coffee Weez may not be so illogical. Just savvy to the ambiguity of the rule that indicates that "if the string contains III you may replace those three characters with U"

If each "I" is individually replaced by a "U" you get "UUU"

And then eliminate the "UU" you get the lone "U" after "M"

Logically exploitation of an under-specification of the rule and an appreciation for the difference between a visual and lexical meaning of "character", no?

Even if were to introduce the rule III -> UUU (not originally given), how does that allow MI to be transformed to MU? Remember, the original problem was that we can never get rid of all the I's because no power of two is a multiple of three. Whether we convert III to U or convert it to UUU doesn't really matter - we're still stuck with this problem.

The Rules are underspecified:

if the string is Mx then you may create Mxx; for example, MI becomes MII;

One can read MII as MxI and thereby get the quested after MIII by replacing MxI with MxxI

The underspecification of course depends upon the meaning given to the "for example". If one choses not to fall into a pattern trap, it becomes possible to intrepret the example as one of many and not a paradigm.

A notation, a rule, an example, a paradigm: what is being transformed using what?

Isn't Douglas R. Hofstadter’s Gödel, Escher, Bach about the power of as Jerome Bruner calls it "going meta"?

Sorry that things are proving so confusing for you. The rules aren't underspecified, and misunderstanding them doesn't demonstrate anything interesting or "meta." Hofstadter’s book deals not with people's difficulties in communicating or understanding formal systems, but with some of their properties and limitations of these systems. It's a worthwhile read.

I guess what I'm wondering, having not worked through the whole book yet (but having looked ahead to discern the "solution" to the MU problem) is why Hofstadter chose to demonstrate the basic properties of formal systems with an invalid axiom (to use his terms). I understand the _logic_ of why you can't get to MU, but I don't understand the rhetorical/pedagogical thinking that gave rise to an example-that's-not-an-example. Nick?

Matt, I think the point of this is just to illustrate a property of this system, but one that is hard to prove. It's not really a false axiom: it's just that the statement "MI cannot be transformed into MU" is true in this system. To prove it, we have to reason at a different level rather than just giving an example that shows that a transformation can be done.

If we asked "Can we transform the string MI to MII?" then the answer is "yes," and we only need to apply rule 2 to MI to show this. So "MI can be transformed to MII" is true in this system. But the proof of this is, as we say, trivial.

The answer to "Can we transform the string MI to MU?" is "no," but the proof turns out to be much harder! We can't just say "by rule 4" or something. Indeed, no single example of a sequence of transformations will prove this. We need to show that of all possible sequeneces of transformations (which are infinite in number), none of them results in "MU." This was what I was trying to do above in my sketch of a proof that MI cannot be transformed into MU.

An easier example of this reasoning can be seen here:

A formal system has only the character, A. There is a single rule: "A" can be added onto the end of any string. Beginning with the string "AA", show that we can never reach the string "A." (That is, show that "AA cannot be transformed into A" is true.)

The proof of this is quite easy, but it's the same kind of proof in some ways. I have to show that of all the infinite strings that can be generated from "AA," none of them are "A." So I'd proceed like this: All of the rules in the system increase the string's length. "A" is shorter than "AA." Therefore, "AA" can never be transformed into "A" by any sequence of applications of rules.

Too simple to be interesting, maybe, but in writing this down I had to reason about categories of and properties of strings, rather than just saying "A -> AA -> AAA" or something like that. I think that sort of reasoning may be what Hofstadter was trying to introduce with this example.

Thank you Nick, that makes a lot of sense. 'preciate you taking the time to spell it out.

I was always struck by the interwoven dialogues in H's book. I thought that dialogue was a neat way to explore the meanderings of "self-reference" which is one of the topics of Hofstadter’s Gödel, Escher, Bach. The book is not solely devoted to "formal systems" Very interesting to consider that the concept of "formal system" or the ways of playing, constructing and stretching formal systems is not given a priori. Exploring potential misunderstanding and underspecification is how many disciplines advance knowledge. For another example see:

http://www.otal.umd.edu/~mgk/blog/archives/000195.html

Matt, I think a partial answer to why the particular example of an 'unsolvable' problem is supplied by how nick and I choose differently to engage in some "jumping out fo the system".
Hofstadter writes (I've checked my recall against p. 37 in the edition currently in my possession):
"it is an inherent property of intelligence that it can jump out of the task which it is preforming, and survey what it has done; it is always looking for, and often finding, patterns."
The exchange here between nick and myself leads me to consider the question of "jumping where to"? One can jump to a path of proof (i.e. providing evidence that it can't be done in such and such a way) or one can re-examine the rules and move to finding a path (a redescribed/reinterpreted set of rules) to achieve the objective.
This is not a choice between optimism and pessimism (or between legitimate and illegitimate). It is, for me at this present time, more like the difference between procedural and declarative languages. Respect for the requirement of formality is processed differently. I am venturing to suggest that coming from a declarative-language angle, a question about the formal system arises: is MI composed of two substrings M and I ? Hofstadter: "The first thing to say about our formal system --- the MIU-system --- is that it utilized only three letters of the alphabet: M,I,U. That means that the only strings of the MIU-system are strings which are composed of those three letters."

Rule IV seems to imply severability of strings. However it could be localized only to strings or substrings made up of the letter "U". Rule II also implies severability. And it is gives the user lots of leaway. Hofstadter: "So the letter "x" in the rule simply stands for any string: but once you have decided which string it stands for, you have to stick with your choice (until you use the rule again, at which point you may make a new choice). [...] It is the function of the "x" to stand for an arbitrary string."
MI --> MII --> MIII --> MU
Rule II applied twice gives you MIII with the application of Rule IV you get MU
There is a leaway built into "you have to stick with your choice (until you use the rule again, at which point you may make a new choice). which implies you may not wish to make a new choice of string and apply the string again (it's like copy, paste, paste). Every interesting that Kari Krauss at accidents and substantials is looking at the concept of involution as demonstrated in the Klein bottle while this discussion has gone on here.