A Turing machine is a hypothetical computing device, first conceived by Alan Turing 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 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, Machine Models and Simulations; Jan van Leeuwen, 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 { mark, blank }, and/or (ii) sequential, computer-like instructions, and/or (iii) machine-actions fully atomised.
Post's "Formulation 1" model of computation
Emil Post in an independent description of a computational process, reduced the symbols allowed to the equivalent binary set of marks on the tape { "mark", "blank"=not_mark }. 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, 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
{ SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, ERASE-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx }
and his most-severely reduced 4-instruction Wang B-machine ("B" for "basic") with the instruction-set
{ SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx }
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 { SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT }.
Davis, adding an explicit HALT instruction to one of the machines discussed by Wang, used a model with the instruction-set
{ SHIFT-LEFT, SHIFT-RIGHT, ERASE, MARK, JUMP-IF-SQUARE-MARKED-to xxx, JUMP-to xxx, HALT }
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 in 1964 – the first "GOTO-less" imperative "structured programming" language to be proved Turing-complete.
Müller's machine language Brainfuck
Brainfuck (BF) is an — sc. not quite — esoteric programming language created in 1993 by Swiss student . It is a variant of Böhm's language P′′. In Böhm's language P′′, the instruction combines two actions: incrementing the contents of the current tape cell and moving the tape head by one position. In BF, this combined operation is split into two separate instructions: an instruction that increments the value stored in the current cell; and an instruction that moves the tape head by one cell.
The two languages are computationally equivalent; that is, it is possible to transform any P′′ program into a BF program (and vice versa), provided the semantics are appropriately synchronized.
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.
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.
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). This improves upon the original result by Cook and Levin.
Register machine models
Peter van Emde Boas 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 { mark, blank }.
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): { INC ( r ), DEC ( r ), JZ ( r,z ) }, i.e. { INCrement contents of register #r; DECrement contents of register #r; IF contents of #r=Zero THEN Jump-to Instruction #z} (2): { CLR ( r ); INC ( r ); JE ( ri, rj, z ) }, i.e. { CLeaR contents of register r; INCrement contents of r; compare contents of ri to rj and if Equal then Jump to instruction z}
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 of the instructions Minsky offered a proof that with such numbering the general recursive functions were indeed possible; he offers proof that μ recursion is indeed possibleMarvin Minsky, 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