The MU Puzzle
The MU Puzzle
The MU Puzzle is a challenge introduced by Douglas Hofstadter in his book "Gödel, Escher, Bach: an Eternal Golden Braid". Given the set of axioms:Nr. Formal rule Informal explanation Example1. XI → XIU Add a U to the end of any string ending in I MI to MIU2. MX → MXX Double the string after the M MIU to MIUIU3. XIIIY → XUY Replace any III with a U MUIIIU to MUUU4. XUUY → XY Remove any UU MUUU to MUOne is asked if it's possible to recover the string MU from MI. As it turns out, this is not possible. The impossibility lies in the fact that the number of "I"s in the string is not divisible by three. From the initial string MI, one notes that the number of "I"s can only be doubled or subtracted by three, therefore:N(I) ≢ 0 (mod 3)And MU is never achieved, since in this case no "I"s are present. Stephen once wrote that his model of Physics suggests a further refinement of the Curry–Howard isomorphism, in which programs, proofs and physical systems ought to be perceived as the same kind of thing. Since this system provides such a nice example of undecidability, I thought it would be interesting to investigate it within the Wolfram Model.
MU in WM
MU in WM
The states graph for the system of axioms previously presented can be easily constructed:
muGraph=[{"MI""MIU","MI""MII","MU""MUU","MUIIIU""MUUU","MUUU""MU"},"MI",5,"StatesGraph"]
Out[]=
We already know that there is no way to construct MU from MI and so evidently, we can check that there is indeed no path in the states graph of the MU puzzle leading MI to MU:
FindShortestPath[muGraph,"MI","MU"]
In fact, the error message shows that there isn't a MU vertex at all, which would remain true for any generation of the graph.
We're more concerned about the physical interpretation of the matter at hand though. On first thought, the problem seems similar to a situation Stephen points out in a post, writing that:
"...incompleteness is ultimately just a statement of gauge dependence in mathematics. Accordingly, my basic claim is that proof theory defines a partial order on the space of all possible mathematical propositions, and choices of models are coordinatizations of the space of mathematical proofs that are analogous to the choices of gauge that allow one to construct total orders that are consistent with this partial order."
To illustrate this idea he considers the simple system “A” → “AB” and how there is a priori no path between the states "ABBA” and “AABB”:
"...incompleteness is ultimately just a statement of gauge dependence in mathematics. Accordingly, my basic claim is that proof theory defines a partial order on the space of all possible mathematical propositions, and choices of models are coordinatizations of the space of mathematical proofs that are analogous to the choices of gauge that allow one to construct total orders that are consistent with this partial order."
To illustrate this idea he considers the simple system “A” → “AB” and how there is a priori no path between the states "ABBA” and “AABB”:
CloudGet["https://wolfr.am/KXgcRNRJ"]mwGraph=ResourceFunction["MultiwaySystem"]["A""AB","AA",8,"StatesGraph",EpilogstraightFoliationLines[{1,0},{0,0},#&,{0,0}]]
Out[]=
FindShortestPath[mwGraph,"AABB","ABBA"]
Out[]=
{}
A particular gauge choice however can lead to a foliation in the states graph where "ABBA” is preceded by “AABB”:
ResourceFunction["MultiwaySystem"]["A"->"AB","AA",8,"StatesGraph",Epilog->straightFoliationLines[{1,0},{0.7,0},#&,{0,0}]]
Out[]=
This would appear to imply that the modification of the MU-puzzle to a different "gauge" of axioms would allow the puzzle to be solved.
The situation at hand is different though, since we don't even have a guarantee of the existence of MU in the entirety of the states graph. As a matter of fact, the better interpretation would be that MU lies completely outside of the light cone of MI and no boosting can make it fall within reach. And so, as Stephen points out in another section of the text, talking about non-constructive proofs:
"...one would require effective hypercomputation (corresponding to a model “traveling” at the analog of the “speed of light”) in order to be able to witness them model-theoretically."
"...one would require effective hypercomputation (corresponding to a model “traveling” at the analog of the “speed of light”) in order to be able to witness them model-theoretically."
Graph Properties
Graph Properties
It is perhaps interesting to hypothesize if the solution to the MU puzzle could've somehow be deduced from properties of the graphs themselves. The Hausdorff dimension for a particular evolution step of the states graph can be calculated to be:
muGraphStates=[{"MI""MIU","MI""MII","MU""MUU","MUIIIU""MUUU","MUUU""MU"},"MI",10,"StatesGraphStructure"]ResourceFunction["WolframHausdorffDimension"][muGraphState,All,"AllDimensions","VertexMethod"Max]
Out[]=
Out[]=
4.30022
And its adjacency matrix displays the following pattern:
MatrixPlot[AdjacencyMatrix[muGraphState]]
Out[]=
For the causal graph one has two disconnected pieces corresponding to the initial splitting “MI” → “MII” and “MI” → “MIU” :
muGraphCausal=[{"MI""MIU","MI""MII","MU""MUU","MUIIIU""MUUU","MUUU""MU"},"MI",10,"CausalGraphStructure"]
Out[]=
With adjacency matrices as follows:
The branchial graph shows no causal invariance as expected and is simply a collection of disconnected pieces:
Reaching MU would effectively mean the termination of a branch within the states graph since no axiom is provided after MU -> MUU. One might argue that the existence of MU would imply a branch sequence that go against the topology of the graph or some other intrinsic property for this class of rules in general. That would in principle correspond to the invariant property in the number of "I"s mentioned in the proof at the beginning. I attempted to pursue some patterns that could correspond to such invariant property, but was unable to find something that would correspond to an analogue of it, if it exists at all. I leave this question as an open problem.