A different sort of blog post today: I figured we'd take a quick break from SICP and have a look at a puzzle from another book I've been working my way through lately. Gödel, Escher, Bach: an Eternal Golden Braid by Douglas Hofstadter is a famous book that I've seen on dozens of must-read lists for both computer science and mathematics.
It's not hard to see why, either. Though the book is touted as ultimately being about the nature of "consciousness" and whether we can get computers/robots to emulate such a thing, from the small amount of it I've read so far I can see that it touches on many other mathematical concepts too: the idea of formal systems, isomorphism and its relation to meaning and especially recursion and self-reference.
Early on in the book, Hofstadter shows us a formal system – the MIU system. Given a string of letters in the MIU system, we can generate additional strings by applying particular rules. This forms the context for the MU puzzle: can we start with a string, say the string MI, and through successive application of the rules of the system, end up with the string MU?
I won't spoil the solution here, of course! But the entirety of the book's discussion on the MIU system itself – with its rules, its strings, and its metaphorical "genie" that can generate infinitely many MIU strings given enough time – well, it was pretty much daring for a programmatic implementation.
So that's the topic for today. With JRuby as our programming language, together with some very basic use of regular expressions, we'll devise a code implementation of this MIU system and use it to generate some strings!
The MIU System
To begin with, let's check out this MIU system and its formal rules.
First, the legal strings in our system are those that contain only the letters M, I and U. For instance, MUI is a legal string, and so are UIUUIII, MM, U, etc. A string containing any other letters or symbols is not a legitimate string in the MIU system (eg. MPQIU is not a legal string since it contains the letters P and Q, which are not part of the system.)
So we can formalise this mathematically as follows:
However as you'll see, just because a string is legal doesn't mean that we can always generate it.
The main point of the system is that we start with given strings (or axioms), and using certain rules of inference, we can derive new strings (or theorems).
Put that way, the similarities between the MIU system and the formal system of mathematics itself are pretty evident, right?
This is another similarity: If we cannot use our rules to derive a particular legal string from our starting string/axiom, then it is not a theorem. So that aforementioned MU puzzle can be rephrased to "If MI is an axiom, is MU a theorem?"
So let's see the rules that we have for generating new strings. Here's the first one:
Our first rule means that if we have a string that ends with an I, say UUI, then we can generate a new string by tacking a U on to the end to get UUIU.
Here's the second rule:
So say we had the string MUIU. Then this second rule allows us to take the part after the M (that is, the UIU part), and repeat it at the end of the string, so we get the new string MUIUUIU.
Our third rule is as follows:
This means that if we had a string like IIIUIIII, we could generate the string UUIIII by replacing that III bit at the front with a U.
(In fact, notice that we have four I's at the end, so we could have also generated the strings IIIUUI and IIIUIU here, depending on where we wanted to do the III → U replacement! As you'll see, this fact leads to some tricky programming.)
Finally, our last rule:
So if we had the string UUUMUU for instance, we can drop the UU at the end and get the string UUUM.
(Again, we could also have dropped a UU from the three U's at the front to get the string UMUU. So we'd need to specify where we want the UU to be dropped!)
And that's the MIU system. So without any further delay, let's program this thing up!
Programming the Rules for the MIU System
First, just for fun, we can use a simple regular expression to check for whether we've got a legal string or not. We'll put such a check in our miu_string?() method:
Short and sweet! Here we use the match() method of the String class along with the regular expression [^MIU]. This regular expression will basically alert us to the existence of any characters in the string that are not an M, I, or U. If any are found, then the match() method returns them for us. If none are found though, then we are returned the value nil instead (which works like the value false in Ruby.)
Then we take the logical complement of whatever was returned (note the '!' at the front of the expression.) If we had nil, we'll now have true. Which is what we want: If we didn't get any matches, then we only contain the characters M, I and U, and so we have a MIU string! On the other hand, if we had even one match, then the logical complement of a non-empty list is nil (ie. false.)
We can check that our method works as we expect it to with a few simple examples right in the JRuby JIRB shell:
miu_string?("MIUIUMM")
#> true
miu_string?("MIAUU")
#> false
miu_string?("UUIIIU6")
#> false
Now programming Rule 1 of the MIU system is very simple. We simply want to check whether the last letter of the string is an I, and if so, we add on a U after it. We can code this up in separate can_apply_rule1?() and apply_rule1() methods as follows:
We should test this too, of course. So here is an example of our Rule 1 in action:
can_apply_rule1?("M")
#> false
can_apply_rule1?("MI")
#> true
apply_rule1("MI")
#> "MIU"
Rule 2 is also pretty simple. We check whether the first letter of our string is an M. If so, we take all of the characters after the string, concatenate them on to the end of the string again, and return this new string.
So we have our can_apply_rule2?() and apply_rule2() methods:
Again, we can test this with a quick example:
can_apply_rule2?("UIUU")
#> false
can_apply_rule2?("MUIIMM")
#> true
apply_rule2("MUIIMM")
#> "MUIIMMUIIMM"
Now as we might have expected, Rule 3 is quite tricky...
For our can_apply_rule3?() method, we can simply match the regular expression III against the given string, and check whether it is nil. If it isn't (ie. the logical complement is true), then we have a set of 3 consecutive I's in the string.
However, recall that if we were given a string like IIII, we actually have a choice for which of the three I's to pick here! And such a choice need to be reflected in our code. So for our apply_rule3() method, we take in an extra parameter index, and use it to tell us which of the III's to replace.
Of course, we don't want the user to have to figure this out on their own every time. So we have another method, rule3_indices() that takes the string and returns us a set of indices of each possible choice for III.
To do this, we first scan the string with the regular expression I{3,}, which will match with any set of three or more consecutive I's. We then accumulate all of the matches into a list (which you can see in that first line, with the slightly cryptic enumeration mapping.)
With our list of matches, we then want to grab the indices corresponding to the start of each match. To do that, we can notice the following.
Suppose we have the string IIIII. Then we have 3 choices for the for the starting position for the III we want to replace, and they will be +0, +1 and +2 letters away from the starting point respectively (eg. here we can choose IIIII, IIIII or IIIII).
And this will hold generally. Given a string of N consecutive I's, we have
N - (length of 3 consecutive I's) + 1 = K different choices for the starting positions,
which will be +0, +1, +2, ... etc.
So we can generate the list of starting positions by enumerating all of the numbers from 0 to K, and then shifting the beginning of the match position forward by all of those numbers at once with a map. And we do this for every set of consecutive I's that we've found.
Then we simply collect everything up into an array, flatten it (to remove the array double-nesting), and return.
This gives us our list of indices. Then we can pass any one of those indices into the apply_rule3() method, which will change that occurrence of III into a U (we do this by duplicating the string before we make the change – this means that we don't mutate the existing string in the method, which is always nice.)
After all of that, we should make sure that this works! Sure enough:
can_apply_rule3?("MIIUUUUIIUI")
#> false
can_apply_rule3?("MIIIIUUIII")
#> true
rule3_indices("MIIIIUUIII")
#> [1, 2, 7]
apply_rule3("MIIIIUUIII", 1)
#> "MUIUUIII"
apply_rule3("MIIIIUUIII", 2)
#> "MIUUUIII"
apply_rule3("MIIIIUUIII", 7)
#> "MIIIIUUU"
With all that sorted, we can expect that Rule 4 is going to be pretty much the same thing:
Here we match the regular expression UU with the string to find any occurrences of two consecutive U's in our can_apply_rule4?() method. We check if the result is nil or not – if it isn't, then we can apply Rule 4 to the string.
But just like with Rule 3 before, we ought to allow for the index of the UU selection to be specified in case we have multiple choices. So we have a rule4_indices() method that works identically to the one we had for Rule 3; except this time we scan with the U{2,} regular expression instead (which matches any occurrence of two or more consecutive U's.)
Then in our apply_rule4() method, we take the given index and simply replace the two U's at that index with the empty string, which effectively drops them.
Then we can test this final rule too:
can_apply_rule4?("MUIUIIMI")
#> false
can_apply_rule4?("MUUIUUUUUI")
#> true
rule4_indices("MUUIUUUUUI")
#> [1, 4, 5, 6, 7]
apply_rule4("MUUIUUUUUI", 4)
#> "MUUIUUUI"
apply_rule4("MUUIUUUUUI", 7)
#> "MUUIUUUI"
apply_rule4("MUUIUUUUUI", 1)
#> "MIUUUUUI"
So the rules of our MIU system are all working correctly! The last thing left to code up is an implementation of the "genie" that takes a list of strings and applies each of the rules to each of those strings to generate more.
Generating MIU Strings
To complete our little program, we'll write a method generate_more_strings() that takes in a list of MIU strings and applies all of the rules to each string in turn. The resulting strings are then filtered for duplicates and returned:
So as you can see, we define a helper method apply_all_rules() that takes a string and, where possible, applies each of the rules for the MIU system and collects the new strings. Note that for Rules 3 and 4, we use all of the possible indices – this is accomplished by mapping the rule application over the list of indices returned by the methods we constructed for that purpose.
With the helper method defined, we then simply map that method over the given list of strings, flatten it (to remove the array nesting) and return only the unique elements of that list.
So the program for the MIU system is done!
We can even demonstrate it with the exact example of the genie that Douglas Hofstadter gives in his book with the MU puzzle. We start with the string MI:
strings = ["MI"]
#> ["MI"]
Then the genie gets to work. It takes our list of strings and returns us a new list – the list of all strings that could possibly be generated with up to a single rule application:
strings = (strings + generate_more_strings(strings)).uniq
#> ["MI", "MIU", "MII"]
The genie keeps going, and returns us the list of all strings that could be generated with two rule applications or less:
strings = (strings + generate_more_strings(strings)).uniq
#> ["MI", "MIU", "MII", "MIUIU", "MIIU", "MIIII"]
And the genie keeps generating more strings:
strings = (strings + generate_more_strings(strings)).uniq
#> ["MI", "MIU", "MII", "MIUIU", "MIIU", "MIIII", "MIUIUIUIU",
#> "MIIUIIU", "MIIIIU", "MIIIIIIII", "MUI"]
And more:
strings = (strings + generate_more_strings(strings)).uniq
#> ["MI", "MIU", "MII", "MIUIU", "MIIU", "MIIII", "MIUIUIUIU",
#> "MIIUIIU", "MIIIIU", "MIIIIIIII", "MUI", "MIUIUIUIUIUIUIUIU",
#> "MIIUIIUIIUIIU", "MIIIIUIIIIU", "MUIU", "MIUU", "MIIIIIIIIU",
#> "MIIIIIIIIIIIIIIII", "MUIIIII", "MIUIIII", "MIIUIII",
#> "MIIIUII", "MIIIIUI", "MIIIIIU", "MUIUI"]
And more, and more, and more...
So if the string MU ever appears in this (infinite) list, then we'll know for sure that we can generate it from MI! But we might be waiting for a while...
No comments:
Post a Comment