Editing Register machine (section)

=== Wang's (1954, 1957) model: Post–Turing machine ===
Wang's work followed from Emil Post's (1936)<ref name="Post_1936"/> paper and led Wang to his definition of his [[Wang B-machine]]—a two-symbol [[Post–Turing machine]] computation model with only four atomic instructions:
 { LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }
To these four both Wang (1954,<ref name="Wang_1954"/> 1957<ref name="Wang_1957"/>) and then C. Y. Lee (1961)<ref name="Lee_1961"/> added another instruction from the Post set { ERASE }, and then a Post's unconditional jump { JUMP_to_ instruction_z } (or to make things easier, the conditional jump JUMP_IF_blank_to_instruction_z, or both. Lee named this a "W-machine" model:
 { LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }
Wang expressed hope that his model would be "a rapprochement"<!-- which one? <ref name="Wang_1954"/> or <ref name="Wang_1957"/> -->{{rp|page=63}} between the theory of Turing machines and the practical world of the computer.

Wang's work was highly influential. We find him referenced by Minsky (1961)<ref name="Minsky_1961"/> and (1967),<ref name="Minsky_1967"/> Melzak (1961),<ref name="Melzak_1961"/> Shepherdson and Sturgis (1963).<ref name="Shepherdson-Sturgis_1963"/> Indeed, Shepherdson and Sturgis (1963) remark that:
:"''...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested by Wang,''"<ref name="Shepherdson-Sturgis_1963"/>{{rp|page=218}}

[[Martin Davis (mathematician)|Martin Davis]] eventually evolved this model into the (2-symbol) Post–Turing machine.

'''Difficulties with the Wang/Post–Turing model''':

Except there was a problem: the Wang model (the six instructions of the 7-instruction Post–Turing machine) was still a single-tape Turing-like device, however nice its ''sequential program instruction-flow'' might be. Both Melzak (1961)<ref name="Melzak_1961"/> and Shepherdson and Sturgis (1963)<ref name="Shepherdson-Sturgis_1963"/> observed this (in the context of certain proofs and investigations):

:"''...a Turing machine has a certain opacity... a Turing machine is slow in (hypothetical) operation and, usually, complicated. This makes it rather hard to design it, and even harder to investigate such matters as time or storage optimization or a comparison between the efficiency of two algorithms.<ref name="Melzak_1961" />{{rp|page=281}} "...although not difficult... proofs are complicated and tedious to follow for two reasons: (1) A Turing machine has only a head so that one is obliged to break down the computation into very small steps of operations on a single digit. (2) It has only one tape so that one has to go to some trouble to find the number one wishes to work on and keep it separate from other numbers''"<ref name="Shepherdson-Sturgis_1963" />{{rp|page=218}}

Indeed, as examples in [[Turing machine examples]], Post–Turing machine and [[partial function|partial functions]] show, the work can be "complicated".
<!-- Example: Multiply '''a''' x '''b''' = '''c''', for example: 3 x 4 = 12.

The scanned square is indicated by brackets around the mark i.e. ['''1''']. An extra mark serves to indicate the symbol "0".

At the start of a computation, just as Shepherdson–Sturgis and Melzak complain, we see the variables expressed in unary—i.e. the tally marks for '''a'''= '''| | | |''' and '''b''' = '''| | | | |''' – "in a line" (concatenated on what Melzak calls a "linear tape"). Space must be available for '''c''' at the end of the computation, extending without bounds to the right:
{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
| width="14.4" Height="11.4" |
| width="13.8" |
| width="13.8" |
| width="13.8" | top
| width="13.8" | a
| width="13.8" | a
| width="13.8" | a
| width="13.8" |
| width="13.8" | top
| width="13.8" | b
| width="13.8" | b
| width="13.8" | b
| width="15.6" | b
| width="13.8" |
| width="13.8" | btm
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" |
| width="13.8" |
| width="13.8" |
|- style="font-size:9pt" align="center" valign="bottom"
| Height="11.4" |
 |
 |
|style="background-color:#FFFF99" | [1]
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
|style="background-color:#FFFF99" | 1
 |
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|}

At the end of the computation the multiplier '''b''' is 5 marks "in a line" (i.e. concatenated) to left of the 13 marks of product '''c'''.
{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
| width="14.4" Height="11.4" |
| width="13.8" |
| width="13.8" |
| width="13.8" | top
| width="13.8" | a
| width="13.8" | a
| width="13.8" | a
| width="13.8" |
| width="13.8" | top
| width="13.8" | b
| width="13.8" | b
| width="13.8" | b
| width="15.6" | b
| width="13.8" |
| width="16.8" | btm
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
| width="13.8" | c
|- style="font-size:9pt" align="center" valign="bottom"
| Height="11.4" |
 |
 |
 |
 |
 |
 |
 |
|style="background-color:#CCFFCC" | [1]
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
|style="background-color:#CCFFCC" | 1
 |
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
|style="background-color:#99CCFF" | 1
 |
 |
 |
|}-->