Meta tags:

Headings (most frequently used words):

rasp, phase, program, random, access, stored, of, execute, machine, contents, informal, definition, model, instruction, set, cook, and, reckhow, 1973, references, an, example, ram, working, as, fetch, parse, jz_routine, inc, dec, self, modifying, programs,

Text of the page (most frequently used words):
the (230), #machine (68), #program (58), and (57), register (39), state (37), rasp (36), instruction (32), inc (27), instructions (26), dec (23), with (19), cpy (19), random (18), access (18), contents (18), ram (17), jump (17), for (16), this (14), empty (14), model (14), halt (14), fetch (14), edit (13), hole (13), phase (13), machines (12), turing (12), their (12), its (12), from (11), two (11), has (11), into (11), copy (11), that (11), fetch_instr (11), will (11), stored (10), 1961 (10), registers (10), then (10), models (9), etc (9), are (9), number (9), set (9), indirect (9), can (9), example (9), use (8), description (8), accumulator (8), test (8), decrement (8), would (8), wikipedia (7), references (7), computer (7), finite (7), parse (7), execute (7), jz_routine (7), table (6), theory (6), but (6), computability (6), 1971 (6), address (6), inc_routine (6), parameters (6), add (5), languages (5), code (5), page (5), computing (5), both (5), isbn (5), chapter (5), computation (5), reckhow (5), cook (5), article (5), have (5), input (5), following (5), operand (5), tape (5), unlike (5), dec_routine (5), encoded (5), pointed (5), move (5), utm (5), search (4), text (4), citations (4), journal (4), association (4), van (4), science (4), complexity (4), vol (4), john (4), universal (4), pages (4), informal (4), definition (4), how (4), second (4), 1973 (4), new (4), same (4), xxx (4), operation (4), unbounded (4), self (4), such (4), indirectly (4), now (4), pir (4), zero (4), there (4), what (4), first (4), action (4), them (4), hide (4), sidebar (4), toggle (3), view (3), may (3), was (3), all (3), articles (3), short (3), machinery (3), emde (3), boas (3), treatment (3), schōnhage (3), 1980 (3), 1990 (3), theoretical (3), modification (3), 1958 (3), received (3), similar (3), systems (3), one (3), simple (3), infinite (3), other (3), melzak (3), mathematical (3), introduction (3), abacus (3), where (3), abstract (3), company (3), stephen (3), book (3), jeffrey (3), hartmanis (3), von (3), neumann (3), boolos (3), been (3), extensively (3), together (3), these (3), any (3), read (3), constant (3), capacity (3), counter (3), uses (3), modifying (3), called (3), routine (3), order (3), given (3), when (3), must (3), back (3), proceeds (3), not (3), point (3), were (3), after (3), expects (3), find (3), actions (3), phases (3), sets (3), data (3), usually (3), tools (3), main (3), contact (2), about (2), privacy (2), policy (2), available (2), additional (2), terms (2), last (2), august (2), lacking (2), november (2), 2018 (2), wikidata (2), jacm (2), presented (2), june (2), 1954 (2), wang (2), press (2), volume (2), algorithms (2), mathematics (2), shows (2), his (2), 1979 (2), storage (2), und (2), english (2), 1959 (2), reference (2), paper (2), appendix (2), cite (2), used (2), recursive (2), particular (2), defines (2), very (2), computers (2), 1st (2), marvin (2), minsky (2), unsolvability (2), 1970290 (2), september (2), university (2), bell (2), bulletin (2), approach (2), lambek (2), kleene (2), 1952 (2), metamathematics (2), edition (2), addison (2), wesley (2), reading (2), which (2), structures (2), programming (2), interpretation (2), 1964 (2), mcgraw (2), hill (2), york (2), robert (2), time (2), 1946 (2), discussion (2), goldstine (2), cambridge (2), original (2), burgess (2), more (2), still (2), over (2), few (2), those (2), integer (2), output (2), print (2), next (2), else (2), subtract (2), sub (2), put (2), mnemonic (2), they (2), modify (2), itself (2), parameter (2), word (2), described (2), here (2), version (2), subroutine (2), return_address (2), makes (2), notion (2), programs (2), demonstration (2), primitive (2), four (2), reader (2), might (2), without (2), get (2), spare (2), completes (2), thus (2), step (2), unconditionally (2), fetches (2), jumps (2), moves (2), contains (2), indeed (2), sequence (2), during (2), column (2), observe (2), end (2), value (2), direct (2), while (2), directly (2), keep (2), place (2), own (2), major (2), precise (2), interprets (2), list (2), drawn (2), none (2), increment (2), working (2), holes (2), sequential (2), interpret (2), tuples (2), numbers (2), right (2), common (2), parallel (2), architecture (2), algorithm (2), learn (2), help (2), general (2), appearance (2), upload (2), file (2), changes (2), links (2), history (2), log (2), create (2), account (2), donate (2), menu (2), topic, mobile, cookie, statement, statistics, developers, conduct, legal, safety, contacts, disclaimers, under, apply, using, site, you, agree, registered, trademark, non, profit, organization, wikimedia, foundation, creative, commons, attribution, sharealike, license, rendered, parsoid, edited, 2026, utc, hidden, categories, category, retrieved, https, org, index, php, title, access_stored, program_machine, oldid, 1369408093, 1957, meeting, variant, hao, smms, appears, clarifies, closely, follows, expands, slightly, needed, effective, understanding, appearing, mit, elsevier, h279, 444, 88071, handbook, jan, leeuwen, simulations, peter, society, industrial, applied, siam, comput, wherein, equivalence, smm, successor, resp, arnold, schönhage, hermes, hans, math, phys, semsterberichte, göttingen, die, universalität, programmgesteuerter, rechenmaschinen, dialectica, 373, graphschemata, rekursive, funktionen, péter, rózsa, russian, dok, akad, nauk, 122, 967, 970, translation, automat, express, operator, ershov, kaphengst, heinz, zeitschrift, fur, mathematische, logik, grundlagen, der, mathematik, 366, 379, eine, abstrakte, programmgesteuerte, rechenmaschine, december, 217, 255, 1963, extremely, valuable, authors, others, minimality, comparison, functions, sturgis, shepherdson, see, former, later, discusses, bases, digital, 1967, englewood, cliffs, prentice, hall, 165449, post, problem, tag, topics, 455, jstor, 2307, doi, 437, annals, 279, 293, offers, acknowledges, benefit, conversations, drs, oxford, telephone, laboratories, vyssotsky, mcilroy, hamming, canadian, arithmetical, 295, 302, proposes, formal, joachim, 1968, massachusetts, 462, 463, kind, automaton, deals, linked, art, donald, knuth, north, holland, publishing, amsterdam, netherlands, 7204, 2103, mass, difficult, centered, around, issues, completeness, 201, 02988, automata, ullman, hopcroft, computational, 232, 245, october, 365, 399, abraham, robinson, calvin, elgot, martin, davis, 1972, 354, 375, bounded, reprinted, 92ff, 004357, readings, examples, allen, newell, gordon, preliminary, logical, design, electronic, instrument, herman, arthur, burks, 2002, england, revised, advanced, than, introductory, textbook, developed, three, treated, compared, tuple, form, recursion, logic, fourth, richard, george, often, copied, exceptions, stop, hlt, pri, bpa, branch, positive, sto, store, lod, load, likewise, salient, feature, provision, achieve, requiring, necessary, designed, each, consecutive, either, purpose, compare, execution, times, various, multi, analysis, influential, define, tables, calling, perhaps, stores, command, jmp, return, subroutines, ability, possible, need, substitute, means, results, introduced, governing, different, early, found, acting, something, gained, frozen, unmodifiable, comment, does, 239ff, although, resulted, only, imagine, mult, done, alternate, inci, deci, send, target, impersonate, no_jump, points, holds, goes, skip, simply, increments, twice, analogous, tested, eventualities, knows, jumped, operands, successful, before, represent, third, causes, unexpected, detected, error, could, until, happens, operations, listed, labelled, numerical, opcode, above, detour, show, life, much, easier, kinds, copys, task, getting, bit, arduous, incrementing, restore, sacrificed, sacrificing, count, upon, start, adopts, role, listing, private, tradition, divides, below, within, agreed, convention, every, require, exactly, doing, containing, exclamation, mark, converts, ease, equip, augmented, destination, source, repeat, loop, simulate, unconditional, erasing, process, interpreter, confusion, mimics, construction, places, manner, unless, conditional, sends, elsewhere, remember, well, formed, written, string, hence, universality, classical, imaginable, convert, desired, along, printed, eventually, intermingled, replacing, user, position, head, placed, specified, format, appropriate, built, chassis, nutshell, distinguish, pointer, closest, actual, greatly, reduced, even, processors, simplest, arithmetic, some, extra, risc, cisc, whether, specific, whereas, harvard, purposes, development, includes, remove, message, please, introducing, improve, lacks, sufficient, corresponding, inline, free, encyclopedia, item, projects, printable, download, pdf, export, switch, legacy, parser, shortened, url, information, permanent, link, related, talk, italiano, فارسی, subsection, top, personal, special, recent, community, portal, contribute, current, events, navigation, content,

