"The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer."
-Edsger W. Dijkstra
Gödel, Escher, Bach's MU Puzzle
I recently obtained and began reading Gödel, Escher, Bach.
One of its earlier thought experiments involves this MUI system devised by Hofstadter. The system itself is quite simple. There are a couple of rules to add characters to a string of Ms Us and Is and a couple string to remove them. The reader is encouraged to work through the system and try to reach the string MUU. The book walks through an orderly tree based approach and shows no such sequence of "moves" yields MUU in less than a dozen iterations.
In order to play with the MUI system more efficiently I wrote a little calculator for it. After not finding a solution after much trial and error I wrote a fuzzy logic function to try to see if it could solve the puzzle. Below is the code.
[insert code here]
I ran this a few times, tweaked it and ran it some more then rpeaeted; only a couple of things ever happened. Either the system would reach a point where it could do nothing else, or it would Is until it ran out of memory.
Later in my reading Hofstadter revealed that there was no solution, and then began discussing the difficulty of proving that there was no solution. Point taken.

Comments
Post new comment