A
Contents 1 Overview 1.1 Physical description 2 Informal description 3 Formal definition 4 Additional details required to visualize or implement Turing machines 4.1 Alternative definitions
4.2 The "state"
4.3
5 Models equivalent to the
8.1 Limitations of Turing machines 8.1.1 Computational complexity theory 8.1.2 Concurrency 8.1.3 Interaction 9 History 9.1 Historical background: computational machinery
9.2 The
10 See also 11 Notes 12 References 12.1 Primary literature, reprints, and compilations
12.2
13 External links Overview[edit]
A
...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.[17] (Turing 1948, p. 3[18]) Informal description[edit]
For visualizations of Turing machines, see
The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q4) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.) Here, the internal state (q1) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its complete configuration) consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.) More precisely, a
A tape divided into cells, one next to the other. Each cell contains a
symbol from some finite alphabet. The alphabet contains a special
blank symbol (here written as '0') and one or more other symbols. The
tape is assumed to be arbitrarily extendable to the left and to the
right, i.e., the
Either erase or write a symbol (replacing aj with aj1). Move the head (which is described by dk and can have values: 'L' for one step left or 'R' for one step right or 'N' for staying in the same place). Assume the same or a new state as prescribed (go to state qi1). In the 4-tuple models, erasing or writing a symbol (aj1) and moving the head left or right (dk) are specified as separate instructions. Specifically, the table tells the machine to (ia) erase or write a symbol or (ib) move the head left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state then the machine will halt; other models require all entries to be filled. Note that every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space. Formal definition[edit] Following Hopcroft and Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple M = ⟨ Q , Γ , b , Σ , δ , q 0 , F ⟩ displaystyle M=langle Q,Gamma ,b,Sigma ,delta ,q_ 0 ,Frangle where Q displaystyle Q is a finite, non-empty set of states; Γ displaystyle Gamma is a finite, non-empty set of tape alphabet symbols; b ∈ Γ displaystyle bin Gamma is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation); Σ ⊆ Γ ∖ b displaystyle Sigma subseteq Gamma setminus b is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents; q 0 ∈ Q displaystyle q_ 0 in Q is the initial state; F ⊆ Q displaystyle Fsubseteq Q is the set of final states or accepting states. The initial tape contents is said to be accepted by M displaystyle M if it eventually halts in a state from F displaystyle F . δ : ( Q ∖ F ) × Γ → Q × Γ × L , R displaystyle delta :(Qsetminus F)times Gamma rightarrow Qtimes Gamma times L,R is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) If δ displaystyle delta is not defined on the current state and the current tape symbol, then the machine halts;[21] Anything that operates according to these specifications is a Turing
machine.
The 7-tuple for the 3-state busy beaver looks like this (see more
about this busy beaver at
Q = A , B , C , HALT displaystyle Q= mbox A , mbox B , mbox C , mbox HALT (states); Γ = 0 , 1 displaystyle Gamma = 0,1 (tape alphabet symbols); b = 0 displaystyle b=0 (blank symbol); Σ = 1 displaystyle Sigma = 1 (input symbols); q 0 = A displaystyle q_ 0 = mbox A (initial state); F = HALT displaystyle F= mbox HALT (final states); δ = displaystyle delta = see state-table below (transition function). Initially all tape cells are marked with 0 displaystyle 0 . State table for 3 state, 2 symbol busy beaver Tape symbol Current state A Current state B Current state C Write symbol Move tape Next state Write symbol Move tape Next state Write symbol Move tape Next state 0 1 R B 1 L A 1 L B 1 1 L C 1 R B 1 R HALT Additional details required to visualize or implement Turing machines[edit] In the words of van Emde Boas (1990), p. 6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like." For instance, There will need to be many decisions on what the symbols actually look
like, and a failproof way of reading and writing symbols indefinitely.
The shift left and shift right operations may shift the tape head
across the tape, but when actually building a
Alternative definitions[edit] Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, changing the set L , R displaystyle L,R to L , R , N displaystyle L,R,N , where N ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right, does not increase the machine's computational power. The most common convention represents each "Turing instruction" in a "Turing table" by one of nine 5-tuples, per the convention of Turing/Davis (Turing (1936) in The Undecidable, p. 126-127 and Davis (2000) p. 152): (definition 1): (qi, Sj, Sk/E/N, L/R/N, qm) ( current state qi , symbol scanned Sj , print symbol Sk/erase E/none N , move_tape_one_square left L/right R/none N , new state qm ) Other authors (Minsky (1967) p. 119, Hopcroft and Ullman (1979) p. 158, Stone (1972) p. 9) adopt a different convention, with new state qm listed immediately after the scanned symbol Sj: (definition 2): (qi, Sj, qm, Sk/E/N, L/R/N) ( current state qi , symbol scanned Sj , new state qm , print symbol Sk/erase E/none N , move_tape_one_square left L/right R/none N ) For the remainder of this article "definition 1" (the Turing/Davis convention) will be used. Example: state table for the 3-state 2-symbol busy beaver reduced to 5-tuples Current state Scanned symbol Print symbol Move tape Final (i.e. next) state 5-tuples A 0 1 R B (A, 0, 1, R, B) A 1 1 L C (A, 1, 1, L, C) B 0 1 L A (B, 0, 1, L, A) B 1 1 R B (B, 1, 1, R, B) C 0 1 L B (C, 0, 1, L, B) C 1 1 N H (C, 1, 1, N, H) In the following table, Turing's original model allowed only the first three lines that he called N1, N2, N3 (cf. Turing in The Undecidable, p. 126). He allowed for erasure of the "scanned square" by naming a 0th symbol S0 = "erase" or "blank", etc. However, he did not allow for non-printing, so every instruction-line includes "print symbol Sk" or "erase" (cf. footnote 12 in Post (1947), The Undecidable, p. 300). The abbreviations are Turing's (The Undecidable, p. 119). Subsequent to Turing's original paper in 1936–1937, machine-models have allowed all nine possible types of five-tuples: Current m-configuration (Turing state) Tape symbol Print-operation Tape-motion Final m-configuration (Turing state) 5-tuple 5-tuple comments 4-tuple N1 qi Sj Print(Sk) Left L qm (qi, Sj, Sk, L, qm) "blank" = S0, 1=S1, etc. N2 qi Sj Print(Sk) Right R qm (qi, Sj, Sk, R, qm) "blank" = S0, 1=S1, etc. N3 qi Sj Print(Sk) None N qm (qi, Sj, Sk, N, qm) "blank" = S0, 1=S1, etc. (qi, Sj, Sk, qm) 4 qi Sj None N Left L qm (qi, Sj, N, L, qm) (qi, Sj, L, qm) 5 qi Sj None N Right R qm (qi, Sj, N, R, qm) (qi, Sj, R, qm) 6 qi Sj None N None N qm (qi, Sj, N, N, qm) Direct "jump" (qi, Sj, N, qm) 7 qi Sj Erase Left L qm (qi, Sj, E, L, qm) 8 qi Sj Erase Right R qm (qi, Sj, E, R, qm) 9 qi Sj Erase None N qm (qi, Sj, E, N, qm) (qi, Sj, E, qm) Any Turing table (list of instructions) can be constructed from the
above nine 5-tuples. For technical reasons, the three non-printing or
"N" instructions (4, 5, 6) can usually be dispensed with. For examples
see
Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the state of the system may be described by a single expression (sequence of symbols) consisting of the symbols on the tape followed by Δ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression is called the 'state formula'. — The Undecidable, pp. 139–140, emphasis added Earlier in his paper Turing carried this even further: he gives an
example where he placed a symbol of the current
"m-configuration"—the instruction's label—beneath the scanned
square, together with all the symbols on the tape (The Undecidable,
p. 121); this he calls "the complete configuration" (The
Undecidable, p. 118). To print the "complete configuration" on
one line, he places the state-label/m-configuration to the left of the
scanned symbol.
A variant of this is seen in Kleene (1952) where Kleene shows how to
write the
1A1 This means: after three moves the tape has ... 000110000 ... on it,
the head is scanning the right-most 1, and the state is A. Blanks (in
this case represented by "0"s) can be part of the total state as shown
here: B01; the tape has a single 1 on it, but the head is scanning the
0 ("blank") to its left and the state is B.
"State" in the context of Turing machines should be clarified as to
which is being described: (i) the current instruction, or (ii) the
list of symbols on the tape together with the current instruction, or
(iii) the list of symbols on the tape together with the current
instruction placed to the left of the scanned symbol or to the right
of the scanned symbol.
Turing's biographer
The table for the 3-state busy beaver ("P" = print/write a "1") Tape symbol Current state A Current state B Current state C Write symbol Move tape Next state Write symbol Move tape Next state Write symbol Move tape Next state 0 P R B P L A P L B 1 P L C P R B P R HALT The "3-state busy beaver"
To the right: the above table as expressed as a "state transition" diagram. Usually large tables are better left as tables (Booth, p. 74). They are more readily simulated by computer in tabular form (Booth, p. 74). However, certain concepts—e.g. machines with "reset" states and machines with repeating patterns (cf. Hill and Peterson p. 244ff)—can be more readily seen when viewed as a drawing. Whether a drawing represents an improvement on its table must be decided by the reader for the particular context. See Finite state machine for more. The evolution of the busy-beaver's computation starts at the top and proceeds to the bottom. The reader should again be cautioned that such diagrams represent a
snapshot of their table frozen in time, not the course ("trajectory")
of a computation through time and space. While every time the busy
beaver machine "runs" it will always follow the same state-trajectory,
this is not true for the "copy" machine that can be provided with
variable input "parameters".
The diagram "Progress of the computation" shows the three-state busy
beaver's "state" (instruction) progress through its computation from
start to finish. On the far right is the Turing "complete
configuration" (Kleene "situation", Hopcroft–Ullman "instantaneous
description") at each step. If the machine were to be stopped and
cleared to blank both the "state register" and entire tape, these
"configurations" could be used to rekindle a computation anywhere in
its progress (cf. Turing (1936) The Undecidable, pp. 139–140).
Models equivalent to the
...whose motion is only partially determined by the configuration ... When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. — The Undecidable, p. 118 Turing (1936) does not elaborate further except in a footnote in which he describes how to use an a-machine to "find all the provable formulae of the [Hilbert] calculus" rather than use a choice machine. He "suppose[s] that the choices are always between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i1, i2, ..., in (i1 = 0 or 1, i2 = 0 or 1, ..., in = 0 or 1), and hence the number 2n + i12n-1 + i22n-2 + ... +in completely determines the proof. The automatic machine carries out successively proof 1, proof 2, proof 3, ..." (Footnote ‡, The Undecidable, p. 138) This is indeed the technique by which a deterministic (i.e. a-) Turing machine can be used to mimic the action of a nondeterministic Turing machine; Turing solved the matter in a footnote and appears to dismiss it from further consideration. An oracle machine or o-machine is a Turing a-machine that pauses its computation at state "o" while, to complete its calculation, it "awaits the decision" of "the oracle"—an unspecified entity "apart from saying that it cannot be a machine" (Turing (1939), The Undecidable, p. 166–168). Universal Turing machines[edit] Main article: Universal Turing machine An implementation of a Turing machine As Turing wrote in The Undecidable, p. 128 (italics added): It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine M, then U will compute the same sequence as M. This finding is now taken for granted, but at the time (1936) it was considered astonishing. The model of computation that Turing called his "universal machine"—"U" for short—is considered by some (cf. Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the stored-program computer. Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it. — Minsky (1967), p. 104 In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and R. E. Stearns. (Arora and Barak, 2009, theorem 1.9) Comparison with real machines[edit] A
It is often said[who?] that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is neglected in this statement is that, because a real machine can only have a finite number of configurations, this "real machine" is really nothing but a linear bounded automaton. On the other hand, Turing machines are equivalent to machines that have an unlimited amount of storage space for their computations. However, Turing machines are not intended to model computers, but rather they are intended to model computation itself. Historically, computers, which compute only on their (fixed) internal storage, were developed only later. There are a number of ways to explain why Turing machines are useful models of real computers: Anything a real computer can compute, a
An experimental prototype of a Turing machine Limitations of Turing machines[edit]
Computational complexity theory[edit]
Further information: Computational complexity theory
A limitation of Turing machines is that they do not model the
strengths of a particular arrangement well. For instance, modern
stored-program computers are actually instances of a more specific
form of abstract machine known as the random-access stored-program
machine or RASP machine model. Like the universal
This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2015) (Learn how and when to remove this template message) Another limitation of Turing machines is that they do not model
concurrency well. For example, there is a bound on the size of integer
that can be computed by an always-halting nondeterministic Turing
machine starting on a blank tape. (See article on unbounded
nondeterminism.) By contrast, there are always-halting concurrent
systems with no inputs that can compute an integer of unbounded size.
(A process can be created with local storage that is initialized with
a count of 0 that concurrently sends itself both a stop and a go
message. When it receives a go message, it increments its count by 1
and sends itself a go message. When it receives a stop message, it
stops with an unbounded number in its local storage.)
Interaction[edit]
In the early days of computing, computer use was typically limited to
batch processing, i.e., non-interactive tasks, each producing output
data from given input data.
That the whole of development and operations of analysis are now capable of being executed by machinery. — (italics in Babbage as cited by Gandy, p. 54) Gandy's analysis of Babbage's
The arithmetic functions +, −, ×, where − indicates "proper" subtraction x − y = 0 if y ≥ x. Any sequence of operations is an operation. Iteration of an operation (repeating n times an operation P). Conditional iteration (repeating n times an operation P conditional on the "success" of test T). Conditional transfer (i.e. conditional "goto"). Gandy states that "the functions which can be calculated by (1), (2),
and (4) are precisely those which are Turing computable."
(p. 53). He cites other proposals for "universal calculating
machines" including those of
… the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized… — Gandy p. 55 The
10. Determination of the solvability of a Diophantine equation. Given
a
By 1922, this notion of "Entscheidungsproblem" had developed a bit, and H. Behmann stated that ... most general form of the
A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion ... — Gandy p. 57, quoting Behmann Behmann remarks that ... the general problem is equivalent to the problem of deciding which mathematical propositions are true. — ibid. If one were able to solve the
By the 1928 international congress of mathematicians, Hilbert "made
his questions quite precise. First, was mathematics complete ...
Second, was mathematics consistent ... And thirdly, was mathematics
decidable?" (Hodges p. 91, Hawking p. 1121). The first two
questions were answered in 1930 by
But what Church had done was something rather different, and in a certain sense weaker. ... the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration. — Hodges p. 112 And Post had only proposed a definition of calculability and
criticized Church's "definition", but had proved nothing.
Alan Turing's a-machine[edit]
In the spring of 1935, Turing as a young Master's student at King's
College Cambridge, UK, took on the challenge; he had been stimulated
by the lectures of the logician
To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a computing machine. — Gandy, p. 74 Gandy states that: I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a diagonal argument to prove unsolvability. — ibid., p. 76 While Gandy believed that Newman's statement above is "misleading",
this opinion is not shared by all. Turing had a lifelong interest in
machines: "Alan had dreamt of inventing typewriters as a boy; [his
mother] Mrs. Turing had a typewriter; and he could well have begun by
asking himself what was meant by calling a typewriter 'mechanical'"
(Hodges p. 96). While at Princeton pursuing his PhD, Turing built
a Boolean-logic multiplier (see below). His PhD thesis, titled
"Systems of
It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent. — Turing (1939) in The Undecidable, p. 160 When Turing returned to the UK he ultimately became jointly
responsible for breaking the German secret codes created by encryption
machines called "The Enigma"; he also became involved in the design of
the ACE (Automatic Computing Engine), "[Turing's] ACE proposal was
effectively self-contained, and its roots lay not in the
[that] the Hilbert
Turing's example (his second proof): If one is to ask for a general
procedure to tell us: "Does this machine ever print 0", the question
is "undecidable".
1937–1970: The "digital computer", the birth of "computer
science"[edit]
In 1937, while at Princeton working on his PhD thesis, Turing built a
digital (Boolean-logic) multiplier from scratch, making his own
electromechanical relays (Hodges p. 138). "Alan's task was to
embody the logical design of a
Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory: the off-line multitape Turing machine..., which represents the standard model for string-oriented computation, and the random access machine (RAM) as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer. — van Emde Boas 1990:4 Only in the related area of analysis of algorithms this role is taken over by the RAM model. — van Emde Boas 1990:16 See also[edit] Algorithm, for a brief history of some of the inventions and the
mathematics leading to Turing's definition of what he called his
"a-machine"
Arithmetical hierarchy
Bekenstein bound, showing the impossibility of infinite-tape Turing
machines of finite size and bounded energy
BlooP and FlooP
Busy beaver
The Emperor's New Mind
Halting problem, for more references
Harvard architecture
Imperative programming
Notes[edit] ^ Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class
of abstract machines that now bear his name. A
δ displaystyle delta is undefined on all states from F displaystyle F References[edit] Primary literature, reprints, and compilations[edit] B.
Boolos, George; Richard Jeffrey (1999) [1989].
Church's thesis[edit] Nachum Dershowitz; Yuri Gurevich (September 2008). "A natural
axiomatization of computability and proof of Church's Thesis" (PDF).
Bulletin of Symbolic Logic. 14 (3). Retrieved 2008-10-15.
Small Turing machines[edit] Rogozhin, Yurii, 1998, "A Universal Turing Machine with 22 States and
2 Symbols", Romanian Journal of Information Science and Technology,
1(3), 259–265, 1998. (surveys known results about small universal
Turing machines)
Stephen Wolfram, 2002, A New Kind of Science, Wolfram Media,
ISBN 1-57955-008-8
Brunfiel, Geoff, Student snags maths prize, Nature, October 24. 2007.
Jim Giles (2007), Simplest 'universal computer' wins student $25,000,
New Scientist, October 24, 2007.
Alex Smith, Universality of Wolfram’s 2, 3 Turing Machine,
Submission for the Wolfram 2, 3 Turing Machine Research Prize.
Vaughan Pratt, 2007, "Simple Turing machines, Universality, Encodings,
etc.", FOM email list. October 29, 2007.
Martin Davis, 2007, "Smallest universal machine", and Definition of
universal
Other[edit]
External links[edit] Wikimedia Commons has media related to Turing machines. Hazewinkel, Michiel, ed. (2001) [1994], "Turing machine", Encyclopedia
of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic
Publishers, ISBN 978-1-55608-010-4
Turing Machine on Stanford Encyclopedia of Philosophy
Detailed info on the Church–Turing Hypothesis (Stanford Encyclopedia
of Philosophy)
Web Turing Machine Web application to construct and execute Turing
machines (Javascript)
Turing Machine-Like Models in Molecular Biology, to understand life
mechanisms with a DNA-tape processor.
The Turing machine—Summary about the Turing machine, its
functionality and historical facts
The Wolfram 2,3 Turing Machine Research Prize—Stephen Wolfram's
$25,000 prize for the proof or disproof of the universality of the
potentially smallest universal Turing Machine. The contest has ended,
with the proof affirming the machine's universality.
"Turing Machine Causal Networks" by Enrique Zeleny, Wolfram
Demonstrations Project.
Turing Machines at Curlie (based on DMOZ)
Purely mechanical Turing Machine
JSTMSimulator: an open source Turing Machine simulator, written in
JavaScript. (source code on GitHub)
How
v t e Automata theory: formal languages and formal grammars Chomsky hierarchy Grammars Languages Abstract machines Type-0 — Type-1 — — — — — Type-2 — — Type-3 — — Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive Recursively enumerable Decidable Context-sensitive Positive range concatenation* Indexed* — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite Turing machine
Decider
Linear-bounded
Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line. Authority control GND: 42035 |