In contrast to the tape and head used by a Turing machine, the model uses multiple uniquely addressed registers, each of which holds a single non-negative integer.
In ascending order of complexity: Any properly defined register machine model is Turing complete.
[1] A register machine consists of: See McCarthy Formalism for more about the conditional expression "IF r=0 THEN ztrue ELSE zfalse"[5] Two trends appeared in the early 1950s.
"[2]: 281 [7]: 218 The first step towards characterizing computers originated[nb 3] with Hans Hermes (1954),[8] Rózsa Péter (1958),[9] and Heinz Kaphengst (1959),[10] the second step with Hao Wang (1954,[11] 1957[12]) and, as noted above, furthered along by Zdzislaw Alexander Melzak (1961),[2] Joachim Lambek (1961)[4] and Marvin Minsky (1961,[3] 1967[13]).
He follows up with: Lambek, Melzak, Minsky, Shepherdson and Sturgis independently discovered the same idea at the same time.
[7] Indeed, Shepherdson and Sturgis (1963) remark that: Martin Davis eventually evolved this model into the (2-symbol) Post–Turing machine.
Initial thought leads to 'cutting the tape' so that each is infinitely long (to accommodate any size integer) but left-ended.
Or in Minsky (1961)[3] and Hopcroft and Ullman (1979),[16]: 171ff the tape is always blank except for a mark at the left end—at no time does a head ever print or erase.
He took his own model, flipped the tapes vertically, called them "holes in the ground" to be filled with "pebble counters".
Legacy of Melzak's model is Lambek's simplification and the reappearance of his mnemonic conventions in Cook and Reckhow 1973.
Intrinsically the model is bounded by the size of its (very-) finite state machine's instructions.
Melzak (1961)[2] specifically mentions the "computed goto" by name but instead provides his model with indirect addressing.
If the pointer-register is unbounded, the RAM, and a suitable RASP built on its chassis, will be Turing equivalent.
Note that the finite state machine does not have to explicitly specify this target register's address.
Cook and Reckhow (1973)[18] cite Hartmanis (1971)[20] and simplify his model to what they call a random-access machine (RAM—i.e.
Melzak (1961)[2] provides his pebble-in-holes counter machine model with indirection but doesn't carry the treatment further.
The work of Elgot–Robinson (1964)[17] define the RASP—the computer-like random-access stored-program machines—and appear to be the first to investigate the failure of the bounded counter machine to calculate the mu-recursive functions.
This failure—except with the draconian use of Gödel numbers in the manner of Minsky (1961)[3]—leads to their definition of "indexed" instructions (i.e. indirect addressing) for their RASP model.
Hartmanis (1971)[20] specifies an instruction set with indirection, citing lecture notes of Cook (1970).
[34] For use in investigations of computational complexity Cook and his graduate student Reckhow (1973)[18] provide the definition of a RAM (their model and mnemonic convention are similar to Melzak's, but offer him no reference in the paper).
The terminology of at least one paper (Kaphengst (1959)[10] seems to hark back to the Burke–Goldstine–von Neumann (1946–1947)[19] analysis of computer architecture.