Turing machine gallery

From Wikipedia, the free encyclopedia

An artistic representation of a Turing Machine.

The following article is a supplement to the article Turing machine.

[edit] Turing machine as a mechanical device

The Turing machine shown here consists of a special paper tape that can be erased as well as written with a "tally mark". Perhaps the TABLE is made out of a similar "read only" paper tape reader, or perhaps it reads punched-cards. Turing's biographer Hodges (1983) has written that Turing as a child liked typewriters. A "'miraculous machine' -- a mechanical process which could work on Hilbert's decision problem" (Hodges p. 98) had been suggested by Hardy, one of Turing's teachers. Nevertheless,

"His machine had no obvious model in anything that existed in 1936, except in general terms of the new electrical industries, with their teleprinters, television 'scanning', and automatic telephone exchange connections. It was his own invention."(Hodges p.109)

Davis (2000) says that Turing built a binary multiplier out of electromechanical relays (p. 170). As noted in the history section of algorithm punched or printed paper tape and punched paper cards were commonplace in the 1930's.

Boolos and Jeffrey (1974, 1999) note that "being in one state or another might be a matter of having one or another cog of a certain gear uppermost..." (p. 21).

[edit] Turing machine as a "poor mug" inside a box pulling the box along a rail

A poor mug in a box, reading, writing, erasing per his list of instructions. After Boolos and Jeffrey figure 3-1, p. 21

"We are not concerned with the mechanics or the electronics of the matter. Perhaps the simplest way to picture the thing is quite crudely: Inside the box there is a man, who does all the reading and writing and erasing and moving. (The box has no bottom: the poor mug just walks along between the ties, pulling the box with him.) The man has a list of m instructions written down on a piece of paper. He is in state qi when he is carrying out instruction number i [etc.]" (Boolos and Jeffrey (1974, 1999) p.21)

This description closely follows Emil Post's "Formulation I" for a "finite combinatory process": a man, equipped with and following a "a fixed unalterable set of instructions", moving left or right through "an infinite sequence of spaces or boxes" and while in a box either printing on a piece of paper a single "vertical stroke" or erasing it (Post 1936 reprinted in Undecidable p.289). Post's formulation was the first of its type to be published; it preceded Turing's by a matter of a few months.

Both descriptions-- Post's and Boolos and Jeffrey's — use simpler 4-tuples rather than 5-tuples to define the 'm-configurations' (instructions) of their processes.

[edit] A robot carries out the instructions

This is a robot with a console enlisted to work as a two-symbol three-state Busy Beaver. Robot is working on a tape initially printed with 0/blanks. Robot has looked at the symbol in the window (symbol 0), has read the instruction ("state") C and is about to PRINT a 1. Then it will push the tape-LEFT button. Lastly it will look toward instruction ("state") B. (The print/erase mechanism is out of sight, beneath the window. Maybe the tape is clear and the mechanism pulls off sticky 0's and sticks on 1's to PRINT and vice versa to ERASE.)

This model was suggested by Stone (1972):

"Let us adopt the point of view that a computer is a robot that will perform any task that can be described as a sequence of instructions" (p. 3).

Stone uses the robot to develop his notion of algorithm. This in turn leads him to his description of the Turing machine and his statement:

"The evidence seems to indicate that every algorithm for any computing device has an equivalent Turing machine algorithm ... if [Church's thesis] is true, it is certainly remarkable that Turing machines, with their extremely primitive operations, are capable of performing any computation that any other device can perform, regardless of how complex a device we choose." (p. 13)

[edit] References

See the main article Turing machine for references.