A
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 algori ...
is a hypothetical computing device, first conceived by
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm.
While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's ''a''-machine model.
Machines equivalent to the Turing machine model
Turing equivalence
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power. They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (The
Church–Turing thesis
In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of comp ...
''hypothesizes'' this to be true: that anything that can be "computed" can be computed by some Turing machine.)
The sequential-machine models
All of the following are called "sequential machine models" to distinguish them from "parallel machine models".
Peter van Emde Boas
Peter van Emde Boas (born 3 April 1945, Amsterdam) is a Dutch computer scientist and professor at the University of Amsterdam
The University of Amsterdam (abbreviated as UvA, nl, Universiteit van Amsterdam) is a public research university l ...
, ''Machine Models and Simulations''; Jan van Leeuwen
Jan van Leeuwen (born December 17, 1946, in Waddinxveen) is a Dutch computer scientist and Emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University. , ed. ''Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', p. 3-66, The MIT Press/Elsevier, 1990. (volume A). QA76.H279 1990.
Tape-based Turing machines
Turing's ''a''-machine model
Turing's a-machine (as he called it) was left-ended, right-end-infinite. He provided symbols əə to mark the left end. A finite number of tape symbols were permitted. The instructions (if a universal machine), and the "input" and "out" were written only on "F-squares", and markers were to appear on "E-squares". In essence he divided his machine into two tapes that always moved together. The instructions appeared in a tabular form called "5-tuples" and were not executed sequentially.
Single-tape machines with restricted symbols and/or restricted instructions
The following models are single tape Turing machines but restricted with (i) restricted tape symbols , and/or (ii) sequential, computer-like instructions, and/or (iii) machine-actions fully atomised.
Post's "Formulation 1" model of computation
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 ...
in an independent description of a computational process, reduced the symbols allowed to the equivalent binary set of marks on the tape . He changed the notion of "tape" from 1-way infinite to the right to an infinite set of rooms each with a sheet of paper in both directions. He atomised the Turing 5-tuples into 4-tuples—motion instructions separate from print/erase instructions. Although his 1936 model is ambiguous about this, Post's 1947 model did not require sequential instruction execution.
His extremely simple model can emulate any Turing machine, and although his 1936 ''Formulation 1'' does not use the word "program" or "machine", it is effectively a formulation of a very primitive programmable computer and associated
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
, with the boxes acting as an unbounded bitstring memory, and the set of instructions constituting a program.
Wang machines
In an influential paper,
Hao Wang reduced Post's "
formulation 1" to machines that still use a two-way infinite binary tape, but whose instructions are simpler – being the "atomic" components of Post's instructions – and are by default executed sequentially (like a "computer program"). His stated principal purpose was to offer, as an alternative to Turing's theory, one that "is more economical in the basic operations". His results were "program formulations" of a variety of such machines, including the 5-instruction Wang W-machine with the instruction-set
:
and his most-severely reduced 4-instruction
Wang B-machine
As presented by Hao Wang (1954, 1957), his basic machine B is an extremely simple computational model equivalent to the Turing machine. It is "the first formulation of a Turing-machine theory in terms of computer-like models" (Minsky, 1967: 200). ...
("B" for "basic") with the instruction-set
:
which has not even an ERASE-SQUARE instruction.
Many authors later introduced variants of the machines discussed by Wang:
Minsky evolved Wang's notion with his version of the (multi-tape) "counter machine" model that allowed SHIFT-LEFT and SHIFT-RIGHT motion of the separate heads but no printing at all.
In this case the tapes would be left-ended, each end marked with a single "mark" to indicate the end. He was able to reduce this to a single tape, but at the expense of introducing multi-tape-square motion equivalent to multiplication and division rather than the much simpler .
Davis, adding an explicit HALT instruction to one of the machines discussed by Wang, used a model with the instruction-set
:
and also considered versions with tape-alphabets of size larger than 2.
Böhm's theoretical machine language P"
In keeping with Wang's project to seek a Turing-equivalent theory "economical in the basic operations", and wishing to avoid unconditional jumps, a notable theoretical language is the 4-instruction language
P" introduced by
Corrado Böhm
Corrado Böhm (17 January 1923 – 23 October 2017) was a Professor Emeritus at the University of Rome "La Sapienza" and a computer scientist known especially for his contributions to the theory of structured programming, constructive mathem ...
in 1964 – the first "GOTO-less" imperative "
structured programming
Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection ( if/then/else) and repetition ( ...
" language to be proved
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
.
Multi-tape Turing machines
In practical analysis, various types of multi-tape Turing machines are often used. Multi-tape machines are similar to single-tape machines, but there is some constant ''k'' number of independent tapes.
Deterministic and non-deterministic Turing machines
If the action table has at most one entry for each combination of symbol and state then the machine is a "deterministic Turing machine" (DTM). If the action table contains multiple entries for a combination of symbol and state then the machine is a "non-deterministic Turing machine" (NDTM). The two are computationally equivalent, that is, it is possible to turn any NDTM into a DTM (and ''vice versa''), although they usually have different runtimes. This can be proved via construction.
Oblivious Turing machines
An oblivious Turing machine is a Turing machine where, for each input length, movement of the various heads is a fixed function of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to. The actual values that are written to the tape at any step can still be different for each input of that length. Pippenger and Fischer showed that any computation that can be performed by a multi-tape Turing machine in ''n'' steps can be performed by an oblivious two-tape Turing machine in steps.
Oblivious machines correspond in a step-wise linear fashion with combinational logic circuits, when the complexity of the transition table is taken as constant. It is thus possible to realize computations as circuit problems in size and depth (see
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
). This improves upon the original result by
Cook and Levin.
Register machine models
Peter van Emde Boas
Peter van Emde Boas (born 3 April 1945, Amsterdam) is a Dutch computer scientist and professor at the University of Amsterdam
The University of Amsterdam (abbreviated as UvA, nl, Universiteit van Amsterdam) is a public research university l ...
includes all machines of this type in one class, "the register machine".
However, historically the literature has also called the most primitive member of this group i.e. "the counter machine" – "the register machine". And the most primitive embodiment of a "counter machine" is sometimes called the "Minsky machine".
The "counter machine", also called a "register machine" model
The primitive model register machine is, in effect, a multitape 2-symbol Post–Turing machine with its behaviour restricted so its tapes act like simple "counters".
By the time of Melzak, Lambek, and Minsky the notion of a "computer program" produced a different type of simple machine with many left-ended tapes cut from a Post–Turing tape. In all cases the models permit only two tape symbols .
Some versions represent the positive integers as only a strings/stack of marks allowed in a "register" (i.e. left-ended tape), and a blank tape represented by the count "0". Minsky eliminated the PRINT instruction at the expense of providing his model with a mandatory single mark at the left-end of each tape.
In this model the single-ended tapes-as-registers are thought of as "counters", their instructions restricted to only two (or three if the TEST/DECREMENT instruction is atomised). Two common instruction sets are the following:
:(1): , i.e.
::
:(2): , i.e.
::
Although his model is more complicated than this simple description, the Melzak "pebble" model extended this notion of "counter" to permit multi-
pebble adds and subtracts.
The random-access machine (RAM) model
Melzak recognised a couple serious defects in his register/counter-machine model: (i) Without a form of indirect addressing he would not be able to "easily" show the model is
Turing equivalent, (ii) The program and registers were in different "spaces", so self-modifying programs would not be easy. When Melzak added indirect addressing to his model he created a random access machine model.
(However, with
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...
of the instructions Minsky offered a proof that with such numbering the general
recursive functions were indeed possible; he offers proof that
μ recursion
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
is indeed possible
Marvin Minsky
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, ...
, ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem.").
Unlike the RASP model, the RAM model does not allow the machine's actions to modify its instructions. Sometimes the model works only register-to-register with no accumulator, but most models seem to include an accumulator.
van Emde Boas divides the various RAM models into a number of sub-types:
* SRAM, the "successor RAM" with only one arithmetic instruction, the successor (INCREMENT h). The others include "CLEAR h", and an IF equality-between-register THEN jump-to xxx.
* RAM: the standard model with addition and subtraction
* MRAM: the RAM augmented with multiplication and division
* BRAM, MBRAM: Bitwise Boolean versions of the RAM and MRAM
* N****: Non-deterministic versions of any of the above with an N before the name
The random-access stored program (RASP) machine model
The RASP is a RAM with the instructions stored together with their data in the same 'space' – i.e. sequence of registers. The notion of a RASP was described at least as early as Kiphengst. His model had a "mill"—an accumulator, but now the instructions were in the registers with the data—the so-called
von Neumann architecture
The von Neumann architecture — also known as the von Neumann model or Princeton architecture — is a computer architecture based on a 1945 description by John von Neumann, and by others, in the '' First Draft of a Report on the EDVAC''. T ...
. When the RASP has alternating even and odd registers—the even holding the "operation code" (instruction) and the odd holding its "operand" (parameter), then indirect addressing is achieved by simply modifying an instruction's operand.
The original RASP model of Elgot and Robinson had only three instructions in the fashion of the register-machine model, but they placed them in the register space together with their data. (Here COPY takes the place of CLEAR when one register e.g. "z" or "0" starts with and always contains 0. This trick is not unusual. The unit 1 in register "unit" or "1" is also useful.)
:
The RASP models allow indirect as well as direct-addressing; some allow "immediate" instructions too, e.g. "Load accumulator with the constant 3". The instructions may be of a highly restricted set such as the following 16 instructions of Hartmanis. This model uses an accumulator A. The mnemonics are those that the authors used (their CLA is "load accumulator" with constant or from register; STO is "store accumulator"). Their syntax is the following, excepting the jumps: "n,
, <>" for "immediate", "direct" and "indirect"). Jumps are via two "Transfer instructions" TRA—unconditional jump by directly "n" or indirectly "< n >" jamming contents of register n into the instruction counter, TRZ (conditional jump if Accumulator is zero in the same manner as TRA):
:
The Pointer machine model
A relative latecomer is Schönhage's Storage Modification Machine or pointer machine
In theoretical computer science a pointer machine is an "atomistic" ''abstract computational machine'' model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model.
Depending on the type, a ...
. Another version is the Kolmogorov-Uspensky machine, and the Knuth "linking automaton" proposal. (For references see pointer machine
In theoretical computer science a pointer machine is an "atomistic" ''abstract computational machine'' model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model.
Depending on the type, a ...
). Like a state-machine diagram, a node emits at least two labelled "edges" (arrows) that point to another node or nodes which in turn point to other nodes, etc. The outside world points at the center node.
Machines with input and output
Any of the above tape-based machines can be equipped with input and output tapes; any of the above register-based machines can be equipped with dedicated input and output registers. For example, the Schönhage pointer-machine model has two instructions called "''input'' ''λ''0,''λ''1" and "''output'' ''β''".
It is difficult to study sublinear In linear algebra, a sublinear function (or functional as is more often used in functional analysis), also called a quasi-seminorm or a Banach functional, on a vector space X is a real-valued function with only some of the properties of a seminorm. ...
space complexity
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...
on multi-tape machines with the traditional model, because an input of size ''n'' already takes up space ''n''. Thus, to study small DSPACE
DSpace is an open source repository software package typically used for creating open access repositories for scholarly and/or published digital content. While DSpace shares some feature overlap with content management systems and document manag ...
classes, we must use a different model. In some sense, if we never "write to" the input tape, we don't want to charge ourself for this space. And if we never "read from" our output tape, we don't want to charge ourself for this space.
We solve this problem by introducing a ''k''-string Turing machine with input and output. This is the same as an ordinary ''k''-string Turing machine, except that the transition function is restricted so that the input tape can never be changed, and so that the output head can never move left. This model allows us to define deterministic space classes smaller than linear. Turing machines with input-and-output also have the same time complexity as other Turing machines; in the words of Papadimitriou 1994 Prop 2.2:
:For any ''k''-string Turing machine ''M'' operating within time bound there is a -string Turing machine ''M with input and output, which operates within time bound .
''k''-string Turing machines with input and output can be used in the formal definition of the complexity resource DSPACE
DSpace is an open source repository software package typically used for creating open access repositories for scholarly and/or published digital content. While DSpace shares some feature overlap with content management systems and document manag ...
.
Other equivalent machines and methods
* Multidimensional Turing machine: For example, a model by Schönhage uses the four head-movement commands .[A. Schōnhage (1980), ''Storage Modification Machines'', Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980.]
* Single-tape, multi-head Turing machine: In an undecidability proof of the "problem of tag", Minsky and Shepherdson and Sturgis described machines with a single tape that could read along the tape with one head and write further along the tape with another.[ John C. Shepherdson and H. E. Sturgis received December 1961 ''Computability of Recursive Functions'', ]Journal of the ACM
The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...
10:217-255, 1963
* Markov algorithm
In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a gener ...
is another remarkably simple computational model, based on string rewriting, equivalent to the Turing machines.
* Lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
* Queue automaton
A queue machine, queue automaton, or pullup automaton (PUA) is a finite state machine with the ability to store and retrieve data from an infinite-memory queue. It is a model of computation equivalent to a Turing machine, and therefore it can proc ...
References
{{DEFAULTSORT:Turing Machine Equivalents
Turing machine
Theory of computation
Models of computation