Turing Machine Glossary

Basic Terms

TM

Turing Machine

TM Definition

Turing Machine Definition. In order to define a TM you have to specify:

• a finite set of Symbols
• a finite set of States
• a transition function (table), i.e. a set (list) of transitions.

States that have no transitions defined, are (implicit) halt states: the TM cannot continue from there.

Symbol

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.

State

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.

Tape

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.

Cell

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.

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.

Action

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

Move

A move is that part of a transition action, which specifies how the head is moved along the tape.

Step

To perform a transition is called a "step".

Non-Basic Terms

Configuration

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.

5-tuple

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.

4-tuple

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.

Exponent

Tape cell repetition counts are also called exponents.

To the busy beaver page of Heiner Marxen. To the home page of Heiner Marxen.