Turing Machine

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.

Each cell of a tape is marked with a symbol. Each TM defines a finite set of possible symbols.

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.

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.

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.

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.