(Please note there's a bit of cruft here - at least as of August 2000 - which I'd fix if I wasn't so sick of Java.)

I have written a perl program to convert from a more convenient (generic) format to HTML. It handles 5-, 6- and 7- tuple formats, and generates output in several forms - HTML (for running the applet), a bitstring for use as the tape for the universal machine, and a grammar in the form of a Post Symbol Manipulation System.

- binary addition (3 + 5)
- binary counter
- min(3, 5)
- palindrome detector (11011)
- sort (abbaaab)
- unary addition (3 + 5)
- unary subtraction (9 - 6)

LetB(n)be the maximum number of 1s that a Turing machine withnstates with the alphabet {1,B} may print on a tape that is initially blank. The problem of determiningB(n)for particular values ofnis known as thebusy beaver problem. This problem was first studied by Tibor Rado in 1962. Currently it is known thatB(1)= 1,B(2)= 4,B(3)= 6, andB(4)= 13, butB(n)is not known forn> 4.

K.H. Rosen, *Discrete Mathematics and its Applications,* 3rd
ed., Addison-Wesley, Reading, Mass., 1993.

So what we're looking for is the machine with the specified number of states that does the most work possible, with the condition that it terminates.

The problem is that the function *B(n)* is non-computable - meaning
that there is provably no algorithm that will explicitly evaluate it for
each and every value of *n*. Enumeration of all (or a
representative subset) of the (4+4*n*)^{2n} machines
with *n* states is not particularly pleasant - it leaves the tester
with the sticky situation of proving (non)termination for many
non-trivial cases - but systematic categorisation may reduce this number
to manageability (for *n* = 3, *n* = 4 see
the references).

The companion function *sigma(n)* is assigned the maximum number of
state transitions possible for a machine of *n* states with the
proviso that it terminates. Clearly *sigma(n)* determines the
halting predicate for all such machines.

States | B(n) |
sigma(n) |
Who | |
---|---|---|---|---|

java | 2 | 4 | 6 | Shen Lin / Tibor Rado |

java | 3 | 6 | 13 | Shen Lin / Tibor Rado |

java | 4 | 13 | 96 | Allen Brady |

java | 4 | 13 | 107 | Allen Brady |

- Assign a number to each symbol in the alphabet. The blank symbol is assigned the value 0.
- Using this mapping, encode each element in the state transition function of the machine as the concatenation of each component of the tupple encoded in unary notation, separated by '1's. The index of the first state is 2, and the halt state is 1. Moving left is coded as 1, right as 2, not moving as 0.
- Concatenate the bitstrings together, adding a single '1' between adjacent states. Add a '1' to the beginning and end of the entire string.
- Encode the machine's tape using the representation established in step 1, using unary numbering (using '0's) and separating individual elements with '1's. Add a '1' to the beginning and end of the entire string. (dodgy - can only initialise the right side of the tape this way - but you can fudge it - see later)
- Append the tape string to the machine string.
- Append a unary number representing the initial position of the tape head (usually zero), and add a '1' to the end of the string. (dodgy - doesn't allow negative offsets - alternately, you can prepend blanks to the tape string with blanks to shift the whole string to the right) -- re-think this

My copy of Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" came from the book:

*The Undecidable: Basic papers on undecidable propositions,
unsolvable problems and computable functions*, edited by Martin
Davis, Raven Press, 1965.

where work by other luminaries such as Gödel, Church and Kleene is
also presented. It was originally printed in the *Proceedings of the
London Mathematical Society*, ser. 2, vol 42 (1936-7), pp230-265,
with corrections published in vol 43 (1937), pp544-546 of the same
journal.

He also collaborated with Shen Lin on an article "Computer Studies of
Turing Machine Problems" in the *Journal of the Association for
Computing Machinery* for April 1965 (volume 12, number 2), pp196-212,
where the pragmatic problem of finding the busy beaver with 3 states is
discussed.

The book:

K.H. Rosen, *Discrete Mathematics and its Applications,* 3rd
ed., Addison-Wesley, Reading, Mass., 1993.

was the source of the 2-state busy beaver.

Jeffrey Shallit supplied the 3-state busy beaver in his excellent postscript handout on the busy beaver problem, which is part of his Introduction to the Theory of Computing course.

Allen Brady presents the transition tables for two 4-state busy beavers
in his article "The Determination of the Value of Rado's Noncomputable
Function *sigma(k)* for Four-State Turing Machines" in the
*Mathematics of Computation* for April 1983 (volume 40, number
162), pp647-665.

Heiner Marxin's busy beaver page has many interesting links.

« My homepage

Peter Gammie Last modified: Sun May 30 13:13:34 CEST 2004