Counter-machine model

This page supplements counter machine.

Although some authors use the name "register machine" synonymously with "counter machine", this article will give details and examples of only of the most primitive species – the "counter machine" – of the genus "register machine."

Within the species "counter machine" there are a number of varieties: the models of Hermes (1954), Kaphengst (1957), Ershov (1958), Péter (1958), Minsky (1961) and Minsky (1967), Melzak (1961), Lambek (1961), Shepherdson and Sturgis (1963), and Schönhage (1980). These models will be described in more detail in the following.

Shepherdson and Sturgis 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" (Shepherdson and Sturgis, p. 219).

Shepherdson and Sturgis observe that:

The only two arithmetic instructions are

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 results in strange words 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 report of Burks-Goldstine-von Neumann (1946) 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:

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

Shepherdson and Sturgis 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 Minsky (1967); see more in the section below.

...
Wikipedia