Looking At Formal Systems On Linux and Unix

Hey There,

For today's post, we're going to put out a brain-teaser that won't get solved (at least on this blog) until tomorrow. It's based on a formal system (which is basically a set of rules, with specific applications, used as a method to solve an equation or problem) invented by Emil Post back in the 1920's and is most commonly referred to as a "post production system."

This basic formal system was re-popularized by Douglas R. Hofstadter in his book Godel, Escher, Bach: An Eternal Golden Braid" when he introduced the concept to folks, who weren't especially crazy about such abstract notions, by way of a little puzzle.

For today's post, we're going to reproduce (paraphrased, of course) that puzzle and let you see if you can solve it (or, if you can prove that it can't be solved, which is a possibility).

For tomorrow's post, we'll be putting up a script for Linux or Unix that will make this whole process much easier and will give you the option to "attack" this problem as quickly or slowly as you prefer. While the script will relieve you of the pleasure of completing this mental exercise (if it's at all possible to complete), it will either get you to the answer very quickly or make you wonder how long it might possibly take to solve. Considering the ingredients, that may turn out to be a huge chunk of your time ;)

And here we go. I hope you enjoy this puzzle as much as I did:

We begin with an absolute. You are starting out with a single string (which is absolutely defined, within the context of this formal system and puzzle, as a set of characters in a specific order - e.g. MI is not the same as IM). That absolute (or starting point) is simply "MI." (Note that all punctuation marks are "not" parts of the strings ;)

Give the string "MI," your goal will be to convert that string into the string "MU." Please note that, although a string like MIMUIM is a valid member of the M I U formal system, given the starting string of MI, you will never be able to have an M anywhere but in the first position. Sadly, this does not make finding the answer easy ;)

There are 4, and only 4, rules in this formal system, and you can only correctly solve the puzzle by applying any and/or all of them, one at a time, for as long as it takes to get you to "MU."

Rule 1: If your string ends with an "I", you can add a "U" to the end of it.

Ex: MI can become MIU.

Rule 2: If you have a string of the form "Mx," you can change that to "Mxx." Note here that the variable x can refer to a string (not necessarily just one character) and that only the letters M, I and U will ever exist in any string you produce by application of these rules. x is simply meant to be used as a variable notation.

Ex: MI can become MII
MIU can become MIUIU

The one thing to remember about this rule is that, once you've picked your character, or string, you can only duplicate it once per invocation of the rule. For instance, this is not acceptable:

Ex: MIU cannot become MIUIUII (duplicating "IU" and then duplicating the "I" before the "U," after the "I." You could do the following, however, in a number of steps:
MIU can become MIIUIU (by duplicating the "I" first, and then duplicating the "IU" from the resultant string)

Rule 3: If the substring "III" appears in your string, you can replace "III" with "U," but you may not do the opposite:

Ex: MIII can become MU
Ex: MU cannot become MIII

Rule 4: If "UU" occurs within your string (at any point), you can remove it from the string:

Ex: MIUUI can become MII

Using these 4 "rules of production" (or "rules of inference") can you take your initial string "MI" and change it to "MU"? Also, if it's not possible, is that provable? And, if it is possible, what's the fastest way to do it?

Have fun trying to figure it out. If you already own the aforementioned book, you may know the solution already (it's hidden somewhere in the approximately 700+ pages). Sometimes, though, your individual path to the solution will teach you a lot more than you'd learn by being told the answer :)

Enjoy,

, Mike