Recursive Structure of Hofstadter Sequences

I'm slowly (but surely!) making my way through Godel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. As I've mentioned before, so far it's been quite an awesome, thought-provoking read; exploring some pretty deep ideas from both mathematics and computer science.

One of those deep ideas is that of recursion. Upon introducing the idea with an amusing "story within a story within a story" dialogue, we are shown several peculiar sequences: starting with the G(n), H(n), F(n) and M(n) sequences. These are examples of Hofstadter sequences. The trick to these sequences is not only that they are recursively defined, but that they are, in fact, non-linearly recursive. G and H are both defined in terms of compositions of themselves. Even more strangely, F and M are defined in terms of nested compositions of each other!

The exercise that Hofstadter gives the reader is to determine the recursive structures that can be created by forming a graph of each of the sequences: where we label some nodes '1' through 'n', and let 'n' be the node directly above the node 'G(n)' in the graph. As we'll see, the graphs branch up and out like a tree, and we'll be able to notice some recursive patterns that define the infinite construction of the entire graph.

So let's get to it! To save having to calculate the values of the sequence by hand, we'll code up some recursive functions in Clojure that we can use to easily find the values for each of the Hofstadter sequences.

Hofstadter's MIU System

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!