Busy Beaver code (version 0.1)

Background

This is the code used to derive the current results. Please note though that this is very much a backend system, and an experimental system rather than a finished product; any pretence to nice interfaces and general useability issues are long gone! There is probably a project in the development of something vaguely usable from this backend for an appropriately qualified enthusiast ...

Please also note that this code is sometimes ugly, and can probaby be optimised and improved in all sorts of ways. Please let me know of any ideas you may have. I will be continually adding both the code and documentation, which will hopefully make things less obscure as time goes on ...

The terminology below is consistent with my papers on the topic. What follows is likely to be nearly incomprehensible if you haven't read at least one of these ...

Software

The above link will download a zip file. Put this in a directory somewhere, unzip it, and once you have Ciao Prolog running, you are ready to go.

Getting Started

To start things up, start Ciao Prolog and load the file engine.pl, as below.

Thss will load and compile several files. You may find that there are some warning messages; you can safely ignore these (these are basically comments on my coding style :-)

You can now use the program by making queries to the Prolog shell.

Emulating a particular machine.

This can be done in two ways. The first way is the naive one, ie to execute each step in exactly the way that the Turing machine would. To do this, a query such as the following should be used.

This runs the machine M (which is a 5-state machine of productivity 1,471 which terminates in 2,358,064 steps) for a maximum of 10 million steps in naive mode, and if successful returns the values Ones (the productivity), Hops (the number of steps), Status (halts, going, etc.) and Outputs (sundry information, generally of interest only to hard-core specialists).

Currently, k must be fixed in advance, and so a small amount of experimentation may need to be done to find the right value of k for each machine. I am currently working on an "adaptive" mode, which will overcome this limitation.

For example, to run the m7 machine above with k = 2, one would use

The general form of a call to emulate is

Bound can be either given explicitly, or as mill(N) for N million, or bill(N) for N billion (for a particular natural number N). Options is a list of zero or more of the following:

Hence to run the above machine for up to 10 billion steps with a macro machine of size 3 whilst printing out the machine configuration whenever the machine is in state b with input 1, we could use

Analysing a particular machine

• Static loop checking For example, any machine which has a transtion for state b with input 0 in whicg the new state is b and the direction is r will loop forever. Hence any machine containing this transition is easily determined to loop. There are various other transitions and combinations of transitions which are checked in a similar manner.
  
  
• Checking that the halt state is unreachable For example, consider a machine containing the transitions

  t(a,0,1,r,b)
  t(b,1,1,l,c)
  t(c,0,1,r,h)
  

  and assume that there are no other transitions which result in state b or c. Hence the only way to execute the halt transition is to run these three transitions in the order given. So we must have {a}01 -> 1{b}1 -> {c}11, which of course means that we do not execute the halt transition. Thus the machine can never halt.

• Historical analysis for "travelling loops" The machine is run for a set number of transitions (say 100) and then a trace of the execution is analysed. If the machine repeatedly shifts a configuration in one direction, then this behaviour, under some simple conditions, can be inferred to continue forever.
  
  
• Historical analysis for an inductive proof of non-termination. This involves finding patterns in the execution trace, and making inductive conjectures based on them. These conjectures are then evaluated by emulating the machine in "hypothetical" mode, ie starting at a given configuration, and showing that another configuration is reached from it.

  For example, if we establish that the following configurations occur in a trace

  11{c}1, 11{c}111, 11{c}11111

  then one reasonable conjecture is that the pattern 11{c}1(11)^m occurs infinitely often in the trace (ie for any m &ge 0). Hence our inductive conjecture is that for any m &ge 0, the configuration 11{c}1(11)^m results in the configuration 11{c}111(11)^m, ie 11{c}1(11)^m+1. If we can establish this, then the machine does not terminate. The computation of whether the smaller version of the pattern leads to the larger one is done by the hypothetical engine.

  The hypothetical engine itself has a number of heuristics for evaluating machine configurations which contain variables. These are constanly being refined!

• Emulation for a large number of steps. This is the final "Hail Mary" before giving up on the analysis. This is designed to catch "monster" machines, which may defy all analysis, but still terminate after a large number of steps.

Hence to analyse the above machine, we would use the query

For searches of dimension 8 or less (ie the number of states in the machine multiplied by the number of tape symbols is 8 or less), the machines generated can be kept in one file. For larger searches (5 states 2 symbols, 3 states 3 symbols, and 2 states 5 symbols), there are millions of machines, and hence the machines have to be stored in several files. We have not attempted any searches of dimension more than 10.

To generate and analyse all machines with say 3 states and 2 symbols, use

...
bb(3,[t(a,0,1,r,b),t(b,0,1,l,c),t(c,1,1,r,c),t(c,0,1,l,a),t(a,1,0,l,a),t(b,1,1,r,h)],0,0,meander).
bb(3,[t(a,0,1,r,b),t(b,0,1,l,c),t(c,1,1,r,c),t(c,0,1,l,a),t(a,1,1,l,a),t(b,1,1,r,h)],4,9,halts).
bb(3,[t(a,0,1,r,b),t(b,0,1,l,c),t(c,1,1,r,c),t(c,0,1,l,a),t(a,1,0,r,a),t(b,1,1,r,h)],2,9,loops(dizzyduck(7))).
bb(3,[t(a,0,1,r,b),t(b,0,1,l,c),t(c,1,1,l,c),t(c,0,1,r,a),t(a,1,1,r,a),t(b,1,1,r,h)],0,1,loops(induction(p([],8),pos(1,2),state([1,tape([1,1,1],v(_46542,0,1,1,3))],b,l,[0]),state([1,1,1,1,tape([1,1,1],v(_46542,0,1,1,3))],b,l,[0])))).
...

The most important piece of data is the final argument, which is the analysis status. If this is "halts", the previous two arguments are the productivity and number of steps to termination respectively. In other cases, they are generally meaningless. Note that the last case also records the successful inductive conjecture, which in this case was

(111)^m 1 {b} 0 -> (111)^m 1111 {b} 0

Some summary information can also be found at the of the file.

One "sanity check" that is possible for searches of small dimension (certainly 6 or less and possibly up to 8) is to freely generate all machines, and then compare the results of the analysis of this case with the previous one. For example, when searching the 2-state 2-symbol case (the simplest by far!), we find that the restricted method (ie the one described above with filters for machines which make the tape blank, or loop) generates 12 machines, but the free one generates 64 machines. By comparing these two lists, we can conclude that at least in this case, our pruning heuristics are correct.

To do this, we use the query

Sometimes it is useful to perform one search, and use the results to improve the search heuristics. Rather than re-generate many known results, it is possible to refine a particular output file (which is the reason for the rather esoteric format of the results files).

Compiling Particular Machines

The emulate routine described above is a general one; it will take any machine (in the right format) and emulate it. Sometimes for some monster machines it is more appropriate (purely on efficiency grounds) to compile these particular machines, rather than emulate them. In other words, we generate a particular program from the machine specification, rather than use the machine specification as the input to a program which is equivalent to a universal Turing machine.

The particular implementation here is rather simplistic version of the macro machines of Marxen and Buntrock. The translator produces a number of Prolog clauses, equivalent to the original machine, which can then be loaded into the Prolog system and the machine executed. For example, to compile 3-state 3-symbol machine (recently discovered by the Ligockis), use the following query.

The second argument specifies the macro size; the first the name of the file in which the output will be written; the third is the machine itself.

Once the file has been generated, load it into the same Prolog shell as the existing code. You can do this as below.

You can then execute the machine with the query below.