PART II. INFINITE AUTOMATA. COMPUTABILITY — Ch. 5. The Turing Machine
As shown in the Introduction, Automata Theory considers the notion of an automaton as a formalization of the notion of a computing machine. The model of finite automata, presented in Part I, may be regarded as a general model of the class of machines with finite memory, and may serve as a standard of comparison with real computing machines, insofar as it influences their operation.
From what was shown in Part I, it could be seen that the operation of finite automata is characterized by the fact that each move of the automaton is completely determined by its internal state and by the input symbol read at that moment. In this sense the operation is rigid, the automaton having no initiative or creativity, the machine lacking the imagination and fantasy proper to human beings.
Such operation is said to have a mechanical character, hence the term “machine”. This term has a somewhat pejorative character, since automata are never considered very intelligent, the comparison taking the human being as its standard.
In order to define more precisely the notion of the mechanical operation of a real machine, two aspects must be taken into consideration. The first is that of memory, which in the case of finite automata is reduced to a finite number of internal states, that is, to finite memory. The second aspect is that of the rigidity of the rules of operation, which in the case of finite automata is maximal.
In the case of real machines, memory is usually finite, but it may be very large, and the rules of operation may be more complex. In theory, in order to discuss the notion of computability, it is useful to introduce an idealized model of a machine with infinite memory, but with completely determined rules of operation. This is the Turing machine.
In what follows, numerous references will be made to a very well-known type of real machine: the computer. The computer will serve as an intuitive model and as a point of reference for the future discussion. It is known that a computer program is nothing other than a description of the manner of processing data, in a formal language. The program describes, in a precise manner, the steps that must be executed, in the order established by its author.
The operation of the computer reproduces, in a certain sense, the operation of the abstract machine. The description, in a programming language, of the manner of processing data is a complete description, in the sense that at every moment the operation to be executed next is known. It is therefore natural to state that: any computation performed by a computer can be precisely described.
Less obvious is the converse statement: any procedure that can be precisely described can be programmed in order to be carried out by a computer. This statement is based on the work of the mathematician Alan Turing concerning computability.
In both of the above statements, the notion of “precise description” is central. Turing proposed a formalization of this notion by defining a class of ideal machines capable of executing any procedure that can be precisely described. These machines were called Turing machines.
The description of a procedure is a problem that concerned researchers even before the appearance of computers.
Obviously, the notion of description presupposes a certain language.
Can one find a language for describing all procedures? Are there procedures which, despite perfect knowledge, cannot be described?
All these questions are connected with a very important notion: effective procedure or algorithm.
