Editing Register machine (section)

== Bibliography ==
'''Background texts:''' The following bibliography of source papers includes a number of texts to be used as background. The mathematics that led to the flurry of papers about abstract machines in the 1950s and 1960s can be found in van Heijenoort (1967)<ref name="Heijenoort_1967"/>—an assemblage of original papers spanning the 50 years from Frege (1879)<ref name="Frege_1879"/> to Gödel (1931).<ref name="Gödel_1931"/> Davis (ed.) ''The Undecidable'' (1965)<ref name="Davis_1965"/> carries the torch onward beginning with Gödel (1931)<ref name="Gödel_1931"/> through Gödel's (1964) postscriptum;<ref name="Gödel_1964"/>{{rp|page=71}} the original papers of [[Alan Turing]] (1936<ref name="Turing_1936"/>–1937) and Emil Post (1936)<ref name="Post_1936"/> are included in ''The Undecidable''. The mathematics of Church, Rosser, and Kleene that appear as reprints of original papers in ''The Undecidable'' is carried further in Kleene (1952),<ref name="Kleene_1952"/> a mandatory text for anyone pursuing a deeper understanding of the mathematics behind the machines. Both Kleene (1952)<ref name="Kleene_1952"/> and Davis (1958)<ref name="Davis_1958"/> are referenced by a number of the papers.

For a good treatment of the counter machine see Minsky (1967) Chapter 11 "Models similar to Digital Computers"—he calls the counter machine a "program computer".<ref name="Minsky_1967"/> A recent overview is found at van Emde Boas (1990).<ref name="EmdeBoas_1990"/> A recent treatment of the Minsky (1961)<ref name="Minsky_1961"/>/Lambek (1961)<ref name="Lambek_1961"/> model can be found Boolos–Burgess–Jeffrey (2002);<ref name="Boolos-Burgess-Jeffrey_2002"/> they reincarnate Lambek's "abacus model" to demonstrate equivalence of Turing machines and partial recursive functions, and they provide a graduate-level introduction to both abstract machine models (counter- and Turing-) and the mathematics of recursion theory. Beginning with the first edition Boolos–Burgess (1970)<ref name="Boolos-Burgess_1970"/> this model appeared with virtually the same treatment.

'''The papers''': The papers begin with Wang (1957)<ref name="Wang_1957"/> and his dramatic simplification of the Turing machine. Turing (1936),<ref name="Turing_1936"/> Kleene (1952),<ref name="Kleene_1952"/> Davis (1958),<ref name="Davis_1958"/> and in particular Post (1936)<ref name="Post_1936"/> are cited in Wang (1957);<ref name="Wang_1957"/> in turn, Wang is referenced by Melzak (1961),<ref name="Melzak_1961"/> Minsky (1961),<ref name="Minsky_1961"/> and Shepherdson–Sturgis (1961–1963)<ref name="Shepherdson-Sturgis_1961"/><ref name="Shepherdson-Sturgis_1963"/> as they independently reduce the Turing tapes to "counters". Melzak (1961)<ref name="Melzak_1961"/> provides his pebble-in-holes counter machine model with indirection but doesn't carry the treatment further. The work of Elgot–Robinson (1964)<ref name="Elgot-Robinson_1964"/> 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 number]]s in the manner of Minsky (1961)<ref name="Minsky_1961"/>—leads to their definition of "indexed" instructions (i.e. indirect addressing) for their RASP model. Elgot–Robinson (1964)<ref name="Elgot-Robinson_1964"/> and more so Hartmanis (1971)<ref name="Hartmanis_1971"/> investigate RASPs with self-modifying programs. Hartmanis (1971)<ref name="Hartmanis_1971"/> specifies an instruction set with indirection, citing lecture notes of Cook (1970).<ref name="Cook_1970"/> For use in investigations of computational complexity Cook and his graduate student Reckhow (1973)<ref name="Cook-Reckhow_1973"/> 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 pointer machines are an offshoot of Knuth (1968,<ref name="Knuth_1968"/> 1973) and independently Schönhage (1980).<ref name="Schönhage_1980"/>

For the most part the papers contain mathematics beyond the undergraduate level—in particular the [[primitive recursive function]]s and [[mu recursive function]]s presented elegantly in Kleene (1952)<ref name="Kleene_1952"/> and less in depth, but useful nonetheless, in Boolos–Burgess–Jeffrey (2002).<ref name="Boolos-Burgess-Jeffrey_2002"/> 

