C# Mu

Mu is a puzzle. The book Gödel, Esher, Bach looks into how thinking and self-awareness come into being. It may be that a strange loop brings into life our cognition. As an example, the mu-puzzle is presented. The book invites us to try to solve this puzzle.

This C# experiment tries to solve the mu-puzzle. It fails because the puzzle has no solution.

Puzzle

The goal of the mu-puzzle is to take the string "mi" and derive the string "mu". To do this, you can use four different rules:

1. If last letter is I, add U.
2. Duplicate set of letters after M. (Mx->Mxx)
3. Change III to U.
4. Remove UU.

C# implementation

So how can we solve this puzzle in the C# language? You can use recursion or a stack-based approach. This program uses a Stack. We also track the patterns we have already processed with a Dictionary.

Program that tries to solve MU puzzle [C#]

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	var dict = new Dictionary<string, bool>(ushort.MaxValue, StringComparer.Ordinal);
	var stack = new Stack<string>(ushort.MaxValue);
	stack.Push("MI");
	while (stack.Count > 0)
	{
	    Mu(stack.Pop(), stack, dict);
	}
    }

    static void Mu(string mu, Stack<string> stack, Dictionary<string, bool> dict)
    {
	if (mu.Length >= 20)
	{
	    return;
	}

	if (dict.ContainsKey(mu))
	{
	    return;
	}
	dict[mu] = true;

	if (mu == "MU")
	{
	    throw new Exception("Found");
	}

	// Add U if last is I.
	if (mu[mu.Length - 1] == 'I')
	{
	    stack.Push(mu + "U");
	}

	// Duplicate all after M.
	string part = mu.Substring(1);
	stack.Push(mu + part);

	// Find all instances of III.
	// Replace with U.
	for (int i = 1; i < mu.Length - 2; i++)
	{
	    if (mu[i] == 'I' &&
		mu[i + 1] == 'I' &&
		mu[i + 2] == 'I')
	    {
		// Replace it.
		string result = mu.Substring(0, i) + "U" + mu.Substring(i + 3);
		stack.Push(result);
	    }
	}

	// Find all instances of UU.
	// Remove UU.
	for (int i = 1; i < mu.Length - 1; i++)
	{
	    if (mu[i] == 'U' &&
		mu[i + 1] == 'U')
	    {
		// Remove them.
		string result = mu.Substring(0, i) + mu.Substring(i + 2);
		stack.Push(result);
	    }
	}
    }
}

What happens? The program never finds "MU" in the Stack! This means it is impossible to derive the string "MU" from "MI" using these rules.

Not possible

So, despite my best efforts, you cannot derive MU from MI with these rules. The book failed to mention this little fact and I thought the amazing C# programming language would have to be able to find some way. Unfortunately, there was no way.

Summary

The mu-puzzle is not solvable, meaning you cannot derive MU from MI. Not even computer programmers can derive MU in this way. It seems like the kind of puzzle that could be solved, if enough recursions are taken, but it just doesn't work.