Turing Machine
In 1936 English mathematician and computer theorist Alan Turing (1912-1954), while studying at Cambridge University, began work in predicate logic. His studies led in 1937 to a proof that certain mathematical problems could be solved by automation. Turing postulated a universal machine--the Turing machine, which would function by passing through a series of discrete states or steps, assuming only one of a possibly infinite list of internal states at any given moment.
Turing described his machine in the paper On Computable Numbers with an Application to the Entscheidungsproblem ("decidability problem"). The Turing Machine consists of the following components: (1) An infinitely long input/output tape stretched like a scroll between rollers so it can be wound forwards and backwards. The tape is marked off into squares, each marked with a 0 or 1. (2) A read/write head that sits above the tape, scanning one symbol at a time, and is always in a particular internal state (which it indicates by displaying a number on its exterior). The head has the ability to read, write, or erase any single square on the input/output tape, and may change to another internal state at any moment. (3) The rule list, stored in the read/write head, which determines the machine's changes of state at any particular point.
The machine begins computation in some given state. It then scans a 0 or 1 from the tape, either leaving that symbol alone or replacing it with its opposite state; finally, it moves to the next square on the tape (scrolling the tape left or right, depending on the machine's internal state). The machine's behavior thus depends on three factors: (1) The machine's state. (2) The number on the scanned square. (3) The rule list. The rule list specifies, for each internal state and binary input, what the machine should write, which direction it should move in, and which state it should go into. For example, suppose the machine is in state 32 and the head reads a 0. The machine consults its rule list and finds rule "32-0-17-R," which means: "If you are in state 32 and read a 0, then change to state 17 and advance the tape head to the right." The output of the machine could be read off the appropriate parts of the tape once the machine had stopped.
One problem with Turing machines, it seems, is that a different machine would have to be constructed for every new computation: that is, a new rule list would have to be built into the device. But Turing realized that any algorithm, or set of procedures for accomplishing some computational task, can be written as a set of instructions. A "universal" Turing machine can thus be constructed to do, if supplied with the proper sequence of instructions (on the tape), what any other particular Turing machine can do. In other words, one machine can be programmed for all possible tasks, for the 1s and 0s on a tape can the behavior of any machine.
The concept of the Turing machine is the foundation of the modern theory of computation. Indeed, the universal Turing machine embodies the essential principle of the computer: a single machine can perform any well-defined task if supplied with the appropriate program. The Turing machine is considered the theoretical prototype of the digital computer because it incorporates the computer's key processing features: (1) input/output device (tape and reader), (2) memory (read/write head or control mechanism storage), and (3) central processing unit (control mechanism that interprets the rules vis-à-vis the input bits). Although an actual Turing machine would never be built, as a thought-experiment which reduces the concept of computation to its ultimate, stripped-down extreme it has proved essential to the theory of computation.
This is the complete article, containing 618 words
(approx. 2 pages at 300 words per page).
