Turing Machines

(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.)

Applet

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.

Sample Turing Machines

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

Busy Beavers

Let B(n) be the maximum number of 1s that a Turing machine with n states with the alphabet {1,B} may print on a tape that is initially blank. The problem of determining B(n) for particular values of n is known as the busy beaver problem. This problem was first studied by Tibor Rado in 1962. Currently it is known that B(1) = 1, B(2) = 4, B(3) = 6, and B(4) = 13, but B(n) is not known for n > 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+4n)²ⁿ 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.

Known Busy Beavers

	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

A Universal Turing Machine

Multiple tapes

Encoding a Turing machine as a bitstring

1. Assign a number to each symbol in the alphabet. The blank symbol is assigned the value 0.
2. 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.
3. Concatenate the bitstrings together, adding a single '1' between adjacent states. Add a '1' to the beginning and end of the entire string.
4. 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)
5. Append the tape string to the machine string.
6. 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

References

Alan Turing

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.

Busy Beavers

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.