The following article is a supplement to the article

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...

Turing machine as a mechanical device

The Turing machine shown here consists of a special

paper tape Five- and eight-hole punched paper tape Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop Punched tape or perforated paper tape is a form of data storage ...

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 card A punched card (also punch card or punched-card) is a piece of stiff paper that holds digital data represented by the presence or absence of holes in predefined positions. Punched cards were once common in data processing applications or to di ...

s. Turing's biographer

Andrew Hodges Andrew Philip Hodges (; born 1949) is a British mathematician, author and emeritus senior research fellow at Wadham College, Oxford. Education Hodges was born in London in 1949 and educated at Birkbeck, University of London where he was awarded ...

(1983) has written that Turing as a child liked

typewriter A typewriter is a mechanical or electromechanical machine for typing characters. Typically, a typewriter has an array of keys, and each one causes a different single character to be produced on paper by striking an inked ribbon selective ...

s. A "'miraculous machine' -- a mechanical process which could work on

Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...

's decision problem" (Hodges p. 98) had been suggested by G. H. 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

teleprinter A teleprinter (teletypewriter, teletype or TTY) is an electromechanical device that can be used to send and receive typed messages through various communications channels, in both point-to-point (telecommunications), point-to-point and point- ...

television Television, sometimes shortened to TV, is a telecommunication Media (communication), medium for transmitting moving images and sound. The term can refer to a television set, or the medium of Transmission (telecommunications), television tra ...

scan Scan may refer to: Acronyms * Schedules for Clinical Assessment in Neuropsychiatry (SCAN), a psychiatric diagnostic tool developed by WHO * Shared Check Authorization Network (SCAN), a database of bad check writers and collection agency for bad ...

ning', and

automatic telephone exchange telephone exchange, telephone switch, or central office is a telecommunications system used in the public switched telephone network (PSTN) or in large enterprises. It interconnects telephone subscriber lines or virtual circuits of digital syste ...

connections. It was his own invention." (Hodges p. 109) Davis (2000) says that Turing built a

binary multiplier A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve com ...

out of

electromechanical In engineering, electromechanics combines processes and procedures drawn from electrical engineering and mechanical engineering. Electromechanics focuses on the interaction of electrical and mechanical systems as a whole and how the two system ...

relays (p. 170). As noted in the history section of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

punched or printed paper tape and punched paper cards were commonplace in the 1930s. Boolos and

Jeffrey Jeffrey may refer to: * Jeffrey (name), including a list of people with the name * ''Jeffrey'' (1995 film), a 1995 film by Paul Rudnick, based on Rudnick's play of the same name * ''Jeffrey'' (2016 film), a 2016 Dominican Republic documentary film ...

(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).

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

:"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 tc. (Boolos and Jeffrey (1974, 1999) p.21) This description closely follows

Emil Post Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory. Life Post was born in Augustów, Suwałki Gove ...

's "Formulation I" for a "finite combinatory process": a man, equipped with and following 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.

A robot carries out the instructions

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

. 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 hurch's thesisis 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) {{clear

Other images

File:Maquina.png, An artistic representation of a Turing Machine File:Turing Machine Model Davey 2012.jpg, Model of a Turing machine

References

See the main article

for references. Turing machine