Monday, September 11, 2006

Hunting beavers: exhaustive generation without isomorphism

In the previous post, I decided to narrow my brute-force search for the 5-node Busy Beaver down to a smaller number of 5-node machines that at least stood a fair chance of halting and used all 5 states. I haven't proved this simplification doesn't exclude the Busy Beaver machine, but I have a strong intuition it doesn't.

The graph-theoretic reformulation

To make the search tractable, we're going to represent the busy beaver Turing machine with a graph. There are two symbols in the alphabet of the Turing machine, so each node in the graph representing a Turing machine "state" should have two outgoing edges. To guarantee that the machine at least contains a HALT instruction, add another node "E" representing the HALT instruction, and stipulate that there must be a path between the start node "S" and the HALT state "E". The situation: Suppose we have a directed graph of n nodes that allows loops and self-loops. Two nodes are distinguished: S and E. There must be a path from every node but E to E. All the nodes but E have two outgoing edges; E must have none. The question: How many non-isomorphic graphs of this form are there? The answer: 65 = 7,776 graphs. Few enough to be tractable!

Ugly details

Where did the magic 65 come from? A chain from S to E must exist, so start there. We can additionally ensure that every node has a path to E by having the chain from S to E run through every node:
The "backbone" of the isomorphism guarantees at least one HALT instruction and gives the machine a chance at reaching it
S 2 3 n E
? ? ? ? ?
That takes care of half the edges. The other n edges each choose one of the n+1 nodes independently, for a total of (n+1)n possibilities.

Applying the results

For each distinct graph found above, a number of machines can be generated by annotating the edges. For example, an annotation "1:1L" means "if I read a one, write a one, move the head left, and transition the Turing machine to the state at the end of this line." There are 2×4×4 = 32 possible annotation sets for each node, putting the solution space at 32n(n+1)n; a whopping 65325 (that's a 26-digit number in decimal!). Still too big to brute force, but still much smaller than the unrestricted solution space of (2n)8n (1040). The restrictions tighten the solution space by roughly 14 orders of magnitude for the n=5 case. Given that the constraints enforce the presence of at least one HALT, and the use of the entire 5 states of the machine, it's easy to see why the stochastic method over the unrestricted state space fails to find answers. The chances of hitting on one of the machines that fits the constraints is roughly 1 to 1014 against; given that the constraint machines aren't guaranteed to halt makes this statistic even more abysmal. Note that this approach still overgenerates. It's easy to see if both outgoing edges of a node lead to the same node that there are only 16 possible labels for the node's edges. The graph approach looks promising. Possibly there are further sensible constraints that would reduce the number of potential non-isomorphic graphs


Post a Comment

<< Home