Counter-machine model

There are many variants of the counter machine, among them those of Hermes, Ershov, Péter, Minsky, Lambek, Shepherdson and Sturgis, and Schönhage. These are explained below.

== The models in more detail ==

=== 1954: Hermes' model === {{harvtxt|Shepherdson|Sturgis|1963}} observe that ''"the proof of this universality [of digital computers to Turing machines] ... seems to have been first written down by Hermes, who showed in [7--their reference number] how an idealized computer could be programmed to duplicate the behavior of any Turing machine"'', and: ''"Kaphengst's approach is interesting in that it gives a direct proof of the universality of present-day digital computers, at least when idealized to the extent of admitting an infinity of storage registers each capable of storing arbitrarily long words"''.{{sfn|Shepherdson|Sturgis|1963|p=219}}

The only two ''arithmetic'' instructions are # Successor operation # Testing two numbers for equality

The rest of the operations are transfers from register-to-accumulator or accumulator-to-register or test-jumps.

Kaphengst's paper is written in German; Sheperdson and Sturgis' translation uses terms such as "mill" and "orders".

The machine contains "a mill" (accumulator). Kaphengst designates his mill/accumulator with the "infinity" symbol but we will use "A" in the following description. It also contains an "order register" ("order" as in "instruction", not as in "sequence"). (This usage came from the Burks–Goldstine–von Neumann (1946) report's description of "...an Electronic Computing Instrument".) The order/instruction register is register "0". And, although not clear from Sheperdson and Sturgis' exposition, the model contains an "extension register" designated by Kaphengst "infinity-prime"; we will use "E".

The instructions are stored in the registers: :"...so the machine, like an actual computer, is capable of doing arithmetic operations on its own program" (p. 244).

Thus this model is actually a random-access machine. In the following, "[ r ]" indicates "contents of" register r, etc.

{|class="wikitable" |- style="font-size:9pt" ! width="21.6" Height="9.6" align="center" valign="bottom" | ! width="41.4" valign="bottom" | ! width="216" align="center" valign="bottom" | Action: ! width="306.6" align="center" valign="bottom" | Description

|- style="font-size:9pt" | Height="9.6" valign="bottom" | F1: | valign="bottom" | {{nowrap|J(A) [E1]}} | valign="bottom" | IF [ A ] = 0 THEN jump to "Exit 1" | valign="bottom" | Jump if contents of accumulator A = 0

{{harvtxt|Shepherdson|Sturgis|1963}} remove the mill/accumulator A and reduce the Kaphengst instructions to register-to-register "copy", arithmetic operation "increment", and "register-to-register compare". ''Observe that there is no decrement''. This model, almost verbatim, is to be found in {{harvtxt|Minsky|1967}}; see more in the section below.

{|class="wikitable" |- style="font-size:9pt" ! width="21.6" Height="9.6" align="center" valign="bottom" | ! width="64.8" valign="bottom" | ! width="252.6" align="center" valign="bottom" | Action: ! width="306.6" align="center" valign="bottom" | Description:

=== 1958: Ershov's class of operator algorithms === {{harvtxt|Shepherdson|Sturgis|1963}} observe that Ersov's model allows for storage of the program in the registers. They assert that Ersov's model is as follows:

|- style="font-size:9pt" | Height="9.6" valign="bottom" | f*: | valign="bottom" | {{nowrap|J(rj, rk)[E1, E2]}} | valign="bottom" | IF [ rj ] ≤ [ rk ] THEN jump to "Exit 1" ELSE jump to "Exit 2" | valign="bottom" | Jump to exit E1 if contents of register rj is less than or equal to contents of rk, else jump to E=2

=== 1958: Péter's "treatment" === {{harvtxt|Shepherdson|Sturgis|1963}} observe that Péter's "treatment" (they are not too specific here) has an equivalence to the instructions shown in the following table. They comment specifically about these instructions, that: :"from the point of view of proving as quickly as possible the computability of all partial recursive functions Péter's is perhaps the best; for proving their computability by Turing machines a further analysis of the copying operation is necessary along the lines we have taken above."{{sfn|Shepherdson|Sturgis|1963|p=246}}

|- style="font-size:9pt" | Height="9.6" valign="bottom" | e. | valign="bottom" | J(m, n)[E1, E2] | valign="bottom" | IF [m]=[n] jump to E1 ELSE jump to E2 | valign="bottom" | Conditional jump to E1 if contents of m equals contents of n, else jump to E2. |}

=== 1961: Minsky's model of a partial recursive function reduced to a "program" of only two instructions === In his inquiry into problems of Emil Post (the tag system) and Hilbert's 10th problem (Hilbert's problems, Diophantine equation) led Minsky to the following definition of: :"an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations".{{sfn|Minsky|1961|p=437}}

His "Theorem Ia" asserts that any partial recursive function is represented by "a program operating on ''two'' integers S1 and S2 using instructions Ij of the forms:{{refn|cf. {{harvnb|Minsky|1961|p=449}}}}

{|class="wikitable" |- style="font-size:9pt" ! width="25" Height="9.6" align="center" valign="bottom" | ! width="69" valign="bottom" | ! width="277.8" align="center" valign="bottom" | Action: ! width="385.2" align="center" valign="bottom" | Description:

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b. | {{nowrap|SUB (r, Ij1,Ij2)}} | If [ r ] ≤ 0 THEN go to instr. Ij2 ELSE [ r ] -1 → r and go to instr. Ij1 | IF contents of register r equals zero THEN jump to instruction Ij2; ELSE decrement (subtract 1 from) contents of register r and jump to instr. Ij1.

The first theorem is the context of a second "Theorem IIa" that : "...represents any partial recursive function by a program operating on one integer S [contained in a single register r1] using instructions Ij of the forms": {|class="wikitable" |- style="font-size:9pt" ! width="25" Height="9.6" align="center" valign="bottom" | ! width="69" valign="bottom" | ! width="277.8" align="center" valign="bottom" | Action: ! width="385.2" align="center" valign="bottom" | Description:

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b. | {{nowrap|DIV (Kj, Ij1, Ij2)}} | [ r1 ]/Kj = 0 then go to instruction Ij2 else go to Ij1. | If division of contents of register 1 by constant Kj has no remainder then instr. Ij1 else instr. Ij2

In this second form the machine uses Gödel numbers to process "the integer S". He asserts that the first machine/model does not need to do this if it has 4 registers available to it.

=== 1961: Melzak model: a single ternary instruction with addition and proper subtraction === :"It is our object to describe a primitive device, to be called a Q-machine, which arrives at effective computability via arithmetic rather than via logic. Its three operations are keeping tally, comparing non-negative integers, and transferring" (Melzak (1961) p. 281)

If we use the context of his model, "keeping tally" means "adding by successive increments" (throwing a pebbles into) or "subtracting by successive decrements"; transferring means moving (not copying) the contents from hole A to hole B, and comparing numbers is self-evident. This appears to be a blend of the three base models.

Melzak's physical model is holes { X, Y, Z, etc. } in the ground together with an unlimited supply of pebbles in a special hole '''S''' (Sink or Supply or both? Melzak doesn't say).

:"The Q-machine consists of an '''indefinitely large number of locations''': S, A1, A2, ..., an indefinitely large supply of counters distributed among these locations, a program, and an operator whose sole purpose is to carry out the instructions. Initially all but a finite number from among the locations ... are empty and each of the remaining ones contains a '''finite number of counters'''" (p. 283, boldface added)

The instruction is a ''single'' "ternary operation" he calls "XYZ": :"XYZ" denotes the operation of {{Ordered list |list_style_type=lower-roman |Count the number of pebbles in hole '''Y''', | put them back into '''Y''', | attempt to remove this same number from hole '''X'''. IF this is not possible because it will empty hole '''X''' THEN do nothing and jump to instruction #I; ELSE, | remove the Y-quantity from '''X''' and (iv) transfer them to, i.e. ''add'' them to, the quantity in hole '''Z'''. }} Of all the possible operations, some are not allowed, as shown in the table below:

{|class="wikitable" style="text-align: center; vertical-align: bottom" |- ! Allowed ! Instruction ! Hole "X" ! Hole "Y" ! Hole "Z" ! Meaning of Instruction |- | NO | XXX | | | | |- style="vertical-align: bottom" | | XXY | ([ X ] - [ X ])=0 → X | [ Y ] + [ X ] → Y | [ Z ] → Z | style="text-align: left" | All of X's pebbles taken from X and added to Y |- style="vertical-align: bottom" | | XXS | ([ X ] - [ X ])=0 → X | [ Y ] → Y | [ Z ] → Z | style="text-align: left" | All of X's pebbles taken from X and put into sink/source S |- | NO | XYX | | | | |- style="vertical-align: bottom" | | XYY | [ X ] - [ Y ] → X | [ Y ] + [ Y ] → Y | [ Z ] → Z | style="text-align: left" | Count of Y's pebbles taken from X and placed in Y, doubling count of Y |- | | XYS | | | | |- | NO | XSX | | | | |- | NO | XSY | | | | |- | NO | XSS | | | | |- style="vertical-align: bottom" | | XYZ | [ X ] - [ Y ] → X | [ Y ] → Y | [ Z ] + [ Y ] → Z | style="text-align: left" | Count of Y's pebbles taken from X and added to Z, |- style="vertical-align: bottom" | | SYY | [ X ] → X | [ Y ] + [ Y ] → Y | [ Z ] → Z | style="text-align: left" | Count of Y's pebbles taken from S and added to Y, doubling Y's count |- style="vertical-align: bottom" | | SYZ | [ X ] → X | [ Y ] → Y | [ Z ] + [ Y ] → [ Z ] | style="text-align: left" | Count of Y's pebbles taken from S and added to Z |}

'''Some observations about the Melzak model''': {{Ordered list |list_style_type=lower-alpha | If all the holes start with 0, then how do we increment? Apparently this is not possible; one hole must contain a single pebble. | The conditional "jump" occurs on every instance of XYZ type because: if it cannot be performed because X does not have enough counters/pebbles then the jump occurs; otherwise if it can be performed it will be and the instructions continue to the next in sequence. | Neither SXY nor XXY can cause a jump because both can always be performed. | Melzak adds indirection to his model (see random-access machine) and gives two examples of its use. But he does not pursue this further. This is the first verified instance of "indirection" to appear in the literature. | Both papers{{spaced ndash}}that of Z. Alexander Melzak (William Lowell Putnam Mathematical Competition, winner 1950) was received 15 May 1961 and Joachim Lambek received a month later on 15 June 1961{{spaced ndash}}are contained in the same volume, one after the other. | Is Melzak's assertion true?{{spaced ndash}}that this model is "so simple that its working could probably be understood by an average school-child after a few minutes's explanation" (p. 282)? The reader will have to decide. }}

=== 1961: Lambek "abacus" model: atomizing Melzak's model to X+, X- with test === '''Original "abacus" model of Lambek (1962):'''

Lambek references Melzak's paper. He atomizes Melzak's single 3-parameter operation (really 4 if we count the instruction addresses) into a 2-parameter increment "X+" and 3-parameter decrement "X-". He also provides both an informal and ''formal'' definition of "a program". This form is virtually identical to the Minsky (1961) model, and has been adopted by {{harvnb|Boolos|Burgess|Jeffrey|2007|p=45|loc=Abacus Computability}}.

{|class="wikitable" |- style="font-size:9pt" ! width="16.8" Height="9.6" align="center" valign="bottom" | ! width="69" valign="bottom" | ! width="277.8" align="center" valign="bottom" | Action: ! width="385.2" align="center" valign="bottom" | Description:

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b. | X- (r, Ia, Ib) | If [ r ] ≤ 0, go to instr.Ib else [ r ]-1 → r and go to instr. Ia | First test for zero, then decrement (subtract 1 from) contents of register r |}

'''Abacus model of Boolos, Burgess & Jeffrey''':{{sfn|Boolos|Burgess|Jeffrey|2007|p=45|loc=Abacus Computability}}

The various editions beginning with 1970 the authors use the Lambek (1961) model of an "infinite abacus". This series of Wikipedia articles is using their symbolism, e.g. " [ r ] +1 → r" "the contents of register identified as number 'r', plus 1, replaces the contents of [is put into] register number 'r' ".

They use Lambek's name "abacus" but follow Melzak's pebble-in-holes model, modified by them to a 'stones-in-boxes' model. Like the original abacus model of Lambek, their model retains the Minsky (1961) use of non-sequential instructions{{spaced ndash}}unlike the "conventional" computer-like default sequential instruction execution, the next instruction Ia is contained within the instruction.

Observe, however, that B-B and B-B-J do not use a variable "X" in the mnemonics with a specifying parameter (as shown in the Lambek version) --i.e. "X+" and "X-"{{spaced ndash}}but rather the instruction mnemonics specifies the registers themselves, e.g. "2+", or "3-":

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b1. | 1- (Ia, Ib) | If [ r1 ] ≤ 0 THEN go to Ib else [ r1 ] -1 → r1 and go to Ia. | Jump to instruction Ib if contents of register r1 is zero ELSE decrement (subtract 1 from) contents of register #1 |}

=== 1963: Shepherdson and Sturgis' model === {{harvtxt|Shepherdson|Sturgis|1963}} reference Minsky (1961) as it appeared for them in the form of an MIT Lincoln Laboratory report: {{Blockquote|1=In Section 10 we show that theorems (including Minsky's results [21, their reference]) on the computation of partial recursive functions by one or two tapes can be obtained rather easily from one of our intermediate forms.|2={{harvnb|Shepherdson|Sturgis|1963|p=218}}}} Their model is strongly influenced by the model and the spirit of Hao Wang (1957){{sfn|Wang|1957}} and his Wang B-machine (also see Post–Turing machine). They "sum up by saying": {{Blockquote|1=...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested and started by Wang.}}

'''Unlimited Register Machine URM''':{{refn|See also {{harvnb|Cutland|1980|p=9}}}} This, their "most flexible machine... consists of a denumerable sequence of registers numbered 1, 2, 3, ..., each of which can store any natural number...Each particular program, however involves only a finite number of these registers" (p. 219). In other words, the number of registers is potentially infinite, and each register's "size" is infinite.

They offer the following instruction set and the following "Notes":{{sfn|Shepherdson|Sturgis|1963|p=219}} {|class="wikitable" |- style="font-size:9pt" ! width="21.6" Height="12" align="center" valign="bottom" | ! width="64.8" valign="bottom" | URM model: ! width="252.6" align="center" valign="bottom" | Action: ! width="306.6" align="center" valign="bottom" | Description:

|- style="font-size:9pt" valign="bottom" | Height="9.6" | a. | P(n) | [ r ] + 1 → r | Increment (add 1 to) contents of register r

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b. | D(n) | [ r ] - 1 → r

| Decrement (subtract 1 from) contents of register r

|- style="font-size:9pt" | Height="9.6" valign="bottom" | f: | valign="bottom" | J(r) [E1] | valign="bottom" | IF [ rj ] = 0 THEN jump to "Exit 1"{{refn|name="cutland_p11"|Understand: "jump to "instruction number E1" {{sfn|Cutland|1980|p=11}}}} ELSE next instruction | valign="bottom" | IF contents of register r = 0 then jump to instruction "Exit 1"<ref name="cutland_p11"/> else next instruction |}

Notes. # This set of instructions is chosen for ease of programming the computation of partial recursive functions rather than economy; it is shown in Section 4 that this set is equivalent to a smaller set. # There are infinitely many instructions in this list since m, n [ contents of rj, etc.] range over all positive integers. # In instructions a, b, c, d the contents of all registers except n are supposed to be left unchanged; in instructions e, f, the contents of all registers are unchanged (p. 219).

Indeed, they show how to reduce this set further, to the following (for an infinite number of registers each of infinite size):

{|class="wikitable" |- style="font-size:9pt" ! width="21.6" Height="9.6" align="center" valign="bottom" | ! width="64.8" valign="bottom" | Reduced URM: ! width="252.6" align="center" valign="bottom" | Action: ! width="306.6" align="center" valign="bottom" | Description:

|- style="font-size:9pt" valign="bottom" | Height="9.6" | a1. | P(r) | [ r ] + 1 → r | Increment (add 1 to) contents of register r

|- style="font-size:9pt" valign="bottom" | Height="9.6" | b1. | D(n) | [ r ] - 1 → r | Decrement (subtract 1 from) contents of register r

'''Limited Register Machine LRM''': Here they restrict the machine to a finite number of registers N, but they also allow more registers to "be brought in" or removed if empty (cf. p. 228). They show that the remove-register instruction need not require an empty register.

'''Single-Register Machine SRM''': Here they are implementing the tag system of Emil Post and thereby allow only writing to the end of the string and erasing from the beginning. This is shown in their Figure 1 as a tape with a read head on the left and a write head on the right, and it can only move the tape right. "A" is their "word" (p. 229): :a. P(i) ;add ai to the end of A :b. D ;delete the first letter of A :f'. Ji[E1] ;If A begins with ai jump to exit 1.

They also provide a model as "a stack of cards" with the symbols { 0, 1 } (p. 232 and Appendix C p. 248): # add card at top printed 1 # add card at top printed 0 # remove bottom card; if printed 1 jump to instruction m, else next instruction.

=== 1967: Minsky's "Simple Universal Base for a Program Computer" === Ultimately, in Problem 11.7-1 Minsky observes that many bases of computation can be formed from a tiny collection: :"Many other combinations of operation types [ 0 ], [ ' ], [ - ], [ O- ], [ → ] and [ RPT ] form universal basis. Find some of these basis. Which combinations of three operations are not universal basis? Invent some other operations..."{{sfn|Minsky|1967|p=214}}

The following are definitions of the various instructions he treats: {|class="wikitable" |- style="font-size:9pt" ! width="16.8" Height="9.6" align="center" valign="bottom" | ! width="39" valign="bottom" | ! width="277.8" align="center" valign="bottom" | Action: ! width="385.2" align="center" valign="bottom" | Description:

Minsky (1967) begins with a model that consists of the three operations plus HALT: :{ [ 0 ], [ ' ], [ - ], [ H ] }

He observes that we can dispense with [ 0 ] if we allow for a specific register e.g. '''w''' already "empty".{{sfn|Minsky|1967|p=206}} Further on he compresses the three { [ 0 ], [ ' ], [ - ] }, into two { [ ' ], [ - ] }.{{sfn|Minsky|1967|p=255ff}}

But he admits the model is easier if he adds some [pseudo]-instructions [ O- ] (combined [ 0 ] and [ - ]) and "go(n)". He builds "go(n)" out of the register '''w''' pre-set to 0, so that [O-] ('''w''', (n)) is an unconditional jump.

In his section 11.5 "The equivalence of Program Machines with General-recursive functions" he introduces two new subroutines: :f. [ → ]

:j. [ ≠ ] ::Jump unless equal": IF [ rj ] ≠ [ rk ] THEN jump to zth instruction ELSE next instruction

He proceeds to show how to replace the "successor-predecessor" set { [ 0 ], [ ' ], [ - ] } with the "successor-equality" set { [ 0 ], [ ' ], [ ≠ ] }. And then he defines his "REPEAT" [RPT] and shows that we can define any primitive recursive function by the "successor-repeat" set { [ 0 ], [ ' ], [RPT] } (where the range of the [ RPT ] cannot include itself. If it does, we get what is called the mu operator (see also mu recursive functions) (p. 213)):

:Any general recursive function can be computed by a program computer using only operations [ 0 ], [ ' ], [ RPT ] if we permit a RPT operation to lie in its own range ... [however] in general a RPT operation could not be an instruction in the finite-state part of the machine...[if it were] this might exhaust any particular amount of storage allowed in the finite part of the machine. RPT operations require infinite registers of their own, in general... etc." (p. 214)

=== 1980: Schönhage's 0-parameter model RAM0 === Schönhage (1980){{sfn|Schönhage|1980}} developed his computational model in context of a "new" model he called the Storage Machine Modification model (SMM), his variety of pointer machine. His development described a RAM (random-access machine) model with a remarkable instruction set requiring no operands at all, excepting, perhaps, the "conditional jump" (and even that could be achieved without an operand):

:"...the RAM0 version deserves special attention for its extreme simplicity; its instruction set consists of only a few one-letter codes, without any (explicit) addressing" (p. 494)

The way Schönhage did this is of interest. He (i) atomizes the conventional register "address:datum" into its two parts: "address", and "datum", and (ii) generates the "address" in a specific register '''n''' to which the finite-state machine instructions (i.e. the "machine code") would have access, and (iii) provides an "accumulator" register '''z''' where all arithmetic operations are to occur.

His particular RAM0 model has only two "arithmetic operations"{{spaced ndash}}"Z" for "set contents of register '''z''' to zero", and "A" for "add one to contents of register '''z'''". The only access to address-register '''n''' is via a copy-from-A-to-N instruction called "set address '''n'''". To store a "datum" in accumulator '''z''' in a given register, the machine uses the contents of '''n''' to specify the register's address and register '''z''' to supply the datum to be sent to the register.

'''Peculiarities:''' A first peculiarity of the Schönhage RAM0 is how it "loads" something into register '''z''': register '''z''' first supplies the register-address and then secondly, receives the datum from the register{{spaced ndash}}a form of indirect "load". The second peculiarity is the specification of the COMPARE operation. This is a "jump if accumulator-register '''z'''=''zero'' (not, for example, "compare the contents of '''z''' to the contents of the register pointed to by '''n'''). Apparently if the test fails the machine skips over the next instruction which always must be in the form of "goto λ" where "λ" is the jump-to address. The instruction{{spaced ndash}}"compare contents of '''z''' to ''zero''" is unlike the Schonhage successor-RAM1 model (or any other known successor-models) with the more conventional "compare contents of register '''z''' to contents of register a for equality".

Primarily for reference{{spaced ndash}}this is a RAM model, not a counter-machine model{{spaced ndash}}the following is the Schönhage RAM0 instruction set:

{|class="wikitable" |- style="font-size:9pt" ! width="16.8" Height="9.6" align="center" valign="bottom" | ! width="48.6" valign="bottom" | Instruction ! width="227.4" align="center" valign="bottom" | Action: ! width="429" align="center" valign="bottom" | Description:

Again, the above instruction set is for a ''random-access machine'', a ''RAM''{{spaced ndash}}a counter machine with indirect addressing; instruction "N" allows for indirect storage of the accumulator, and instruction "L" allows for indirect load of the accumulator.

While peculiar, Schönhage's model shows how the conventional counter-machine's "register-to-register" or "read-modify-write" instruction set can be atomized to its simplest 0-parameter form. <!-- One possible instruction set (now using more conventional mnemonics) might be the following set 1A through 8. This set is not minimimal{{spaced ndash}}we can dispense with at least one instruction. But the arithmetic operations are "symmetric" in the sense that what we do to A (e.g. 1A, 2A, 3A) we can do to N (e.g. 1N, 2N, 3N), with the exception of 8 and 9 which use the contents of N to address the register that provides the datum to A (LDAN) or accepts the datum from A (STAN): {|class="wikitable" |- style="font-size:9pt" ! width="16.8" Height="9.6" align="center" valign="bottom" | ! width="48.6" valign="bottom" | Instruction ! width="246" align="center" valign="bottom" | Action: ! width="390.6" align="center" valign="bottom" | Description:

Shepherdson-Sturgis (1963) have shown how similar instruction sets, expanded with "convenience instructions" such as "CLRA" and "CLRN", are possible. The very convenient instruction "LDN k"{{spaced ndash}}LoaD N with "immediate" constant k (actually a register address) obtained from the instruction"{{spaced ndash}}is useful when the number of registers is known and bounded to less than some kmax.

As discussed above, the CPYAN instruction is required for indirect addressing.

If the jump-to address were in its own register (or even in N) then the jump-to address/parameter could be dispensed with. But all of this atomization comes at a significant cost{{spaced ndash}}the program must generate a register-address by successive INCN instructions, or a register-address by successive "INC_Jaddress", for example. -->

==References== {{Reflist|2}}

==Bibliography==

*{{Cite book |last1= Boolos |first1= George |author-link1= George Boolos |last2= Burgess |first2= John P. |author-link2= John P. Burgess |last3= Jeffrey |first3= Richard |author-link3= Richard Jeffrey |title= Computability and Logic |date= 2007 |edition= 5 |orig-date= 1974 |publisher= Cambridge University Press |location= Cambridge, England |isbn= 978-0-521-87752-7 }} The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 ''Abacus Computability''; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.

*{{cite book |last= Cutland |first= Nigel |year= 1980 |title= Computability: An Introduction to Recursive Function Theory |url= http://poincare.matf.bg.ac.rs/~zarkom/Book_Math__Cutland_Computability.pdf |publisher= Cambridge University Press |isbn= 0521223849 |access-date=7 November 2023 }}

*{{cite journal | last = Ershov | first = A. P. | author-link = Andrey Ershov | title = Ob operatsionnykh algoritmakh | trans-title = On Operator Algorithms | journal = Doklady Akademii Nauk SSSR | volume = 122 | year = 1958 | pages = 967–970 | language = ru }}, {{cite journal | last = Ershov | first = A. P. | author-link = Andrey Ershov | author-mask=0 | title = On Operator Algorithms | journal = Automatic Translation / Programming and Translation (Automat. Express) | volume = 1 | year = 1959 | pages = 20–23 | language = en }}

* {{citation | last1 = Fischer | first1 = Patrick C. | author1-link = Patrick C. Fischer | last2 = Meyer | first2 = A. R. | author2-link = Albert R. Meyer | last3 = Rosenberg | first3 = Arnold L. | author3-link = Arnold L. Rosenberg | journal = Mathematical Systems Theory | mr = 0235932 | pages = 265–283 | title = Counter machines and counter languages | volume = 2 | year = 1968 | issue = 3 | doi=10.1007/bf01694011| s2cid = 13006433 }}. Develops time hierarchy and space hierarchy theorems for counter machines, analogous to the hierarchies for Turing machines.

*{{cite journal | last = Hermes | first = Hans | author-link = Hans Hermes | title = Die Universalität programmgesteuerter Rechenmaschinen | journal = Mathematisch-Physikalische Semesterberichte (Göttingen) | volume = 4 | year = 1954 | pages = 42–53 | language = de }}

*{{cite journal | last = Kaphengst | first = Heinz | title = Eine Abstrakte programmgesteuerte Rechenmaschine | journal = Zeitschrift für mathematische Logik und Grundlagen der Mathematik | volume = 5 | year = 1959 | pages = 366–379 | language = de }}

*{{cite book | last = Kleene | first = Stephen Cole | author-link = Stephen Cole Kleene | title = Introduction to Metamathematics | publisher = D. Van Nostrand Company, Inc. | location = New York | date = 1952 | oclc = 523942 | lccn = 53001848 | pages = 550 }}, {{Cite book|last=Kleene|first=Stephen Cole|author-link=Stephen Cole Kleene|display-authors=0|title=reprint|publisher= Ishi Press|orig-year=1952|date=13 March 2009|isbn=9780923891572}}

*{{cite book | last = Knuth | first = Donald E. | author-link = Donald Knuth | title = The Art of Computer Programming | edition = 2nd | year = 1973 | origyear = 1968 | publisher = Addison-Wesley | location = Reading, Massachusetts | pages = 462–463 }} Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."

*{{cite journal | last = Lambek | first = Joachim | author-link = Joachim Lambek | date = September 1961 | title = How to Program an Infinite Abacus | journal = Mathematical Bulletin | volume = 4 | issue = 3 | pages = 295–302 }} In his Appendix II, Lambek proposes a "formal definition of 'program'. He references {{harvtxt|Melzak|1961}} and {{harvtxt|Kleene|1952}}. *{{cite journal | last = Melzak | first = Z. A. | title = An Informal Arithmetical Approach to Computability and Computation | journal = Canadian Mathematical Bulletin | volume = 4 | number = 3 | pages = 279–293 | date = September 1961 | doi = 10.4153/CMB-1961-031-9}} Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University." * {{cite journal|first=Marvin |last=Minsky|author-link=Marvin Minsky|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines|journal=Annals of Mathematics|date=1961|volume=74|pages=437-455|doi=10.2307/1970290|issue=3|jstor=1970290}} * {{cite book |first= Marvin |last=Minsky |author-link= Marvin Minsky |title = Computation: Finite and Infinite Machines |url= https://archive.org/details/computationfinit0000mins |url-access= registration | edition = 1st | publisher = Prentice-Hall, Inc.| location = Englewood Cliffs, N. J. | year = 1967}} In particular see chapter 11: ''Models Similar to Digital Computers'' and chapter 14: ''Very Simple Bases for Computability''. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.

*{{cite journal | last = Péter | first = Rózsa | author-link = Rózsa Péter | title = Graphschemata und rekursive Funktionen | journal = Dialectica | volume = 12 | year = 1958 | pages = 373 | language = de }}

* {{cite journal|last=Schönhage|first=Arnold|author-link=Arnold Schönhage|year=1980|title=Storage Modification Machines|journal=SIAM J. Comput.|volume=9|issue=3|pages=366–379|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/0209036 }} Wherein Schönhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc.

*{{cite report | last = Schroeppel | first = Rich | author-link = Rich Schroeppel | title = A Two Counter Machine Cannot Calculate 2N | institution = Massachusetts Institute of Technology, Artificial Intelligence Laboratory | type = AI Memo | series = AIM-257 | date = May 1972 | hdl=1721.1/6202 }} The author references {{harvtxt|Minsky|1967}} and notes that "Frances Yao independently proved the non-computability using a similar method in April 1971."

*{{Cite journal |last1= Shepherdson |first1= John C. |author-link1= John Shepherdson |last2= Sturgis |first2= H. E. |title= Computability of Recursive Functions |date= 1963 |journal= Journal of the ACM |volume= 10 |issue= 2 |pages= 217–255 |doi=10.1145/321160.321170 |doi-access= free }} An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

*{{cite book | last = van Emde Boas | first = Peter | author-link = Peter van Emde Boas | chapter = Machine Models and Simulations | pages = 3–66 | editor-last = Van Leeuwen | editor-first = Jan | editor-link = Jan van Leeuwen | title = Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity | edition = 1st | publisher = The MIT Press/Elsevier | year = 1990 | isbn = 9780444880710 }} Van Emde Boas' treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980 {{mdash}} it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.

*{{cite journal | last = Wang | first = Hao | author-link = Hao Wang (academic) | title = A Variant to Turing's Theory of Computing Machines | journal = Journal of the Association for Computing Machinery | volume = 4 | pages = 63–92 | year = 1957 | quote = Presented at the meeting of the Association, June 23–25, 1954 }}

==Further reading== * {{cite book |last=Wolfram |first=Stephen |author-link=Stephen Wolfram |title=A New Kind of Science |url=https://www.wolframscience.com/nks/ |publisher=Wolfram Media, Inc. |date=2002 |pages=[https://www.wolframscience.com/nks/p97--register-machines/ 97–102] |isbn=1-57955-008-8}}

Category:Models of computation