MU Puzzle

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Thu Feb 27 2014 13:31:24 GMT-0500 (EST)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: MU Puzzle
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 9221870
Keywords: 

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.

Resources
---------
http://en.wikipedia.org/wiki/MU_puzzle
http://en.wikipedia.org/wiki/Post_canonical_system
http://en.wikipedia.org/wiki/Formal_system

]]></Notes>

<_-.XholonClass>
  
  <FormalSystem>
    <PostProductionSystem>
      <MIUSystem/>    
    </PostProductionSystem>
  </FormalSystem>
  
  <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 -->
    </Theorem>
  </String>
  <Strings/>
  
  <Letter superClass="Attribute_String"/> <!-- letter of the alphabet  M I U -->
  <Letters/>
  
  <Rule/>
  <Rules/>
  
</_-.XholonClass>

<xholonClassDetails>
  <MUPuzzle xhType="XhtypePureActiveObject">
    <port name="processQueue" connector="../ProcessQueue"/>
    <port name="strings" connector="../Strings"/>
    <port name="rules" connector="../Rules"/>
  </MUPuzzle>
  <ProcessQueue implName="org.primordion.xholon.base.Queue"/>
</xholonClassDetails>

<MIUSystem>
  
  <MUPuzzle/>
  <ProcessQueue/>
  
  <!-- Some example strings/theorems of the MIU-system:
  MU
  UIM
  MUUMUU
  UIIUMIUUIMUIIUMIUUIMUIIU
  -->
  <Strings>
    <Axiom>MI</Axiom> <!-- this is the sole initial string, an axiom -->
  </Strings>
  
  <!-- The MIU-system "utilizes only three letters of the alphabet: M, I, U." -->
  <Letters>
    <Letter>M</Letter>
    <Letter>I</Letter>
    <Letter>U</Letter>
  </Letters>
  
  <!-- There are four rules in the MIU-system; rules are also called rules of production, or rules of inference -->
  <Rules>
    <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>
    <Rule roleName="II">
      <Annotation>Suppose you have Mx. Then you may add Mxx to your collection (of strings) (Mx → Mxx).</Annotation>
    </Rule>
    <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>
    <Rule roleName="IV">
      <Annotation>If UU occurs inside one of your strings, you can drop it (xUUy → xy).</Annotation>
    </Rule>
  </Rules>
  
</MIUSystem>

<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
    }
  }
]]></MIUSystembehavior>

<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;
      processQ.obj(strings.first());
    },
    
    act: function() {
      // only process those theorems that are already in the Q at the start of the timestep
      var qSize = processQ.attr("Size");
      puzzle.println(qSize);
      for (var i = 0; i < qSize; i++) {
        var unprocessedTheorem = processQ.obj();
        if (unprocessedTheorem) {
          if (unprocessedTheorem.text() == "MU") {
            puzzle.println("MU can be produced.");
          }
          else {
            this.tryRules(unprocessedTheorem);
          }
        }
      }
    },
    
    tryRules: function(theorem) {
      this.tryRuleI(theorem);
      this.tryRuleII(theorem);
      this.tryRuleIII(theorem);
      this.tryRuleIV(theorem);
    },
    
    tryRuleI: function(theorem) {
      // xI → xIU
      //puzzle.println("tryRuleI");
      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
      //puzzle.println("tryRuleII");
      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
      //puzzle.println("tryRuleIV");
      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>';
      parentTheorem.append(xmlStr);
      var newTheorem = parentTheorem.last();
      newTheorem.role("byRule" + rule);
      processQ.obj(newTheorem);
    }
    
  }
]]></MUPuzzlebehavior>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>MIUSystem</title>
    <rect id="MIUSystem" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>String</title>
      <rect id="MIUSystem/Strings/String" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>