Overview
The Turing Machine is a conceptual model of computation developed by Alan Turing. It is a formal mathematical description that mirrors to some degree actual computing machines.
One of the primary purposes of using the Turing model is to aid in understanding which problems are computable
Intuition
The Turing machine consists of a tape that contains the inputs to the machine. The tape is a linear structure of cells, each cell contains a character in some alphabet that is used by the machine.
The tape starts at the first cell, but is infinite in length. This is done to prevent questions of computability to hinge on a lack of computer resources. The Turing machine can read the symbols from the tape, and it can write back to the tape.
In addition, the machine consists of an internal state, which governs how the computation proceeds. The internal state can change with each step of the computation, and indeed, the state will likely change as the machine reads the initial inputs from the tape.
Tape
| a | a | c | 2 | _ | _ |
Internal State
5
Definition
A Turing machine is described by the followoing elements
- A set of states, label {% Q %}
- A set of symbols, representing the alphabet used by the machine, labeled {% \Sigma %}
- A function, {% \delta : Q \times \Sigma \rightarrow Q \times \Sigma \times (l,r) %}, which determines what the machine does/. It takes the current state of the machine, the symbol from the alphabet that the tape head is currently pointed at, and it returns a new state that machine moves to, a symbol to write to the tape (where the tape head is currently pointing) and an instruction to either move the tape head either left or right.
- An element {% q_0 \in Q %} that represents the state the machine starts in
Operation
The machine starts in the state {% q_0 %}. The input to the machine is given as a series of {% n %} symbols, {% w_1w_2...w_n %} writtin on the first {% n %} entires on the tape. The machines head starts on the first (leftmost) entry on the tape. The function {% \delta %} indicates what the machine does next. It takes the state of the machine, and the symbol currently pointed to by the machines head as inputs. It returns a new state, a new symbol which is written to the tape where the head is pointing, and an action, either a left or a right move of the head.
Now the machines head points to a new position on the tape. The machine is in a new state, and the transition function now determines what happens next. This continues to iterate until the machine writes either the acceptance or rejectance symbols.