Turing machine gallery

Turing machine gallery

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

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


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 [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.

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

References

See the main article Turing machine for references.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Register machine — In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Contents 1 Overview 2 Formal definition 3 …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Artificial neural network — An artificial neural network (ANN), usually called neural network (NN), is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an… …   Wikipedia

  • Culture of the United Kingdom — The Proms is an eight week summer season of daily orchestral classical music concerts, on the last night with some traditional patriotic music of the United Kingdom.[1][2] …   Wikipedia

  • Topic outline of computer science — Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is… …   Wikipedia

  • University of Cambridge — Latin: Academia Cantabrigiensis Motto Hinc lucem et pocula sacra (Latin) Motto in English …   Wikipedia

  • United Kingdom — Infobox Country conventional long name = United Kingdom of Great Britain and Northern Ireland common name = the United Kingdom symbol type = Royal coat of arms map caption = map caption |countryprefix=the |region=on the European continent… …   Wikipedia

  • History of computing — The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables. The timeline of… …   Wikipedia

  • University of Manchester — The University of Manchester Arms of the University of Manchester. The Manchester bee is the main symbol of Manchester. Motto Latin: Cognitio, sapientia, humanitas Motto in English Knowledge, Wisdom, Humanity …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”