Turing Machine Glossary

This glossary is not meant to be complete or "official". It just reflects my understanding and use of terms related to Turing machines and Busy Beavers.

Basic Terms

Turing Machine
TM Definition
Turing Machine Definition. In order to define a TM you have to specify: States that have no transitions defined, are (implicit) halt states: the TM cannot continue from there.
Each cell of a tape is marked with a symbol. Each TM defines a finite set of possible symbols.
Blank Symbol (zero symbol)
The Blank is a special symbol, used to initialize the infinitely many cells at the far left and right end of the tape.
A TM always "is in" a state. We use capital letters for states: A, B, C, ... Each TM defines a finite set of possible states.
The tape is the "memory" of a TM. It is a strip (series) of cells. It is considered to be horizontal, from left to right. It is unlimited at both ends, i.e. can contain an unbounded amount of non-blank symbols.
Empty Tape
A Tape containing only blank symbols. Busy Beavers start with an empty tape.
Cells are the constituent part of a tape. Each cell is marked with a symbol.
Tape Position
A whole number specifying exactly one cell of a tape. The initial tape position is 0, the cells at the right end have (increasing) positive tape positions, and the cells at the left side are numbered with negative tape positions.
Head (read/write head)
The read/write head of a TM identifies one cell of the tape, which is first read from and then written to as part of the action performed for a transition.
Transitions are part of the definition of a TM. This is, what a TM "does". A transition maps an input condition (state and symbol) to an output action (symbol, move and state). Cf. step.
An action is the output part of a transition. It specifies the output symbol to be written to the cell under the head, the move of the head, and the output state.
Direction (Orientation)
Either "left" (L or <) or "right" (R or >).
A move is that part of a transition action, which specifies how the head is moved along the tape.
To perform a transition is called a "step".

Non-Basic Terms

A configuration of a TM contains the complete information necessary for its further operation: tape contents, head position and state. While the definition of the TM is needed to make use of a configuration, it is normally not considered to be part of a configuration.
Busy Beaver (BB)
This term has been coined by Tibor Rado in 1962, when he announced the "busy beaver contest", the quest for the most "productive" TMs with 2 symbols and N states, started on an all empty tape. Any TM that is not surpassed by another TM with the same number of symbols and states is called a "busy beaver". The "productivity" of a TM is the number of non-blank symbols in its tape after it halts.
This is one of two common styles to define the transitions of a TM. A 5-tupel transition has 5 components: (input state, input symbol, output symbol, move, output state). This is the original notation of Alan Turing, as e.g. described by H.B.Enderton. Tibor Rado used the 5-tupel style for the Busy Beaver Contest, but it can be easily adapted to the 4-tupel style.
This is one of two common styles to define the transitions of a TM. A 4-tupel transition either contains an output symbol or a move, but not both. Such a transition has 4 components: (input state, input symbol, output symbol or move, output state).
Macro Machine (MM)
A constructed TM used to simulate another TM faster. See also my macro machine page.
Oriented State
A state constructed for a macro machine, containing an orientation of the head to indicate from which side the macro machine approaches the current symbol. See also my macro machine page.
Tape Cell Repetition Count
A (positive) number attached to tape cells to indicate how often the symbol really occurs. Such a tape cell stands for a possibly large part of the tape, containing the same symbol again and again. See also my macro machine page.
Tape cell repetition counts are also called exponents.

To the busy beaver page of Heiner Marxen.
To the home page of Heiner Marxen.
Valid HTML 3.2!

$Date: 2010/06/11 18:35:54 $

. This
. part
. intentionally
. left
. blank
. for
. better
. in-page
. jumping.