Editing Register machine (section)

===Minsky, Melzak–Lambek and Shepherdson–Sturgis models "cut the tape" into many===
{{Tone|section|date=January 2024}}
Initial thought leads to 'cutting the tape' so that each is infinitely long (to accommodate any size integer) but left-ended. These three tapes are called "Post–Turing (i.e. Wang-like) tapes". The individual heads move to the left (for decrementing) and to the right (for incrementing). In a sense, the heads indicate "the top of the stack" of concatenated marks. Or in Minsky (1961)<ref name="Minsky_1961"/> and Hopcroft and Ullman (1979),<ref name="Hopcroft-Ullman_1979"/>{{rp|pages=171ff}} the tape is always blank except for a mark at the left end—at no time does a head ever print or erase.

Care must be taken to write the instructions so that a test for zero and a jump occur ''before'' decrementing, otherwise the machine will "fall off the end" or "bump against the end"—creating an instance of a [[partial function]]. 

Minsky (1961)<ref name="Minsky_1961"/> and Shepherdson–Sturgis (1963)<ref name="Shepherdson-Sturgis_1963"/> prove that only a few tapes—as few as one—still allow the machine to be Turing equivalent if the data on the tape is represented as a [[Gödel number]] (or some other uniquely encodable Encodable-decodable number); this number will evolve as the computation proceeds. In the one tape version with [[Gödel numbering|Gödel number]] encoding the counter machine must be able to (i) multiply the Gödel number by a constant (numbers "2" or "3"), and (ii) divide by a constant (numbers "2" or "3") and jump if the remainder is zero. Minsky (1967)<ref name="Minsky_1967" /> shows that the need for this bizarre instruction set can be relaxed to { INC (r), JZDEC (r, z) } and the convenience instructions { CLR (r), J (r) } if two tapes are available. However, a simple Gödelization is still required. A similar result appears in Elgot–Robinson (1964)<ref name="Elgot-Robinson_1964" /> with respect to their RASP model.<!-- To do a multiplication algorithm we don't need the extra mark to indicate "0", but we will need an extra "temporary" tape '''t'''.  And we will need an extra "blank/zero" register (e.g. register #0) for an unconditional jump:

{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
|style="font-weight:bold" width="83.4" Height="12" | At  the start:
| width="16.8" |
| width="15" |
| width="16.2" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
| width="15" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | register 0:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | a = register 1:
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99;font-weight:bold" | []
|style="font-weight:bold" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | b = register 2:
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | c = register 3:
|style="background-color:#CCFFFF;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | t = register 4:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="3" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt"
|style="font-weight:bold" Height="12" align="center" valign="bottom" | At the end:
|  valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
| align="center" valign="bottom" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | register 0:
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | a = register 1:
|style="background-color:#FFFF99;font-weight:bold" | []
 |
 |
 |
|style="font-weight:bold" |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | b = register 2:
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC;font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | c = register 3:
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF" | 1
|style="background-color:#CCFFFF;font-weight:bold" | []
 |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | t = register 4:
 | 1
 | 1
 | 1
 | 1
|style="font-weight:bold" | []
 |
 |
 |
 |
 |
 |
 |
 |
 |
|}

We can write simple Post–Turing "subroutines" to atomize "increment" and "decrement" into Post–Turing instructions. Note that the head stays always just one square to the right of the top-most printed mark, i.e. at the "top of the stack". "r" is a parameter in the instructions that symbolizes the tape-as-register to be moved and printed or erased, and tested:
:
: "Increment r" = PRINT_SCANNED_SQUARE_of_TAPE_r, MOVE_TAPE_r_LEFT; i.e. (or: move tape r's head right)
::'''X+''' r is equivalent to '''P''' r; '''L''' r
: "Decrement r" = JUMP_IF_TAPE_r_BLANK(ZERO) TO XXX, ELSE MOVE_TAPE_r_RIGHT, ERASE_SCANNED_SQUARE_of_TAPE_rN; (or: move tape r's head left)
::'''X-''' r is equivalent to '''J0''' r, xxx; '''R''' r; '''E''' r

Indeed this is similar to the approach that Minsky (1961)<ref name="Minsky_1961"/> took. He started with 4 left-ended tape-machine that:
: "used the basic arithmetic device of the present paper. Then, two of the tapes were eliminated by the prime-factor method".<ref name="Minsky_1961"/>{{rp|page=438}}

He then observed that:
: "we may formulate these results so that the operations act essentially only on the ''length'' of the strings"<ref name="Minsky_1961"/>{{rp|page=449}}

His first model, "1961" (it had changed by 1967<ref name="Minsky_1967"/>) started out with only a single mark at the left end of each tape-as-register. The machine was not allowed to '''P'''rint any marks, just move '''L'''eft or '''R'''ight and test for the mark = "1" in the following example. Thus the conventional Post–Turing-like instruction set went from
: { R; L; P; E; J0 xxx; J1 xxx, H }

to, for each tape-as-register:
: { R; L; J1 xxx, H }

where '''R''' can be renamed '''INC'''rement, '''R''' can be renamed '''DEC'''rement, "J1" can be combined with "DEC" to create a non-atomized instruction, or can be kept separate and renamed '''J'''ump if '''Z'''ero. -->