Busy beavers

This is the third out of a series of four articles on increasingly fast-growing functions. The first article described the Ackermann function (corresponding to ω) and the Goodstein function (corresponding to ε_0). The second article went into much more detail about a specific function, namely Friedman’s TREE() function, giving an improved lower bound for TREE(3) in terms of the related tree() function. All of the functions we’ve encountered are computable, i.e. it’s theoretically possible for a computer to evaluate the function.

We use an idealised form of computer, the Turing machine. This has an unbounded tape of cells (one cell for each integer), each of which contains a symbol (typically an integer between 0 and m − 1, where m is the number of distinct symbols). Initially, all cells are initialised with the blank symbol 0. The machine starts on one of the cells of the tape, and has an initial ‘state’ (an integer between 1 and n).

  • Read the symbol σ in the cell where the machine is situated;
  • As a function of σ and the current state s of the machine, write a particular symbol in the cell, move either left or right, select a new state, and optionally halt.

Some machines halt, and others don’t. The busy beaver function S(n,m) is defined to be the longest halting time of any of the n-state m-symbol Turing machines that do halt. S(n,2) grows really fast, and will eventually overtake TREE(n) (probably before n = 1000). It grows faster than any computable function, so must therefore be uncomputable (indeed, it’s equivalent to the Halting Problem).

Here are some particular values and lower bounds for the 2-symbol busy beaver function:

Turmites

Although these machines are no more powerful than ordinary Turing machines, people have investigated generalisations where the tape is Z^2 rather than Z. The most familiar example is Langton’s Ant, which has an incredibly simple definition but takes about 10000 steps before settling into a periodic behaviour. The tape after 11528 steps is shown below, where the periodic ‘highway’ is clearly visible:

langton-ant

Someone decided to name these multi-dimensional Turing machines ‘turmites’, as a portmanteau of ‘Turing’ and ‘termites’. They behave in interesting ways, such as the one below. This generates a spiral of squares, the side lengths of which grow like the Fibonacci sequence:

golden-spiral

One can devise a busy beaver function for these two-dimensional Turing machines; Tim Hutton has collected some preliminary results. Georgi Gochev discovered a few 5-state 2-colour two-dimensional Turing machines with long lifespans.

Paterson’s worms

A particular finite class of Turing machines on the hexagonal lattice are rather interesting in the diversity of patterns they can create. For instance, one of these ‘Paterson’s worms’ produces an expanding Star of David (image courtesy of Benjamin Chaffin):

worm-1544152

Another one, ‘worm 1042020’, takes an enormous 57493855205939 steps before eventually halting to produce the following intricate configuration (zoomed out by four orders of magnitude):

worm-1042020

It was simulated to completion by Tom Rokicki, who designed a Hashlife-based algorithm to vastly accelerate the computation. There is currently only one worm with an unknown fate, known simply as ‘worm 1042015’. It doesn’t halt within 10^21 timesteps, and is extremely chaotic as far as it has been simulated.

Equivalent busy beaver functions

In the fast-growing hierarchy introduced in the first post, the busy beaver function would correspond to the Church-Kleene ordinal ω1CK. Rather than using Turing machines, there are many other definitions which achieve this growth rate. Here are two examples:

  • The diameter of the largest unit disc which can be covered by a set of n Wang tiles incapable of tiling the whole plane;
  • The longest time taken for a tree of n elementary combinators to eventually β-reduce to its minimal form.

The second of these alternatives will be explained in more detail in the fourth article, where I’ll generalise it to define a function far beyond the busy beaver function. I haven’t yet determined the ordinal corresponding to this function, but a lower bound is ω1CK^2. (I suspect this lower bound is very poor.)

Advertisements
This entry was posted in Fast-growing functions. Bookmark the permalink.

4 Responses to Busy beavers

  1. Ikosarakt says:

    Busy Beaver is not the number of steps with n-states, but number of 1’s which was wrote until Turing machine halts.

    • apgoucher says:

      Busy Beaver is the name given to the Turing machines, rather than the function. There are two relevant functions, namely S (maximum halting time) and Sigma (maximum number of non-blank symbols left on the tape by a halting machine).

  2. Pingback: Langton’s ant revisited | Complex Projective 4-Space

  3. Bo-Gyu Jeong says:

    Recently, it has been shown that S(25,2) > Graham’s number.
    Link: http://googology.wikia.com/wiki/User_blog:Deedlit11/Okay,_more_Turing_machines#A_New_Record.21_Beating_Graham.27s_number_with_a_2-symbol_TM

    (Actually, it has been shown that Sigma(25,2) > Graham’s number, but S(n,2) >= Sigma(n,2) anyway)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s