Turing machines

Turing machines can be defined as ideal computers provided with infinite reading/writing capabilities, whose behavior is deterministically directed by a finite list of instructions called the program. Turing proved the existence in this class of a universal computing machine U with the following properties: For any Turing machine M, there is a finite program P such that U, operating under the direction of P, will compute the same results as M. The whole computer science is rooted in this fundamental theorem.

Turing machines are usually assumed to be capable of reading and writing arrays of symbols whose meanings refer to computational procedures of practical interest (algorithms). The natural environment of these machines is therefore the world of alphanumeric strings or, more in general, of the symbols of a formal language. The machines themselves, however, do not belong to this world of symbols. Even in their more abstract and schematic representations, they are thought of as formed by components belonging to an ideal world governed by deterministic laws. Because of their infinite reading/writing capabilities, devices of this sort do not actually exist, but can be well-approximated by common computers of very large storage capacity.

Turing's investigation aimed at understanding the power and the limits of mechanical computation [A. M. Turing, On Computable Numbers with an Application to the Entscheidungsproblem, Proc.London Math.Soc., 42 (230), 1936]. This problem relates strictly to Gödel's findings regarding the relationship between two different aspects of arithmetic: arithmetic as an algorithm and arithmetic as a logical theory. In particular, the fact that, in general, no Turing's machine can predict in a finite amount of time whether another Turing machine will stop in a finite amount of time (non solvability of the halting problem), is strictly related to Gödel's incompleteness theorems. For instance, the behavior of a computer is in general unpredictable, although the most common computation processes known in programming are predictable.