Text of the page (random words):
of the first instruction jz pc pir hole 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 program parameters 5 jz 18 15 dec 18 inc 19 jz 15 5 h n encoded program 5 3 18 15 2 18 1 19 3 15 5 0 n step state machine instructions 1 fetch_instr cpy 1 2 5 i 3 3 18 15 2 18 1 19 3 15 5 0 n parse phase edit now that the number of the program instruction e g 3 jz is in register 2 the program instruction register pir the state machine proceeds to decrement the number until the ir is empty if the ir were empty before decrement then the program instruction would be 0 halt and the machine would jump to its halt routine after the first decrement if the hole were empty the instruction would be inc and the machine would jump to instruction inc_routine after the second decrement the empty ir would represent dec and the machine would jump to the dec_routine after the third decrement the ir is indeed empty and this causes a jump to the jz_routine routine if an unexpected number were still in the ir then the machine would have detected an error and could halt for example pc ir hole 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 program parameters 5 jz 18 15 dec 18 inc 19 jz 15 5 h n encoded program 5 3 18 15 2 18 1 19 3 15 5 0 n state machine instructions cpy 1 2 5 i 3 3 18 15 2 18 1 19 3 15 5 0 n jz 2 halt 5 3 3 18 15 2 18 1 19 3 19 5 0 n 3 dec 2 5 2 3 18 15 2 18 1 19 3 15 5 0 n 4 jz 2 inc_routine 5 2 3 18 15 2 18 1 19 3 15 5 0 n 5 dec 2 5 1 3 18 15 2 18 1 19 3 15 5 0 n 6 jz 2 dec_routine 5 1 3 18 15 2 18 1 19 3 15 5 0 n 7 dec 2 5 0 3 18 15 2 18 1 19 3 15 5 0 n 8 jz 2 jz_routine 5 0 halt halt 5 3 3 18 15 2 18 1 19 3 15 5 0 n inc_routine etc 5 3 3 18 15 2 18 1 19 3 15 5 0 n dec_routine etc 5 3 3 18 15 2 18 1 19 3 15 5 0 n 9 jz_routine etc 5 3 3 18 15 2 18 1 19 3 15 5 0 n execute phase jz_routine edit now the state machine knows what program instruction to execute indeed it has jumped to the jz_routine sequence of instructions the jz instruction has 2 operands i the number of the register to test and ii the address to go to if the test is successful the hole is empty i operand fetch which register to test for empty analogous to the fetch phase the finite state machine moves the contents of the register pointed to by the pc i e hole 6 into the program instruction register pir 2 it then uses the contents of register 2 to point to the register to be tested for zero i e register 18 hole 18 contains a number n to do the test now the state machine uses the contents of the pir to indirectly copy the contents of register 18 into a spare register 3 so there are two eventualities ia register 18 is empty ib register 18 is not empty ia if register 3 is empty then the state machine jumps to ii second operand fetch fetch the jump to address ib if register 3 is not empty then the state machine can skip ii second operand fetch it simply increments twice the pc and then unconditionally jumps back to the instruction fetch phase where it fetches program instruction 8 dec ii operand fetch jump to address if register 3 is empty the state machine proceeds to use the pc to indirectly copy the contents of the register it points to 8 into itself now the pc holds the jump to address 15 then the state machine unconditionally goes back to the instruction fetch phase where it fetches program instruction 15 halt pc ir hole 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 program parameters 5 jz 18 15 dec 18 inc 19 jz 15 5 h n encoded program 5 3 18 15 2 18 1 19 3 15 5 0 n step state machine instructions 9 jz_routine inc 1 6 3 3 18 15 2 18 1 19 3 15 5 0 n 10 cpy 1 2 6 i 18 3 18 15 2 18 1 19 3 15 5 0 n 11 test hole cpy 2 3 6 18 i n 3 18 15 2 18 1 19 3 15 5 0 n 12 test hole jz 3 jump 6 18 i n 3 18 15 2 18 1 19 3 15 5 0 n n n 13 no_jump inc 1 7 18 n 3 18 15 2 18 1 19 3 15 5 0 n 14 inc 1 8 18 n 3 18 15 2 18 1 19 3 15 5 0 n 15 j fetch_instr 8 18 n 3 18 15 2 18 1 19 3 15 5 0 n 1 fetch_instr cpy 1 2 8 i 2 n 3 18 15 2 18 1 19 3 15 5 0 n 2 parse etc 13 jump inc 1 7 18 n 3 18 15 2 18 1 19 3 15 5 0 n 14 cpy 1 1 15 18 n 3 18 15 2 18 1 19 3 15 5 0 n 15 j fetch_instr 15 18 n 3 18 15 2 18 1 19 3 15 5 0 n 1 fetch_instr cpy 1 2 15 i 0 n 3 18 15 2 18 1 19 3 15 5 0 n 2 parse etc execute phase inc dec edit the following completes the ram s state machine interpretation of program instructions inc h dec h and thus completes the demonstration of how a ram can impersonate a rasp target program instruction set inc h dec h jz h xxx halt without indirect state machine instructions inci and deci to execute the inc and dec program instructions the state machine must use indirect copy to get the contents of the pointed to register into spare register 3 dec or inc it and then use indirect copy to send it back to the pointed to register pc ir hole 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 program parameters 5 jz 18 15 dec 18 inc 19 jz 15 5 h n encoded program 5 3 18 15 2 18 1 19 3 15 5 0 n state machine instructions 15 j fetch_instr 8 18 n 3 18 15 2 18 1 19 3 15 5 0 n 16 fetch_instr cpy 1 2 8 i 2 n 3 18 15 2 18 1 19 3 15 5 0 n 17 parse jz 2 halt 8 2 n 3 18 15 2 18 1 19 3 15 5 0 n 18 dec 2 8 1 n 3 18 15 2 18 1 19 3 15 5 0 n 19 jz 2 inc_routine 8 1 n 3 18 15 2 18 1 19 3 15 5 0 n 20 dec 2 8 0 n 3 18 15 2 18 1 19 3 15 5 0 n 21 jz 2 dec_routine 8 0 n 3 18 15 2 18 1 19 3 15 5 0 n 22 dec_routine inc 1 9 0 n 3 18 15 2 18 1 19 3 15 5 0 n 23 cpy 1 2 9 i 18 n 3 18 15 2 18 1 19 3 15 5 0 n 24 cpy 2 3 9 18 i n 3 18 15 2 18 1 19 3 15 5 0 n 25 jz 3 2 9 18 n 3 18 15 2 18 1 19 3 15 5 0 n 26 dec 3 9 18 n 1 3 18 15 2 18 1 19 3 15 5 0 n 27 cpy 3 2 9 18 i n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 28 inc 1 10 18 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 29 j fetch_instr 10 18 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 30 fetch_instr cpy 1 2 10 i 1 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 31 parse jz 2 halt 10 1 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 32 dec 2 10 0 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 33 jz 2 inc_routine 10 0 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 34 inc_routine inc 1 11 0 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 35 cpy 1 2 11 i 19 n 1 3 18 15 2 18 1 19 3 15 5 0 n 1 36 cpy 2 3 11 19 i 0 3 18 15 2 18 1 19 3 15 5 0 n 1 0 37 inc 3 11 19 1 3 18 15 2 18 1 19 3 15 5 0 n 1 0 38 cpy 3 2 11 19 i 1 3 18 15 2 18 1 19 3 15 5 0 n 1 1 39 inc 1 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n 1 0 40 j fetch_instr 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n 1 0 41 fetch_instr etc 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n 1 0 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 h or mult h a h b might be done self modifying rasp programs edit when a ram is acting as a rasp something new has been gained unlike the ram the rasp has the capacity for self modification of its program instructions the state machine instructions are frozen unmodifiable by the machine cook reckhow 1971 p 75 comment on this in their description of their rasp model as does hartmanis 1971 pp 239ff an early description of this notion can be found in goldstine von neumann 1946 we need an order instruction that can substitute a number into a given order by means of such an order the results of a computation can be introduced into the instructions governing that or a different computation p 93 such an ability makes the following possible subroutines the calling routine or perhaps the subroutine stores the return address return_address in the subroutine s last command i e jmp return_address so called jump tables self modifying code rasp program instruction set of cook and reckhow 1973 edit in an influential paper stephen a cook and robert a reckhow define their version of a rasp the random access stored program machine rasp described here is similar to the rasp s described by hartmanis 1971 p 74 their purpose was to compare execution times of the various models ram rasp and multi tape turing machine for use in the theory of complexity analysis the salient feature of their rasp model is no provision for indirect program instructions cf their discussion p 75 this they achieve by requiring the program to modify itself if necessary an instruction can modify the parameter their word i e operand of a particular instruction they have designed their model so each instruction uses two consecutive registers one for the operation code their word and the parameter either an address or an integer constant their rasp s registers are unbounded in capacity and unbounded in number likewise their accumulator ac and instruction counter ic are unbounded the instruction set is the following operation mnemonic operation code description load constant lod k 1 put constant k into accumulator add add j 2 add contents of register j to accumulator subtract sub j 3 subtract contents of register j from accumulator store sto j 4 copy contents of accumulator into register j branch on positive accumulator bpa xxx 5 if contents of accumulator 0 then jump to xxx else next instruction read rd j 6 next input into register j print pri j 7 output contents of register j halt hlt any other or integer stop references edit 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 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 stephen a cook and robert a reckhow 1972 time bounded random access machines journal of computer systems science 7 1973 354 375 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 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 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 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 vyssotsky of the bell telephone laboratories and with dr h wang of oxford university marvin minsky 1961 recursive unsolvability of post s problem of tag and other topics in theory of turing machines annals of mathematics 74 3 437 455 doi 10 2307 1970290 jstor 1970290 marvin minsky 1967 computation finite and infinite machines 1st ed englewood cliffs n j prentice hall inc 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 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 ershov a p on operator algorithms russian dok akad nauk 122 1958 967 970 english translation automat express 1 1959 20 23 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 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 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 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 retrieved from https en wikipedia org w index php title random access_stored program_machine oldid 1369408093 category register machines hidden categories articles with short description short description with empty wikidata description articles lacking in text citations from november 2018 all articles lacking in text citations this page was last edited on 14 august 2026 at 20 04 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mob...