Turing Machines and the Busy Beaver Functions
The following is in-progress, but I want to have the basics in place.
Some time ago, I wrote a brief article about the Busy Beaver function, Turing machines, and decidability; combinatorial group theory, my field of research, tends to rub elbows a bit with computability theory, and it's something I find very fun. Somewhere along my playing with the Godot engine, I wanted to familiarize myself with how it handles animation tweens and though "hey, the tape of a Turing machine seems like a great example." So, let's get that article loosely reassembled and a Turing machine to play with!
First, a link to the Turing machine: here. And now to run through the basics of how a Turing machine works.
A Turing machine consists of:
- A tape of cells, all adjacent to each other, on which one can write symbols from a finite alphabet, with a specially designated "blank" symbol. On my Turing machine, the "blank" symbol is simply a 0.
- A head, that points at the current position and can read and write values from the alphabet. Some Turing machines, like mine, move the tape, rather than the write head, so the "move left" or "move right" instruction might feel backwards.
- A state register, which records the current state of the Turing machine, with a special "halt" state, which stops the machine.
- An instruction table, which determines three things, all based on the current state and current symbol: what symbol to write, what direction to move, and what state to transfer to.
Take some time to play with the linked Turing machine. You can control the instruction table by clicking the corresponding square, which cycles through the alphabet, state, or moving the tape left/right. You can also control the default values written on the tape, by clicking it as well. The "write" column determines what symbol will be written at the current position. The "move" column is hopefully self-evident. The "next" column determines the next state, with "H" meaning halt. Running the Turing machine in its default set-up results in: checking that the current symbol is 0, and the current state is 0, in which case the tape moves left. The next cell it reads is still 0, the state is still 0, so the tape continues moving left. As a result, we have a very boring "program:" move the tape left forever.
After you're feeling comfortable with how the Turing machine functions, try running the following program (as given by the instruction table):
| Symbol | 0 Write | 0 Move | 0 Next | 1 Write | 1 Move | 1 Next | 2 Write | 2 Move | 2 Next |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | R | 1 | 0 | R | 2 | 1 | L | 2 |
| 1 | 1 | R | H | 1 | R | 1 | 1 | L | 0 |
This basic process leads to the Busy Beaver function, BB(m,n): the m-symbol, n-state Busy Beaver function is the largest number of steps a Turing machine with exactly m symbols and n states can run before halting (but, importantly, not running forever). The previous example is the 2-symbol, n-state Busy Beaver function, BB(2,n). Focus is commonly on 2-symbol Turing machines, so usually BB(n) is understood to be a 2-symbol, n-state machine. As a small note, there are a few different things we could consider the Busy Beaver function: we could ask what the maximum number of 1s written, before halting, for example. The difference is, ultimately, not terribly material.