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.
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".
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.
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".
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.
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 and also considered versions with tape-alphabets of size larger than 2.
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.
[4] Oblivious machines correspond in a step-wise linear fashion with combinational logic circuits, when the complexity of the transition table is taken as constant.
Minsky eliminated the PRINT instruction at the expense of providing his model with a mandatory single mark at the left-end of each tape.
Melzak recognised a couple serious defects in his register/counter-machine model:[5] (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.
His model had a "mill"—an accumulator, but now the instructions were in the registers with the data—the so-called von Neumann architecture.
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.
For example, the Schönhage pointer-machine model has two instructions called "input λ0,λ1" and "output β".
In some sense, if we never "write to" the input 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.