Editing Register machine (section)

==References==
{{reflist|refs=
<ref name="Abelson-Sussman_1996">[[Harold Abelson]] and [[Gerald Jay Sussman]] with Julie Sussman, [[Structure and Interpretation of Computer Programs]], [[MIT Press]], [[Cambridge, Massachusetts]], 2nd edition, 1996</ref>
<ref name="Melzak_1961">{{cite journal |author-last=Melzak |author-first=Zdzislaw Alexander |author-link1=:d:Q95321564 |date=September 1961 |title=An Informal Arithmetical Approach to Computability and Computation |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=89, 279–293 [89, 281, 288, 290–292] |doi=10.4153/CMB-1961-031-9 |doi-access=free}} The manuscript was received by the journal on 15 May 1961. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssotsky of the Bell Telephone Laboratories and with Dr. H. Wang of Oxford University." [https://web.archive.org/web/20230520150655/https://www.cambridge.org/core/services/aop-cambridge-core/content/view/C94994F05E6820B5014B7A3A14024726/S0008439500050955a.pdf/an-informal-arithmetical-approach-to-computability-and-computation.pdf]</ref>
<ref name="Minsky_1961">{{cite journal |author-last=Minsky |author-first=Marvin |author-link=Marvin Minsky |date=1961 |title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines |journal=Annals of Mathematics |jstor=1970290 |volume=74 |issue=3 |pages=437–455 [438, 449] |doi=10.2307/1970290}}</ref>
<ref name="Lambek_1961">{{cite journal |author-last=Lambek |author-first=Joachim |author-link=Joachim Lambek |date=September 1961 |title=How to Program an Infinite Abacus |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=295–302 [295] |doi=10.4153/CMB-1961-032-6 |doi-access=free}} The manuscript was received by the journal on 15 June 1961. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.</ref>
<ref name="McCarthy_1960">McCarthy (1960)</ref>
<ref name="Hermes_1954">[[Hans Hermes]] "Die Universalität programmgesteuerter Rechenmaschinen". ''Math.-Phys. Semesterberichte'' (Göttingen) 4 (1954), 42–53.</ref>
<ref name="Péter_1958">[[Rózsa Péter|Péter, Rózsa]] "Graphschemata und rekursive Funktionen", ''Dialectica'' 12 (1958), 373.</ref>
<ref name="Kaphengst_1959">{{ill|Heinz Kaphengst|de|Heinz Kaphengst|lt=Kaphengst, Heinz}}, "Eine Abstrakte Programmgesteuerte Rechenmaschine", ''Zeitschrift fur mathematische Logik und Grundlagen der Mathematik'' 5 (1959), 366–379. [https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19590051413]</ref>
<ref name="Wang_1954">[[Hao Wang (academic)|Hao Wang]] "Variant to Turing's Theory of Computing Machines". Presented at the meeting of the Association, 23–25 June 1954.</ref>
<ref name="Wang_1957">[[Hao Wang (academic)|Hao Wang]] (1957), "A Variant to Turing's Theory of Computing Machines", ''JACM'' (''Journal of the Association for Computing Machinery'') 4; 63–92. Presented at the meeting of the Association, 23–25 June 1954.</ref>
<ref name="Minsky_1967">{{cite book |author-last=Minsky |author-first=Marvin |author-link=Marvin Minsky |date=1967 |title=Computation: Finite and Infinite Machines |url=https://archive.org/details/computationfinit0000mins |url-access=registration |edition=1st |publisher=Prentice-Hall, Inc. |location=Englewood Cliffs, New Jersey, USA |page=214}} 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.</ref>
<ref name="Shepherdson-Sturgis_1963">Shepherdson, Sturgis (1963): [[John C. Shepherdson]] and [[H. E. Sturgis]] (1961) received December 1961 "Computability of Recursive Functions", ''Journal of the Association for Computing Machinery'' (JACM) 10:217–255 [218, 219, 245ff, 246], 1963. 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".</ref>
<ref name="Matiyasevich_1993">[[Yuri Matiyasevich]], ''Hilbert's Tenth Problem'', commentary to Chapter 5 of the book, at http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm.)</ref>
<ref name="Post_1936">Emil Post (1936)</ref>
<ref name="Lee_1961">C. Y. Lee (1961)</ref>
<ref name="Hopcroft-Ullman_1979">[[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. {{isbn|0-201-02988-X}}, pp. 171ff. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.</ref>
<ref name="Elgot-Robinson_1964">[[Calvin Elgot]] and [[Abraham Robinson]] (1964), "Random-Access Stored-Program Machines, an Approach to Programming Languages", ''Journal of the Association for Computing Machinery'', Vol. 11, No. 4 (October 1964), pp.&nbsp;365–399.</ref>
<ref name="Cook-Reckhow_1973">[[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354–375.</ref>
<ref name="Burks-Goldstine-Neumann_1947">[[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946–1947), "Preliminary discussion of the logical design of an electronic computing instrument", reprinted pp.&nbsp;92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. {{isbn|0-07-004357-4}}.</ref>
<ref name="Hartmanis_1971">[[Juris Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," ''Mathematical Systems Theory'' 5, 3 (1971) pp.&nbsp;232–245.</ref>
<ref name="Shepherdson-Sturgis_1961">Shepherdson, Sturgis (1961), p. 219</ref>
<ref name="Ershov_1958">[[Andrey Ershov|Ershov, Andrey P.]] "On operator algorithms", (Russian) ''Dok. Akad. Nauk'' 122 (1958), 967–970. English translation, Automat. Express 1 (1959), 20–23.</ref>
<ref name="Davis_1958">[[Martin Davis (mathematician)|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.</ref>
<ref name="Knuth_1968">[[Donald Knuth]] (1968), ''The Art of Computer Programming'', Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462–463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."</ref>
<ref name="EmdeBoas_1990">[[Peter van Emde Boas]], "Machine Models and Simulations" pp.&nbsp;3–66, in: [[Jan van Leeuwen]], ed. ''Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', The MIT PRESS/Elsevier, 1990. {{isbn|0-444-88071-2}} (volume A). QA 76.H279 1990. van Emde Boas' treatment of SMMs appears on pp.&nbsp;32–35. This treatment clarifies Schōnhage 1980—it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.</ref>
<ref name="Kleene_1952">[[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. {{isbn|0-7204-2103-9}}.</ref>
<ref name="Schönhage_1980">[[Arnold Schönhage]] (1980), ''Storage Modification Machines'', Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. ''Storage Modification Machines'', in ''Theoretical Computer Science'' (1979), pp.&nbsp;36–37</ref>
<ref name="Boolos-Burgess-Jeffrey_2002">[[George Boolos]], [[John P. Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, England. 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.</ref>
<ref name="Boolos-Burgess_1970">[[George Boolos]], [[John P. Burgess]] (1970)</ref>
<ref name="Frege_1879">Frege (1879)</ref>
<ref name="Gödel_1931">Gödel (1931)</ref>
<ref name="Gödel_1964">Gödel (1964), postscriptum p. 71.</ref>
<ref name="Davis_1965">Davis (ed.) ''The Undecidable'' (1965)</ref>
<ref name="Heijenoort_1967">van Heijenoort (1967)</ref>
<ref name="Turing_1936">Turing (1936)</ref>
<ref name="Cook_1970">Cook (1970)</ref>
}}