On Jul 23, Levi Pearson wrote:
> On Tue, Jul 23, 2013 at 2:19 PM, Daniel C. <[email protected]> wrote:
> > So what I'm asking is whether it is possible to procedurally generate
> > all possible n-state Turing machines that have an alphabet of {0, 1}.
> > Obviously you would have to examine them each individually to see
> > whether they halt, but at least you'd have a list of all of them,
> > which is a finite (if large) set.
> >
> The problem with enumerating Turing Machines is the tape. You can't,
> in general, enumerate all Turing machines of n states because they
> include a finite tape that can hold an arbitrarily large finite number
> of non-blank cells. Of course, the BB problem specifically states an
> all-blank tape; I think this makes potential-BB Turing machines
> enumerable. Just enumerate all the possible 5-tuples with the {0, 1}
> alphabet and n states, and there you go.
The tricky part is that each potential BB machine consists of multiple
5-tuples. To be precise, 2*n such tuples, one for each (state, symbol)
input pair. For each tuple, there are 4*(n+1) possible combinations of
the (symbol, direction, state) output pair. Raise the number of outputs
to the power of the number of inputs, and you get the number of
potential machines: (4*(n+1))^(2*n)
Once you have the number of machines, it's simple to translate any or
each number in that range to a set of states, with division and modulus
operations. To be fair, those operations will be on huge numbers, so
you'll need some sort of bignum implementation for anything over 6;
Python is convenient:
from itertools import product
try:
range = xrange
except NameError:
pass
def bb(states):
halt = "-"
symbols = "01"
directions = "LR"
outstates = states + halt
n = len(states)
s = len(symbols)
d = len(directions)
for i in range((d*s*(n+1))**(s*n)):
machine = []
for state, symbol in product(states, symbols):
i, newstate = divmod(i, n+1)
i, newdir = divmod(i, d)
i, newsym = divmod(i, s)
machine.append((
state,
symbol,
symbols[newsym],
directions[newdir],
outstates[newstate],
))
yield machine
def main():
try:
for machine in bb("ABC"):
print(["".join(c) for c in machine])
except KeyboardInterrupt:
pass
except IOError:
pass
if __name__ == "__main__":
main()
This has been generalized a bit more than you strictly require; for
example; the divmod operations for direction and output symbol could be
rewritten as single bit checks and a right shift.
The list of 64 single-state machines is relatively easy to verify by
hand. Beyond that, the numbers get huge fast:
2: 20736
3: 16777216
4: 25600000000
5: 63403380965376
6: 232218265089212416
7: 1180591620717411303424
8: 7958661109946400884391936
9: 68719476736000000000000000000
So fast that my machine takes three and a half minutes to dump the set
of three-state machines into /dev/null, so it would theoretically be
three and a half *days* to list the four-state machines, and twenty-five
years for five-state. Fortunately, the real work is embarrassingly
parallel. In fact, even the conversion of a number to a machine can be
parallelized.
I would be curious to see how many of those states can be ruled out just
by looking at the state graph. Many of them don't even have a halt
condition; others never output a 1; yet others wouldn't have a viable
transition route from the start state to a halt and/or 1 state.
One could also eliminate anything with disconnected state nodes, given
that they would emulate a machine with fewer states. So would a machine
with multiple dead ends in the state graph, though that might be harder
to check.
I'm less certain about graphs where nothing transitions back to the
initial state. It feels like such a machine, if it would ever halt,
could output at most one more tick than a machine of fewer states.
Generalizing, it's probable that each state needs a path to each of the
other states, but I'm not entirely certain that's provable.
Beyond that, one could throw out any machine isomorphic to a machine
with a smaller number, by permuting the symbols of the non-initial
states and reversing the divmod logic. Even if it's a busy beaver, it
gives you no new information. It might even be possible to construct a
new enumeration without isomorphic results, but that's probably harder
than throwing them out after the fact.
Anything else? Is it possible to discover Christmas trees or other
non-halting machines without running them?
- Eric
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
