9.1 THE STANDARD TURING MACHINE
Although we can envision a variety of automata with complex and sophisticated storage devices, a Turing machine’s storage is actually quite simple. It can be visualized as a single, one-dimensional array of cells, each of which can hold a single symbol. This array extends indefinitely in both directions and is therefore capable of holding an unlimited amount of information. The information can be read and changed in any order. We will call such a storage device a tape because it is analogous to the magnetic tapes used in older computers.
Definition of a Turing Machine
A Turing machine is an automaton whose temporary storage is a tape. This tape is divided into cells, each of which is capable of holding one symbol. ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
