Turing Machines

Alan Turing's formalisation of computation forms the basis of many surprising results in theoretical computer science. Here I have collected some sample machines, some of the more interesting results, and simple developments of some of them.

(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

The applet used to execute the examples below is available with source code as a jarball. Its written in Java 1.1.5; I know it crashes Netscape 4.x for Linux, but it appears to work fine under JDK1.1.5 and on other platforms (Solaris, OSF1).

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

Here are a few sample Turing machines collected from various places. Their main utility is to illustrate some of the common programming paradigms.

Busy Beavers

So what are they, anyway? Try this definition I found in my discrete maths textbook:

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

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

This section is far from complete.

Multiple tapes

The power of multi-tape Turing machines is no greater than their traditional single-tape counterparts, which can be shown by a constructive proof. This allows us to employ the convenient tactic of splitting the source machine, data and working space onto three separate storage media, while remaining confident that the power of the implementation is unchanged.


Encoding a Turing machine as a bitstring

The aim of this step is to represent any quintuple Turing machine (using a single tape and an arbitrary alphabet) as a string of symbols taken from the set {0,1}. This would then be suitable input for a universal machine, and can also be considered to be the unique binary number identifying a particular machine. (note that the encoding described below is one-to-one but not onto).
  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

The Alan Turing Home Page is the work of Andrew Hodges, author of Alan Turing: the Enigma. The book makes fascinating reading, and is definitely the authoritative biography of the great man, although I feel it could have focussed more on his achievements as a mathematician rather than promoting him as a social radical.

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

Tibor Rado's original article "On non-computable functions", where he defines the "Busy Beaver game" can be found in The Bell System Technical Journal for May 1962 (volume 41), pp 877-884.

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