Skip to content

Instantly share code, notes, and snippets.

Last active August 29, 2015 13:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kenwebb/9221870 to your computer and use it in GitHub Desktop.
Save kenwebb/9221870 to your computer and use it in GitHub Desktop.
MU Puzzle
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook MIT License, Copyright (C) Ken Webb, Thu Feb 27 2014 13:31:24 GMT-0500 (EST)-->
Title: MU Puzzle
InternalName: 9221870
My Notes
Douglas Hofstadter introduces the Mu Puzzle in chapter I of his 1979 Pullitzer Prize-winning book "Godel, Escher, Bach: an Eternal Golden Braid". The goal of the puzzle is to produce the string/theorem "MU", starting with the string/axiom "MI", using just the four rules of the MIU system. Each rule can be applied when it's legal to do so, but only if you (or the computer) want to apply it.
Here's a `derivation` (a sequence of strings) that can be constructed using the four rules, starting with the axiom MI:
(1) MI axiom
(2) MII from (1) by rule II
(3) MIII from (2) by rule II
(4) MIIIU from (3) by rule I
(5) MUIU from (4) by rule III
(6) MUIUUIU from (5) by rule II
(7) MUIIU from (6) by rule IV
Hofstadter mentions two procedures for finding a solution to the puzzle of producing MU:
1. Try to work out a derivation manually on paper.
2. Have the computer apply every applicable rule to the axiom MI,
and then apply every applicable rule to the resulting theorems,
and so forth until it produces MU.
A `decision procedure` is a procedure that terminates in a finite amount of time,
either producing a derivation for the the desired theorem,
or conclusing that there is no possible derivation.
Hofstadter describes working inside the system and working outside the system, in this case the system of rules.
People make observations about what they are doing, while computers typically don't.
Can you produce MU, with or without the help of a computer?
The best way to view the entire theorem tree, as depicted in Figure 11 on page 40 of Hofstadter's book,
is to use Xholon's built-in ability to export information in YAML format.
- Click the "clsc" button at the top of this page, to load the app using the "clsc" GUI.
- Let the app run for 10 timesteps or so.
- Right-click the Axiom node in the Composite Structure Hierarchy, and
select Export > SnapshotYaml.
- This will generate content in a new tab.
<MUPuzzle/> <!-- the main active object, with a behavior -->
<ProcessQueue/> <!-- queue of theorems not yet processed by the rules -->
<String superClass="Attribute_String"> <!-- a sequence of 1+ letters of the alphabet -->
<Theorem> <!-- a string that's producible using the rules -->
<Axiom/> <!-- an initial theorem -->
<Letter superClass="Attribute_String"/> <!-- letter of the alphabet M I U -->
<MUPuzzle xhType="XhtypePureActiveObject">
<port name="processQueue" connector="../ProcessQueue"/>
<port name="strings" connector="../Strings"/>
<port name="rules" connector="../Rules"/>
<ProcessQueue implName="org.primordion.xholon.base.Queue"/>
<!-- Some example strings/theorems of the MIU-system:
<Axiom>MI</Axiom> <!-- this is the sole initial string, an axiom -->
<!-- The MIU-system "utilizes only three letters of the alphabet: M, I, U." -->
<!-- There are four rules in the MIU-system; rules are also called rules of production, or rules of inference -->
<Rule roleName="I">
<Annotation>If you possess a string whose last letter is I, you can add on a U at the end (xI → xIU).</Annotation>
<Rule roleName="II">
<Annotation>Suppose you have Mx. Then you may add Mxx to your collection (of strings) (Mx → Mxx).</Annotation>
<Rule roleName="III">
<Annotation>If III occurs in one of the strings in your collection, you may make a new string with U in place of III (xIIIy → xUy).</Annotation>
<Rule roleName="IV">
<Annotation>If UU occurs inside one of your strings, you can drop it (xUUy → xy).</Annotation>
<MIUSystembehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var beh = {
postConfigure: function() {
// set application parameters
$wnd.xh.param("MaxProcessLoops", "50"); // run the system a maximum of 50 timesteps
$wnd.xh.param("TimeStepInterval", "500"); // 2 timesteps per second
<MUPuzzlebehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
var puzzle, processQ, strings, rules;
var beh = {
postConfigure: function() {
puzzle = this.cnode.parent();
processQ = puzzle.processQueue;
strings = puzzle.strings;
rules = puzzle.rules;
act: function() {
// only process those theorems that are already in the Q at the start of the timestep
var qSize = processQ.attr("Size");
for (var i = 0; i < qSize; i++) {
var unprocessedTheorem = processQ.obj();
if (unprocessedTheorem) {
if (unprocessedTheorem.text() == "MU") {
puzzle.println("MU can be produced.");
else {
tryRules: function(theorem) {
tryRuleI: function(theorem) {
// xI → xIU
var str = theorem.text();
if (str && str.charAt(str.length-1) == "I") {
var newStr = str + "U";
this.makeNewTheorem(theorem, newStr, "I");
tryRuleII: function(theorem) {
// Mx → Mxx
var str = theorem.text();
if (str) {
var x = str.substring(1);
var newStr = "M" + x + x;
this.makeNewTheorem(theorem, newStr, "II");
// TODO this rule can be applied multiple times for "IIII" etc.
tryRuleIII: function(theorem) {
// xIIIy → xUy
var str = theorem.text();
//puzzle.println("tryRuleIII " + str);
var pos = str.indexOf("III");
if (pos != -1) {
var newStr = str.substring(0, pos) + "U";
if (str.length > pos+3) {
newStr = newStr + str.substring(pos+3);
this.makeNewTheorem(theorem, newStr, "III");
tryRuleIV: function(theorem) {
// xUUy → xy
var str = theorem.text();
var pos = str.indexOf("UU");
if (pos != -1) {
var newStr = str.substring(0, pos);
if (str.length > pos+2) {
newStr = newStr + str.substring(pos+2);
this.makeNewTheorem(theorem, newStr, "IV");
makeNewTheorem: function(parentTheorem, newStr, rule) {
var xmlStr = '<Theorem>' + newStr + '</Theorem>';
var newTheorem = parentTheorem.last();
newTheorem.role("byRule" + rule);
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="">
<rect id="MIUSystem" fill="#98FB98" height="50" width="50" x="25" y="0"/>
<rect id="MIUSystem/Strings/String" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment