ABSTRACT

Artificial intelligence.—A Turing machine is a model (→MODEL) of computing imagined by the mathematician Alan Turing. It is an extension of the concept of automaton (see below): input symbols are recorded on a “tape” and transitions between states cause the “reading head” to move on the tape and, whenever necessary, change the symbols marked on it (→ SYMBOL). It would be pointless to actually build such a device, since the model cannot be used to perform practical computations. Nevertheless, the theoretical possibility of building one has played an important role in demonstrating the computability of many classes of problems.