Random-access stored-program machine - Revision history

WOSlinker: fix italics

2024-06-08T06:20:15Z

fix italics

← Previous revision		Revision as of 06:20, 8 June 2024
Line 2,235:		Line 2,235:
	:* [[Andrey Ershov\|Ershov, A. P.]] ''On operator algorithms'', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.		:* [[Andrey Ershov\|Ershov, A. P.]] ''On operator algorithms'', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
	:* [[Rózsa Péter\|Péter, Rózsa]] ''Graphschemata und rekursive Funktionen'', Dialectica 12 (1958), 373.		:* [[Rózsa Péter\|Péter, Rózsa]] ''Graphschemata und rekursive Funktionen'', Dialectica 12 (1958), 373.
	:* Hermes, Hans ''Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.		:* Hermes, Hans ''Die Universalität programmgesteuerter Rechenmaschinen''. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.
	* [[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. 36–37		* [[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. 36–37
	* [[Peter van Emde Boas]], ''Machine Models and Simulations'' pp. 3–66, appearing 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.		* [[Peter van Emde Boas]], ''Machine Models and Simulations'' pp. 3–66, appearing 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. 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.		:van Emde Boas' treatment of SMMs appears on pp. 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.
	* [[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, June 23–25, 1954.		* [[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, June 23–25, 1954.

Citation bot: Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 159/193

2023-06-25T21:42:41Z

Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 159/193

← Previous revision		Revision as of 21:42, 25 June 2023
Line 2,228:		Line 2,228:
	\|volume=74		\|volume=74
	\|pages=437–455		\|pages=437–455
	\|doi=10.2307/1970290\|issue=3~~\|publisher=Annals of Mathematics~~\|jstor=1970290		\|doi=10.2307/1970290\|issue=3\|jstor=1970290
	}}		}}
	*{{cite book \|author= [[Marvin Minsky]] \|title = Computation: Finite and Infinite Machines \|url= https://archive.org/details/computationfinit0000mins \|url-access= registration \| edition = 1st \| publisher = Prentice-Hall, Inc.\| location = Englewood Cliffs, N. J. \| year = 1967 \|isbn= 0-13-165449-7}} 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.		*{{cite book \|author= [[Marvin Minsky]] \|title = Computation: Finite and Infinite Machines \|url= https://archive.org/details/computationfinit0000mins \|url-access= registration \| edition = 1st \| publisher = Prentice-Hall, Inc.\| location = Englewood Cliffs, N. J. \| year = 1967 \|isbn= 0-13-165449-7}} 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.

Onel5969: clean up, typo(s) fixed: 354-375 → 354–375 (3)

2023-06-17T13:29:42Z

clean up, typo(s) fixed: 354-375 → 354–375 (3)

Certes: typo: Association for Computing Machinery (via WP:JWB)

2023-03-20T20:37:32Z

typo: Association for Computing Machinery (via WP:JWB)

← Previous revision		Revision as of 20:37, 20 March 2023
Line 2,231:		Line 2,231:
	}}		}}
	*{{cite book \|author= [[Marvin Minsky]] \|title = Computation: Finite and Infinite Machines \|url= https://archive.org/details/computationfinit0000mins \|url-access= registration \| edition = 1st \| publisher = Prentice-Hall, Inc.\| location = Englewood Cliffs, N. J. \| year = 1967 \|isbn= 0-13-165449-7}} 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.		*{{cite book \|author= [[Marvin Minsky]] \|title = Computation: Finite and Infinite Machines \|url= https://archive.org/details/computationfinit0000mins \|url-access= registration \| edition = 1st \| publisher = Prentice-Hall, Inc.\| location = Englewood Cliffs, N. J. \| year = 1967 \|isbn= 0-13-165449-7}} 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.
	* [[John C. Shepherdson]] and [[H. E. Sturgis]] (1961) received December 1961 ''Computability of Recursive Functions'', Journal of the Association of Computing Machinery (JACM) 10:217-255, 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".		* [[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, 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".
	:* Kaphengst, Heinz, ''Eine Abstrakte programmgesteuerte Rechenmaschine''', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:''5'' (1959), 366-379.		:* Kaphengst, Heinz, ''Eine Abstrakte programmgesteuerte Rechenmaschine''', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:''5'' (1959), 366-379.
	:* [[Andrey Ershov\|Ershov, A. P.]] ''On operator algorithms'', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.		:* [[Andrey Ershov\|Ershov, A. P.]] ''On operator algorithms'', (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.

Mdmi: correct the link for Hartmanis

2022-09-23T11:25:55Z

correct the link for Hartmanis

← Previous revision		Revision as of 11:25, 23 September 2022
Line 2,216:		Line 2,216:
	* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.		* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
	* [[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. 365–399.		* [[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. 365–399.
	* [[J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.		* [[Juris Hartmanis \| J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
	* [[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. {{ISBN\|0-201-02988-X}}. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.		* [[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. {{ISBN\|0-201-02988-X}}. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
	* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. {{ISBN\|0-7204-2103-9}}.		* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. {{ISBN\|0-7204-2103-9}}.

Mdmi: Melzak: supply cross-references, correct spellings that were miscopied from the reference; Boolos: tweak grammar; Bell: capitalize McGraw

2022-09-23T11:21:13Z

Melzak: supply cross-references, correct spellings that were miscopied from the reference; Boolos: tweak grammar; Bell: capitalize McGraw

← Previous revision		Revision as of 11:21, 23 September 2022
Line 2,211:		Line 2,211:
	Often both the RAM and RASP machines are presented together in the same article. These have been copied over from [[Random-access machine]]; with a few exceptions, these references are the same as those at [[Register machine]].		Often both the RAM and RASP machines are presented together in the same article. These have been copied over from [[Random-access machine]]; with a few exceptions, these references are the same as those at [[Register machine]].

	* [[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~~.		* [[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 two recursion models.
	* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp. 92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', ~~mcGraw~~-Hill Book Company, New York. {{ISBN\|0-07-004357-4}} .		* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp. 92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. {{ISBN\|0-07-004357-4}} .
	* [[Stephen Cook\|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354-375.		* [[Stephen Cook\|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354-375.
	* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.		* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
Line 2,221:		Line 2,221:
	* [[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."		* [[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."
	* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.		* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.
	* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', [[Canadian Mathematical Bulletin]], vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. ~~Vyssots~~ of the Bell telephone ~~Laborators~~ and with Dr. H. Wang of Oxford University."		* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', [[Canadian Mathematical Bulletin]], vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. [[Richard Hamming \| R. Hamming]], [[Douglas McIlroy \| D. McIlroy]] and [[Victor A. Vyssotsky \| V. Vyssotsky]] of the [[Bell Labs \| Bell telephone Laboratories]] and with Dr. [[Hao Wang (academic) \| H. Wang]] of [[University of Oxford \| Oxford University]]
	*{{cite journal\|author=[[Marvin Minsky]]		*{{cite journal\|author=[[Marvin Minsky]]
	\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines		\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines

Paul2520: clears CS1 date error(s) (via WP:JWB)

2022-09-19T15:49:51Z

clears CS1 date error(s) (via WP:JWB)

← Previous revision		Revision as of 15:49, 19 September 2022
Line 2,225:		Line 2,225:
	\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines		\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines
	\|journal=Annals of Mathematics		\|journal=Annals of Mathematics
	\|date=1961~~, received August 15, 1960~~		\|date=1961
	\|volume=74		\|volume=74
	\|pages=437–455		\|pages=437–455

TheMathCat: wikilink

2021-08-13T17:14:30Z

wikilink

← Previous revision		Revision as of 17:14, 13 August 2021
Line 2,221:		Line 2,221:
	* [[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."		* [[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."
	* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.		* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.
	* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."		* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', [[Canadian Mathematical Bulletin]], vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
	*{{cite journal\|author=[[Marvin Minsky]]		*{{cite journal\|author=[[Marvin Minsky]]
	\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines		\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines

Beland: convert special characters (via WP:JWB)

2021-05-25T06:54:53Z

convert special characters (via WP:JWB)

← Previous revision		Revision as of 06:54, 25 May 2021
Line 63:		Line 63:
	To ease the example we will equip the ''state machine'' of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions:		To ease the example we will equip the ''state machine'' of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions:
	:RAM state machine instructions:		:RAM state machine instructions:
	::{ INC h; DEC h; JZ h,xxx; CPY ~~⟪h~~{{sub\|a}}~~⟫~~,{{angbr\|h{{sub\|a}}}}; CPY {{angbr\|h{{sub\|a}}}},~~⟪h~~{{sub\|a}}~~⟫~~ }		::{ INC h; DEC h; JZ h,xxx; CPY ⟪h{{sub\|a}}⟫,{{angbr\|h{{sub\|a}}}}; CPY {{angbr\|h{{sub\|a}}}},⟪h{{sub\|a}}⟫ }

	As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" {{--}} converts to action {{--}} the program:		As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" {{--}} converts to action {{--}} the program:
Line 227:		Line 227:

	The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:		The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:
	* copy indirect from i and direct to j: CPY ~~⟪h~~{{sub\|i}}~~⟫~~,{{angbr\|h{{sub\|j}}}}		* copy indirect from i and direct to j: CPY ⟪h{{sub\|i}}⟫,{{angbr\|h{{sub\|j}}}}
	* copy direct from i and indirect to j: CPY {{angbr\|h{{sub\|i}}}},~~⟪h~~{{sub\|j}}~~⟫~~		* copy direct from i and indirect to j: CPY {{angbr\|h{{sub\|i}}}},⟪h{{sub\|j}}⟫

	The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the column labelled "State machine instruction ↓". Observe that at the end of the fetch, register #2 contains the numerical value 3 of the "operation code" ("opcode") of the first instruction '''JZ''':		The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the column labelled "State machine instruction ↓". Observe that at the end of the fetch, register #2 contains the numerical value 3 of the "operation code" ("opcode") of the first instruction '''JZ''':
Line 373:		Line 373:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 5 i		\|style="font-weight:bold" \| 5 i
	\|style="font-weight:bold" \| [3]		\|style="font-weight:bold" \| [3]
Line 542:		Line 542:
	!		!
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 5 i		\|style="font-weight:bold" \| 5 i
	\|style="font-weight:bold" \| [3]		\|style="font-weight:bold" \| [3]
Line 993:		Line 993:
	! 10		! 10
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 6 i		\|style="font-weight:bold" \| 6 i
	\|style="font-weight:bold" \| [18]		\|style="font-weight:bold" \| [18]
Line 1,016:		Line 1,016:
	! 11		! 11
	\| test hole:		\| test hole:
	\| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| CPY ⟪2⟫,{{angbr\|3}}
	\|style="font-weight:bold" \| 6		\|style="font-weight:bold" \| 6
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,154:		Line 1,154:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 8 i		\|style="font-weight:bold" \| 8 i
	\|style="font-weight:bold" \| [2]		\|style="font-weight:bold" \| [2]
Line 1,246:		Line 1,246:
	! 14		! 14
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|1}}		\| CPY ⟪1⟫,{{angbr\|1}}
	\|style="font-weight:bold" \| [15]		\|style="font-weight:bold" \| [15]
	\|style="font-weight:bold" \| 18		\|style="font-weight:bold" \| 18
Line 1,292:		Line 1,292:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 15 i		\|style="font-weight:bold" \| 15 i
	\|style="font-weight:bold" \| [0]		\|style="font-weight:bold" \| [0]
Line 1,508:		Line 1,508:
	! 16		! 16
	\|style="font-weight:bold" \| fetch_instr:		\|style="font-weight:bold" \| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 8 i		\|style="font-weight:bold" \| 8 i
	\|style="font-weight:bold" \| [2]		\|style="font-weight:bold" \| [2]
Line 1,669:		Line 1,669:
	! 23		! 23
	\|		\|
	\| \| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| \| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 9 i		\|style="font-weight:bold" \| 9 i
	\|style="font-weight:bold" \| 18		\|style="font-weight:bold" \| 18
Line 1,692:		Line 1,692:
	! 24		! 24
	\|		\|
	\| \| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| \| CPY ⟪2⟫,{{angbr\|3}}
	\|style="color:#808080" \| 9		\|style="color:#808080" \| 9
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,761:		Line 1,761:
	! 27		! 27
	\|		\|
	\| \| CPY {{angbr\|3}},~~⟪2⟫~~		\| \| CPY {{angbr\|3}},⟪2⟫
	\|style="color:#808080" \| 9		\|style="color:#808080" \| 9
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,853:		Line 1,853:
	! 30		! 30
	\|style="font-weight:bold" \| fetch_instr:		\|style="font-weight:bold" \| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 10 i		\|style="font-weight:bold" \| 10 i
	\|style="font-weight:bold" \| 1		\|style="font-weight:bold" \| 1
Line 1,968:		Line 1,968:
	! 35		! 35
	\|		\|
	\| \| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| \| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 11 i		\|style="font-weight:bold" \| 11 i
	\|style="font-weight:bold" \| 19		\|style="font-weight:bold" \| 19
Line 1,991:		Line 1,991:
	! 36		! 36
	\|		\|
	\| \| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| \| CPY ⟪2⟫,{{angbr\|3}}
	\|style="color:#808080" \| 11		\|style="color:#808080" \| 11
	\|style="font-weight:bold" \| 19 i		\|style="font-weight:bold" \| 19 i
Line 2,037:		Line 2,037:
	! 38		! 38
	\|		\|
	\| \| CPY {{angbr\|3}},~~⟪2⟫~~		\| \| CPY {{angbr\|3}},⟪2⟫
	\|style="color:#808080" \| 11		\|style="color:#808080" \| 11
	\|style="font-weight:bold" \| 19 i		\|style="font-weight:bold" \| 19 i
Line 2,128:		Line 2,128:
	\|}		\|}

	'''Alternate instructions''': Although the demonstration resulted in a primitive RASP of only four instructions, the reader might imagine how an additional instruction such as "ADD {{angbr\|h}}" or "MULT {{angbr\|h{{sub\|a}}}},~~⟪h~~{{sub\|b}}>might be done.		'''Alternate instructions''': Although the demonstration resulted in a primitive RASP of only four instructions, the reader might imagine how an additional instruction such as "ADD {{angbr\|h}}" or "MULT {{angbr\|h{{sub\|a}}}},⟪h{{sub\|b}}>might be done.

	==== Self-Modifying RASP programs ====		==== Self-Modifying RASP programs ====

Cedar101: /* Informal definition: random-access stored-program model (RASP) */

2021-05-04T13:54:14Z

Informal definition: random-access stored-program model (RASP)

Show changes

← Previous revision		Revision as of 06:54, 25 May 2021
Line 63:		Line 63:
	To ease the example we will equip the ''state machine'' of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions:		To ease the example we will equip the ''state machine'' of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions:
	:RAM state machine instructions:		:RAM state machine instructions:
	::{ INC h; DEC h; JZ h,xxx; CPY ~~⟪h~~{{sub\|a}}~~⟫~~,{{angbr\|h{{sub\|a}}}}; CPY {{angbr\|h{{sub\|a}}}},~~⟪h~~{{sub\|a}}~~⟫~~ }		::{ INC h; DEC h; JZ h,xxx; CPY ⟪h{{sub\|a}}⟫,{{angbr\|h{{sub\|a}}}}; CPY {{angbr\|h{{sub\|a}}}},⟪h{{sub\|a}}⟫ }

	As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" {{--}} converts to action {{--}} the program:		As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" {{--}} converts to action {{--}} the program:
Line 227:		Line 227:

	The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:		The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:
	* copy indirect from i and direct to j: CPY ~~⟪h~~{{sub\|i}}~~⟫~~,{{angbr\|h{{sub\|j}}}}		* copy indirect from i and direct to j: CPY ⟪h{{sub\|i}}⟫,{{angbr\|h{{sub\|j}}}}
	* copy direct from i and indirect to j: CPY {{angbr\|h{{sub\|i}}}},~~⟪h~~{{sub\|j}}~~⟫~~		* copy direct from i and indirect to j: CPY {{angbr\|h{{sub\|i}}}},⟪h{{sub\|j}}⟫

	The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the column labelled "State machine instruction ↓". Observe that at the end of the fetch, register #2 contains the numerical value 3 of the "operation code" ("opcode") of the first instruction '''JZ''':		The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the column labelled "State machine instruction ↓". Observe that at the end of the fetch, register #2 contains the numerical value 3 of the "operation code" ("opcode") of the first instruction '''JZ''':
Line 373:		Line 373:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 5 i		\|style="font-weight:bold" \| 5 i
	\|style="font-weight:bold" \| [3]		\|style="font-weight:bold" \| [3]
Line 542:		Line 542:
	!		!
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 5 i		\|style="font-weight:bold" \| 5 i
	\|style="font-weight:bold" \| [3]		\|style="font-weight:bold" \| [3]
Line 993:		Line 993:
	! 10		! 10
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 6 i		\|style="font-weight:bold" \| 6 i
	\|style="font-weight:bold" \| [18]		\|style="font-weight:bold" \| [18]
Line 1,016:		Line 1,016:
	! 11		! 11
	\| test hole:		\| test hole:
	\| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| CPY ⟪2⟫,{{angbr\|3}}
	\|style="font-weight:bold" \| 6		\|style="font-weight:bold" \| 6
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,154:		Line 1,154:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 8 i		\|style="font-weight:bold" \| 8 i
	\|style="font-weight:bold" \| [2]		\|style="font-weight:bold" \| [2]
Line 1,246:		Line 1,246:
	! 14		! 14
	\|		\|
	\| CPY ~~⟪1⟫~~,{{angbr\|1}}		\| CPY ⟪1⟫,{{angbr\|1}}
	\|style="font-weight:bold" \| [15]		\|style="font-weight:bold" \| [15]
	\|style="font-weight:bold" \| 18		\|style="font-weight:bold" \| 18
Line 1,292:		Line 1,292:
	! 1		! 1
	\| fetch_instr:		\| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 15 i		\|style="font-weight:bold" \| 15 i
	\|style="font-weight:bold" \| [0]		\|style="font-weight:bold" \| [0]
Line 1,508:		Line 1,508:
	! 16		! 16
	\|style="font-weight:bold" \| fetch_instr:		\|style="font-weight:bold" \| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 8 i		\|style="font-weight:bold" \| 8 i
	\|style="font-weight:bold" \| [2]		\|style="font-weight:bold" \| [2]
Line 1,669:		Line 1,669:
	! 23		! 23
	\|		\|
	\| \| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| \| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 9 i		\|style="font-weight:bold" \| 9 i
	\|style="font-weight:bold" \| 18		\|style="font-weight:bold" \| 18
Line 1,692:		Line 1,692:
	! 24		! 24
	\|		\|
	\| \| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| \| CPY ⟪2⟫,{{angbr\|3}}
	\|style="color:#808080" \| 9		\|style="color:#808080" \| 9
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,761:		Line 1,761:
	! 27		! 27
	\|		\|
	\| \| CPY {{angbr\|3}},~~⟪2⟫~~		\| \| CPY {{angbr\|3}},⟪2⟫
	\|style="color:#808080" \| 9		\|style="color:#808080" \| 9
	\|style="font-weight:bold" \| 18 i		\|style="font-weight:bold" \| 18 i
Line 1,853:		Line 1,853:
	! 30		! 30
	\|style="font-weight:bold" \| fetch_instr:		\|style="font-weight:bold" \| fetch_instr:
	\| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 10 i		\|style="font-weight:bold" \| 10 i
	\|style="font-weight:bold" \| 1		\|style="font-weight:bold" \| 1
Line 1,968:		Line 1,968:
	! 35		! 35
	\|		\|
	\| \| CPY ~~⟪1⟫~~,{{angbr\|2}}		\| \| CPY ⟪1⟫,{{angbr\|2}}
	\|style="font-weight:bold" \| 11 i		\|style="font-weight:bold" \| 11 i
	\|style="font-weight:bold" \| 19		\|style="font-weight:bold" \| 19
Line 1,991:		Line 1,991:
	! 36		! 36
	\|		\|
	\| \| CPY ~~⟪2⟫~~,{{angbr\|3}}		\| \| CPY ⟪2⟫,{{angbr\|3}}
	\|style="color:#808080" \| 11		\|style="color:#808080" \| 11
	\|style="font-weight:bold" \| 19 i		\|style="font-weight:bold" \| 19 i
Line 2,037:		Line 2,037:
	! 38		! 38
	\|		\|
	\| \| CPY {{angbr\|3}},~~⟪2⟫~~		\| \| CPY {{angbr\|3}},⟪2⟫
	\|style="color:#808080" \| 11		\|style="color:#808080" \| 11
	\|style="font-weight:bold" \| 19 i		\|style="font-weight:bold" \| 19 i
Line 2,128:		Line 2,128:
	\|}		\|}

	'''Alternate instructions''': Although the demonstration resulted in a primitive RASP of only four instructions, the reader might imagine how an additional instruction such as "ADD {{angbr\|h}}" or "MULT {{angbr\|h{{sub\|a}}}},~~⟪h~~{{sub\|b}}>might be done.		'''Alternate instructions''': Although the demonstration resulted in a primitive RASP of only four instructions, the reader might imagine how an additional instruction such as "ADD {{angbr\|h}}" or "MULT {{angbr\|h{{sub\|a}}}},⟪h{{sub\|b}}>might be done.

	==== Self-Modifying RASP programs ====		==== Self-Modifying RASP programs ====

← Previous revision		Revision as of 13:29, 17 June 2023
Line 1:		Line 1:
	{{more footnotes\|date=November 2018}}		{{more footnotes needed\|date=November 2018}}
	In [[theoretical computer science]] the '''random-access stored-program''' (RASP) machine model is an [[abstract machine]] used for the purposes of [[algorithm]] development and [[Algorithmic complexity theory\|algorithm complexity theory]].		In [[theoretical computer science]] the '''random-access stored-program''' (RASP) machine model is an [[abstract machine]] used for the purposes of [[algorithm]] development and [[Algorithmic complexity theory\|algorithm complexity theory]].

Line 2,213:		Line 2,213:
	* [[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 two recursion models.		* [[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 two recursion models.
	* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp. 92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. {{ISBN\|0-07-004357-4}} .		* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp. 92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', McGraw-Hill Book Company, New York. {{ISBN\|0-07-004357-4}} .
	* [[Stephen Cook\|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), ~~354-375~~.		* [[Stephen Cook\|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354–375.
	* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.		* [[Martin Davis (mathematician)\|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
	* [[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. 365–399.		* [[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. 365–399.
	* [[Juris Hartmanis \| J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.		* [[Juris Hartmanis\|J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
	* [[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. {{ISBN\|0-201-02988-X}}. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.		* [[John Hopcroft]], [[Jeffrey Ullman]] (1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. {{ISBN\|0-201-02988-X}}. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
	* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. {{ISBN\|0-7204-2103-9}}.		* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. {{ISBN\|0-7204-2103-9}}.
	* [[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."		* [[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."
	* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages ~~295-302~~. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.		* [[Joachim Lambek]] (1961, received 15 June 1961), ''How to Program an Infinite Abacus'', Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.
	* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', [[Canadian Mathematical Bulletin]], vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. [[Richard Hamming \| R. Hamming]], [[Douglas McIlroy \| D. McIlroy]] and [[Victor A. Vyssotsky \| V. Vyssotsky]] of the [[Bell Labs \| Bell telephone Laboratories]] and with Dr. [[Hao Wang (academic) \| H. Wang]] of [[University of Oxford \| Oxford University]]		* [[Z. A. Melzak]] (1961, received 15 May 1961), ''An informal Arithmetical Approach to Computability and Computation'', [[Canadian Mathematical Bulletin]], vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. [[Richard Hamming\|R. Hamming]], [[Douglas McIlroy\|D. McIlroy]] and [[Victor A. Vyssotsky\|V. Vyssotsky]] of the [[Bell Labs\|Bell telephone Laboratories]] and with Dr. [[Hao Wang (academic)\|H. Wang]] of [[University of Oxford\|Oxford University]]
	*{{cite journal\|author=[[Marvin Minsky]]		*{{cite journal\|author=[[Marvin Minsky]]
	\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines		\|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines
Line 2,239:		Line 2,239:
	* [[Peter van Emde Boas]], ''Machine Models and Simulations'' pp. 3–66, appearing 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.		* [[Peter van Emde Boas]], ''Machine Models and Simulations'' pp. 3–66, appearing 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. 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.		:van Emde Boas' treatment of SMMs appears on pp. 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.
	* [[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, June 23–25, 1954.		* [[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, June 23–25, 1954.

	[[Category:Register machines]]		[[Category:Register machines]]