Turing machines and intermediate automata

The Turing machine is a suitable model for the computational power of a computer. A Turing machine has two main parts: a finite-state machine with a head, and a tape (see illustration). The tape is infinite in both directions and is divided into squares. The head sees at any moment of time one square of the tape and is able to read the content of the square as well as to write on the square. The finite-state machine is in one of its states. Each square of the tape holds exactly one of the symbols, also called input symbols or machine characters. It is assumed that one of the input symbols is a special one, the blank, denoted by B.

Turing machine

At any moment of time, the machine, being in one of its states and looking at one of the input symbols in some square, may act or halt. The action means that, in the next moment of time, the machine erases the old input symbol and writes a new input symbol on the same square (it may be the same symbol as before, or a new symbol; if the old one was not B and the new one is B, the machine is said to erase the old symbol), changes the state to a new one (again, it is possible that the new state will be equal to the old one), and finally moves the head one square to the left, or one square to the right, or stays on the same square as before.

For some pairs of states and input symbols the action is not specified in the description of a Turing machine; thus the machine halts. In this case, symbols remaining on the tape form the output, corresponding to the original input, or more precisely, to the input string (or sequence) of input symbols. A sequence of actions, followed by a halt, is called a computation. A Turing machine accepts some input string if it halts on it. The set of all accepted strings over all the input symbols is called a language accepted by the Turing machine. Such languages are called recursively enumerable sets.

Another automaton is a nondeterministic Turing machine. It differs from an ordinary, deterministic Turing machine in that for a given state and input symbol, the machine has a finite number of choices for the next move. Each choice means a new input symbol, a new state, and a new direction to move its head.

A linear bounded automaton is a nondeterministic Turing machine which is restricted to the portion of the tape containing the input. The capability of the linear bounded automaton is smaller than that of a Turing machine.

A computational device with yet smaller capability than that of a linear bounded automaton is a push-down automaton. It consists of a finite-state machine that reads an input symbol from a tape and controls a stack. The stack is a list in which insertions and deletions are possible, both operations taking place at one end, called the top. The device is nondeterministic, so it has a number of choices for each next move. Two types of moves are possible. In the first type, a choice depends on the input symbol, the top element of the stack, and the state of the finite-state machine. The choice consists of selecting a next state of the finite-state machine, removing the top element, leaving the stack without the top element, or replacing the top element by a sequence of symbols. After performing a choice, the input head reads the next input symbol. The other type is similar to the first one, but now the input symbol is not used and the head is not moved, so the automaton controls the stack without reading input symbols. See Abstract data type

Finite-state machines

A finite-state automaton, or a finite-state machine, or a finite automaton, is a computational device having a fixed upper bound on the amount of memory it uses (unlike Turing and related machines). One approach to finite automata is through the concept of an acceptor. The finite automaton examines an input string (that is, a sequence of input symbols, located on the tape) in one pass from left to right. It has a finite number of states, among which one is specified as initial. The assumption is that the finite automaton starts scanning of input standing in its initial state. Some of the states are called accepting states. The finite automaton has a transition function (or next-state function) which maps each state and input symbol into the next state. In each step the finite automaton computes the next state and reads the next input symbol. If after reading the entire input string the last state is accepting, the string is accepted; otherwise it is rejected.