All texts and papers excepting the four starred have been witnessed. These four are written in German and appear as references in Shepherdson–Sturgis (1963)<ref name="Shepherdson-Sturgis_1963"/> and Elgot–Robinson (1964);<ref name="Elgot-Robinson_1964"/> Shepherdson–Sturgis (1963)<ref name="Shepherdson-Sturgis_1963"/> offer a brief discussion of their results in Shepherdson–Sturgis' Appendix A. The terminology of at least one paper (Kaphengst (1959)<ref name="Kaphengst_1959"/> seems to hark back to the Burke–Goldstine–von Neumann (1946–1947)<ref name="Burks-Goldstine-Neumann_1947"/> analysis of computer architecture.

{|class="wikitable" style="text-align:center; font-size:88%"
|-  style="vertical-align:bottom;"
! style="width:114.6;"| Author
! style="width:43.2;"| Year
! style="width:46.8;"| Reference
! style="width:41.4;"| Turing machine
! style="width:43.2;"| Counter machine
! style="width:27.6;"| RAM
! style="width:28.2;"| RASP
! style="width:38.4;"| Pointer machine
! style="width:54px;"| Indirect addressing
! style="width:43.8;"| Self-modifying program
|-  style="vertical-align:bottom;"
| style="text-align:left" | Goldstine & von Neumann
| 1947<ref name="Burks-Goldstine-Neumann_1947"/>
| {{ya}}
|
|
|
|
|
|
| {{ya}}
|-  style="vertical-align:bottom;"
| style="text-align:left" | Kleene
| 1952<ref name="Kleene_1952"/>
| {{ya}}
|
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Hermes
| 1954–1955<ref name="Hermes_1954"/>
|
|
| {{dunno}}
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Wang
| 1957<ref name="Wang_1957"/>
| {{ya}}
| {{ya}}
| hints
|
|
|
| hints
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Péter
| 1958<ref name="Péter_1958"/>
|
|
| {{dunno}}
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Davis
| 1958<ref name="Davis_1958"/>
| {{ya}}
| {{ya}}
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Ershov
| 1959<ref name="Ershov_1958"/>
|
|
| {{dunno}}
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Kaphengst
| 1959<ref name="Kaphengst_1959"/>
|
|
| {{dunno}}
|
| {{ya}}
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Melzak
| 1961<ref name="Melzak_1961"/>
|
|
| {{ya}}
|
|
|
| {{ya}}
| hints
|-  style="vertical-align:bottom;"
| style="text-align:left" | Lambek
| 1961<ref name="Lambek_1961"/>
|
|
| {{ya}}
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Minsky
| 1961<ref name="Minsky_1961"/>
|
|
| {{ya}}
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Shepherdson & Sturgis
| 1963<ref name="Shepherdson-Sturgis_1963"/>
|
|
| {{ya}}
|
|
|
| hints
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Elgot & Robinson
| 1964<ref name="Elgot-Robinson_1964"/>
|
|
|
|
| {{ya}}
|
| {{ya}}
| {{ya}}
|-  style="vertical-align:bottom;"
| style="text-align:left" | Davis- Undecidable
| 1965<ref name="Davis_1965"/>
| {{ya}}
| {{ya}}
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | van Heijenoort
| 1967<ref name="Heijenoort_1967"/>
| {{ya}}
|
|
|
|
|
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Minsky
| 1967<ref name="Minsky_1967"/>
|
|
| {{ya}}
| hints
|
|
| hints
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Knuth
| 1968,<ref name="Knuth_1968"/> 1973
| {{ya}}
|
|
|
|
| {{ya}}
| {{ya}}
| {{ya}}
|-  style="vertical-align:bottom;"
| style="text-align:left" | Hartmanis
| 1971<ref name="Hartmanis_1971"/>
|
|
|
|
| {{ya}}
|
|
| {{ya}}
|-  style="vertical-align:bottom;"
| style="text-align:left" | Cook & Reckhow
| 1973<ref name="Cook-Reckhow_1973"/>
|
|
|
| {{ya}}
| {{ya}}
|
| {{ya}}
| {{ya}}
|-  style="vertical-align:bottom;"
| style="text-align:left" | Schönhage
| 1980<ref name="Schönhage_1980"/>
|
|
|
| {{ya}}
|
| {{ya}}
| {{ya}}
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | van Emde Boas
| 1990<ref name="EmdeBoas_1990"/>
| {{ya}}
| {{ya}}
| {{ya}}
| {{ya}}
| {{ya}}
| {{ya}}
|
|
|-  style="vertical-align:bottom;"
| style="text-align:left" | Boolos & Burgess; Boolos, Burgess & Jeffrey
| 1970<ref name="Boolos-Burgess_1970"/>–2002<ref name="Boolos-Burgess-Jeffrey_2002"/>
| {{ya}}
| {{ya}}
| {{ya}}
|
|
|
|
|
|}