1442:: This, their "most flexible machine... consists of a denumerable sequence of registers numbered 1, 2, 3, ..., each of which can store any natural number...Each particular program, however involves only a finite number of these registers" (p. 219). In other words, the number of registers is potentially infinite, and each register's "size" is infinite.
1306:
They use Lambek's name "abacus" but follow Melzak's pebble-in-holes model, modified by them to a 'stones-in-boxes' model. Like the original abacus model of Lambek, their model retains the Minsky (1961) use of non-sequential instructions – unlike the "conventional" computer-like default
1938:
can be computed by a program computer using only operations , , if we permit a RPT operation to lie in its own range ... in general a RPT operation could not be an instruction in the finite-state part of the machine... this might exhaust any particular amount of storage allowed in the finite part
103:
The machine contains "a mill" (accumulator). Kaphengst designates his mill/accumulator with the "infinity" symbol but we will use "A" in the following description. It also contains an "order register" ("order" as in "instruction", not as in "sequence"). (This usage came from the Burks–Goldstine–von
845:
If we use the context of his model, "keeping tally" means "adding by successive increments" (throwing a pebbles into) or "subtracting by successive decrements"; transferring means moving (not copying) the contents from hole A to hole B, and comparing numbers is self-evident. This appears to be a
104:
Neumann (1946) report's description of "...an
Electronic Computing Instrument".) The order/instruction register is register "0". And, although not clear from Sheperdson and Sturgis's exposition, the model contains an "extension register" designated by Kaphengst "infinity-prime"; we will use "E".
1302:
The various editions beginning with 1970 the authors use the Lambek (1961) model of an "infinite abacus". This series of
Knowledge articles is using their symbolism, e.g. " +1 → r" "the contents of register identified as number 'r', plus 1, replaces the contents of register number 'r' ".
861:: S, A1, A2, ..., an indefinitely large supply of counters distributed among these locations, a program, and an operator whose sole purpose is to carry out the instructions. Initially all but a finite number from among the locations ... are empty and each of the remaining ones contains a
841:"It is our object to describe a primitive device, to be called a Q-machine, which arrives at effective computability via arithmetic rather than via logic. Its three operations are keeping tally, comparing non-negative integers, and transferring" (Melzak (1961) p. 281)
1314:
Observe, however, that B-B and B-B-J do not use a variable "X" in the mnemonics with a specifying parameter (as shown in the Lambek version) --i.e. "X+" and "X-" – but rather the instruction mnemonics specifies the registers themselves, e.g. "2+", or "3-":
1660:
and thereby allow only writing to the end of the string and erasing from the beginning. This is shown in their Figure 1 as a tape with a read head on the left and a write head on the right, and it can only move the tape right. "A" is their "word" (p. 229):
1172:
The conditional "jump" occurs on every instance of XYZ type because: if it cannot be performed because X does not have enough counters/pebbles then the jump occurs; otherwise if it can be performed it will be and the instructions continue to the next in
77:"Kaphengst's approach is interesting in that it gives a direct proof of the universality of present-day digital computers, at least when idealized to the extent of admitting an infinity of storage registers each capable of storing arbitrarily long words"
2432:, 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."
2017:
first supplies the register-address and then secondly, receives the datum from the register – a form of indirect "load". The second peculiarity is the specification of the COMPARE operation. This is a "jump if accumulator-register
1646:: Here they restrict the machine to a finite number of registers N, but they also allow more registers to "be brought in" or removed if empty (cf. p. 228). They show that the remove-register instruction need not require an empty register.
1217:
Lambek references Melzak's paper. He atomizes Melzak's single 3-parameter operation (really 4 if we count the instruction addresses) into a 2-parameter increment "X+" and 3-parameter decrement "X-". He also provides both an informal and
1201:
Is Melzak's assertion true? – that this model is "so simple that its working could probably be understood by an average school-child after a few minutes's explanation" (p. 282)? The reader will have to
1698:"Many other combinations of operation types , , , , and form universal basis. Find some of these basis. Which combinations of three operations are not universal basis? Invent some other operations..." (p. 214)
2034:). Apparently if the test fails the machine skips over the next instruction which always must be in the form of "goto λ" where "λ" is the jump-to address. The instruction – "compare contents of
2611:
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
1964:
The way Schönhage did this is of interest. He (i) atomizes the conventional register "address:datum" into its two parts: "address", and "datum", and (ii) generates the "address" in a specific register
1406:
In
Section 10 we show that theorems (including Minsky's results ) on the computation of partial recursive functions by one or two tapes can be obtained rather easily from one of our intermediate forms.
2564:, 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.
2570:, May 1972, "A Two counter Machine Cannot Calculate 2", Massachusetts Institute of Technology, A. I. Laboratory, Artificial Intelligence Memo #257. The author references Minsky 1967 and notes that "
1571:
This set of instructions is chosen for ease of programming the computation of partial recursive functions rather than economy; it is shown in
Section 4 that this set is equivalent to a smaller set.
73:"the proof of this universality ... seems to have been first written down by Hermes, who showed in how an idealized computer could be programmed to duplicate the behavior of any Turing machine"
511:
observe that PĂ©ter's "treatment" (they are not too specific here) has an equivalence to the instructions shown in the following table. They comment specifically about these instructions, that:
2191:
While peculiar, Schönhage's model shows how the conventional counter-machine's "register-to-register" or "read-modify-write" instruction set can be atomized to its simplest 0-parameter form.
2188: – a counter machine with indirect addressing; instruction "N" allows for indirect storage of the accumulator, and instruction "L" allows for indirect load of the accumulator.
2414:, 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)
1918:
He proceeds to show how to replace the "successor-predecessor" set { , , } with the "successor-equality" set { , , }. And then he defines his "REPEAT" and shows that we can define any
1577:
In instructions a, b, c, d the contents of all registers except n are supposed to be left unchanged; in instructions e, f, the contents of all registers are unchanged (p. 219).
2404:, 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."
2295:
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
1960:"...the RAM0 version deserves special attention for its extreme simplicity; its instruction set consists of only a few one-letter codes, without any (explicit) addressing" (p. 494)
2515:
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".
2489:. 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.
241:
remove the mill/accumulator A and reduce the
Kaphengst instructions to register-to-register "copy", arithmetic operation "increment", and "register-to-register compare".
1956:) model with a remarkable instruction set requiring no operands at all, excepting, perhaps, the "conditional jump" (and even that could be achieved without an operand):
1191:
2049:
Primarily for reference – this is a RAM model, not a counter-machine model – the following is the Schönhage RAM0 instruction set:
1183:) and gives two examples of its use. But he does not pursue this further. This is the first verified instance of "indirection" to appear in the literature.
1435:...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested and started by Wang.
1948:
Schönhage (1980) developed his computational model in context of a "new" model he called the
Storage Machine Modification model (SMM), his variety of
2299:; 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.
628:"an interesting basis for recursive function theory involving programs of only the simplest arithmetic operations" (Minsky (1961) p. 437).
2042:" is unlike the Schonhage successor-RAM1 model (or any other known successor-models) with the more conventional "compare contents of register
2288:
1968:
to which the finite-state machine instructions (i.e. the "machine code") would have access, and (iii) provides an "accumulator" register
1889:
But he admits the model is easier if he adds some -instructions (combined and ) and "go(n)". He builds "go(n)" out of the register
2624:, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.
2603:
832:
to process "the integer S". He asserts that the first machine/model does not need to do this if it has 4 registers available to it.
1767:
IF contents of register r not zero decrement contents of register r and jump to zth instruction, else if 0 then next instruction
1581:
Indeed, they show how to reduce this set further, to the following (for an infinite number of registers each of infinite size):
1169:
If all the holes start with 0, then how do we increment? Apparently this is not possible; one hole must contain a single pebble.
849:
Melzak's physical model is holes { X, Y, Z, etc. } in the ground together with an unlimited supply of pebbles in a special hole
1900:
In his section 11.5 "The equivalence of
Program Machines with General-recursive functions" he introduces two new subroutines:
2637:
2429:
2323:
1922:
by the "successor-repeat" set { , , } (where the range of the cannot include itself. If it does, we get what is called the
366:
observe that Ersov's model allows for storage of the program in the registers. They assert that Ersov's model is as follows:
1754:
Test register r and jump to instruction z if contents is zero; if not, decrement (subtract 1 from) contents of register r
1919:
1975:
In his particular RAM0 model has only two "arithmetic operations" – "Z" for "set contents of register
100:
Kaphengst's paper is written in German; Sheperdson and
Sturgis's translation uses terms such as "mill" and "orders".
1886:
already "empty" (Minsky (1967) p. 206). Later (pages 255ff) he compresses the three { , , }, into two { , }.
1675:
They also provide a model as "a stack of cards" with the symbols { 0, 1 } (p. 232 and Appendix C p. 248):
111:"...so the machine, like an actual computer, is capable of doing arithmetic operations on its own program" (p. 244).
2315:
2280:
1935:
1694:
Ultimately, in Problem 11.7-1 Minsky observes that many bases of computation can be formed from a tiny collection:
516:
2133:
Indirectly store the contents of accumulator z into the register pointed to by the contents of address-register n
1222:
definition of "a program". This form is virtually identical to the Minsky (1961) model, and has been adopted by
97:
The rest of the operations are transfers from register-to-accumulator or accumulator-to-register or test-jumps.
599:
1428:
1198:
received a month later on 15 June 1961 – are contained in the same volume, one after the other.
2306:
2439:(1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines".
2391:
724:"...represents any partial recursive function by a program operating on one integer S using instructions I
2387:
1399:
1187:
1953:
1927:
1180:
116:
2535:, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
632:
His "Theorem Ia" asserts that any partial recursive function is represented by "a program operating on
617:
1807:
Do until contents of register = 0: Repeat instructions m thru n. When = 0, go to next instruction.
621:
1939:
of the machine. RPT operations require infinite registers of their own, in general... etc." (p. 214)
600:
1961: Minsky's model of a partial recursive function reduced to a "program" of only two instructions
2617:
2577:
2350:
1420:
52:
2421:
2497:
2456:
2378:
2342:
1574:
There are infinitely many instructions in this list since m, n range over all positive integers.
2557:
245:. This model, almost verbatim, is to be found in Minsky (1967); see more in the section below.
2599:
2538:
2319:
2284:
523:
a further analysis of the copying operation is necessary along the lines we have taken above."
40:
2506:
2448:
2362:
2119:
Indirectly copy into accumulator z the contents of the register pointed to by accumulator z
1384:
if contents of register r1 is zero ELSE decrement (subtract 1 from) contents of register #1
2374:
2591:
2567:
2370:
2346:
2272:
2268:
1949:
28:
829:
2473:
2407:
1424:
1195:
636:
integers S1 and S2 using instructions Ij of the forms (cf. Minsky (1961) p. 449):
520:
48:
17:
2631:
2529:
2495:
Shepherdson, John C.; Sturgis, H. E. (1963). "Computability of Recursive Functions".
2468:
2436:
2264:
836:
1961: Melzak model: a single ternary instruction with addition and proper subtraction
613:
44:
36:
2382:
2009:
A first peculiarity of the Schönhage RAM0 is how it "loads" something into register
2397:
1874:
Minsky (1967) begins with a model that consists of the three operations plus HALT:
925:
Of all the possible operations, some are not allowed, as shown in the table below:
515:"from the point of view of proving as quickly as possible the computability of all
2574:
independently proved the non-computability using a similar method in April 1971."
1741:
Increment (add 1 to) contents of register r (apostrophe ' signifies "successor")
2571:
2547:
2394:
theorems for counter machines, analogous to the hierarchies for Turing machines.
1923:
1882:
He observes that we can dispense with if we allow for a specific register e.g.
32:
593:
Conditional jump to E1 if contents of m equals contents of n, else jump to E2.
1685:
remove bottom card; if printed 1 jump to instruction m, else next instruction.
1653:
1637:
If contents of register m ≠0 THEN jump to instruction "Exit 1" ELSE continue
710:; ELSE decrement (subtract 1 from) contents of register r and jump to instr. I
609:
2596:
Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity
1912:
Jump unless equal": IF ≠THEN jump to zth instruction ELSE next instruction
1290:
First test for zero, then decrement (subtract 1 from) contents of register r
1657:
605:
2510:
2151:
If contents of accumulator z = 0 THEN skip next instruction else continue
1558:
IF contents of register r = 0 then jump to instruction "Exit 1" else next
1176:
Neither SXY nor XXY can cause a jump because both can always be performed.
1208:
1961: Lambek "abacus" model: atomizing Melzak's model to X+, X- with test
2105:"Set address n": copy contents of accumulator z into address-register n
1689:
2460:
2366:
1035:
Count of Y's pebbles taken from X and placed in Y, doubling count of Y
2054:
1707:
1586:
1320:
1231:
529:
371:
250:
124:
2144:
If = 0 skip the next instruction (which must be a goto instruction I
1702:
The following are definitions of the various instructions he treats:
1450:
1445:
They offer the following instruction set, and the following "Notes":
1136:
Count of Y's pebbles taken from S and added to Y, doubling Y's count
218:
Clear contents of A if contents of A = contents of r, else "set" A=1
2522:, Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:
2452:
734:
641:
2206:
2204:
671:
Increment (add 1 to) contents of register r and go to instruction I
2426:
An informal Arithmetical Approach to Computability and Computation
1419:
Their model is strongly influenced by the model and the spirit of
1398:
reference Minsky (1961) as it appeared for them in the form of an
720:
The first theorem is the context of a second "Theorem IIa" that
706:
IF contents of register r equals zero THEN jump to instruction I
519:
PĂ©ter's is perhaps the best; for proving their computability by
119:. In the following, "" indicates "contents of" register r, etc.
1690:
1967: Minsky's "Simple Universal Base for a Program Computer"
2479:(1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc.
2308:
Computability: An Introduction to Recursive Function Theory
1000:
All of X's pebbles taken from X and put into sink/source S
2059:
1987:
is via a copy-from-A-to-N instruction called "set address
1843:
If ≠THEN jump to zth instruction ELSE next instruction
1714:
1711:
1594:
1591:
1458:
1455:
1327:
1324:
1238:
1235:
741:
738:
648:
645:
536:
533:
378:
375:
257:
254:
131:
2553:
Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
2155:
2137:
2123:
2109:
2095:
2081:
2067:
1751:
IF = 0 THEN jump to instruction z ELSE next instruction
2062:
1307:
sequential instruction execution, the next instruction I
128:
1979:
to zero", and "A" for "add one to contents of register
2551:
Die Universalität programmgesteuerter Rechenmaschinen.
1995:
in a given register, the machine uses the contents of
579:
Copy incremented contents of register m to register n
1804:
RPT a:. Repeat cannot operate within its own range.
899:. IF this is not possible because it will empty hole
2234:
1555:
IF = 0 THEN jump to "Exit 1" ELSE next instruction
1223:
319:
IF = 0 THEN jump to "Exit 1" ELSE next instruction
1623:Decrement (subtract 1 from) contents of register r
1487:Decrement (subtract 1 from) contents of register r
811:
If division of contents of register 1 by constant K
486:IF ≤ THEN jump to "Exit 1" ELSE jump to "Exit 2"
2622:A Variant to Turing's Theory of Computing Machines
2472:
2353:(1968), "Counter machines and counter languages",
2222:
2210:
1865:RPT a:. Repeat can operate within its own range.
1411:
1395:
1117:Count of Y's pebbles taken from X and added to Z,
508:
363:
238:
68:
2520:Eine Abstrakte programmgesteuerte Rechenmaschine'
2091:Increment the contents of accumulator-register z
1854:THEN jump to instruction z ELSE next instruction
1155:Count of Y's pebbles taken from S and added to Z
903:THEN do nothing and jump to instruction #I; ELSE,
2003:to supply the datum to be sent to the register.
1999:to specify the register's address and register
1433:
1404:
981:All of X's pebbles taken from X and added to Y
272:Increment (add 1 to) contents of accumulator A
188:Increment (add 1 to) contents of accumulator A
2030:to the contents of the register pointed to by
1972:where all arithmetic operations are to occur.
1192:William Lowell Putnam Mathematical Competition
853:(Sink or Supply or both? Melzak doesn't say).
772:Multiply contents of register r1 by constant K
160:Copy contents of accumulator A to register r
107:The instructions are stored in the registers:
1350:Increment (add 1 to) contents of register #1
1297:Abacus model of Boolos, Burgess & Jeffrey
895:attempt to remove this same number from hole
624:) led Minsky to the following definition of:
344:Clear contents of register E if contents of r
146:Copy contents of register r to accumulator A
8:
2026:(not, for example, "compare the contents of
1868:* Note: RPT must be in an infinite register
1867:
1861:
1840:
1826:
1814:
1801:
1774:
1764:If ≠0 THEN -1 → r ELSE next instruction
1761:
1748:
1735:
1722:
1671:f'. Ji ;If A begins with ai jump to exit 1.
1609:Increment (add 1 to) contents of register r
1473:Increment (add 1 to) contents of register r
1261:Increment (add 1 to) contents of register r
1194:, winner 1950) was received 15 May 1961 and
358:
1846:Conditional jump: if contents of register r
359:1958: Ershov's class of operator algorithms
2180:Again, the above instruction set is for a
2171:Unconditional goto (jump to) instruction I
2165:Unconditional goto (jump to) instruction I
2056:
1858:
1837:
1823:
1811:
1798:
1771:
1758:
1745:
1732:
1719:
1627:
1588:
1548:
1534:
1505:
1491:
1452:
1179:Melzak adds indirection to his model (see
583:
569:
565:Copy contents of register m to register n
555:
541:
531:
469:
455:
419:
383:
373:
326:
312:
276:
262:
252:
222:
208:
192:
178:
164:
150:
136:
126:
2475:Computation: Finite and Infinite Machines
2046:to contents of register a for equality".
1213:Original "abacus" model of Lambek (1962):
1207:
489:Jump to exit E1 if contents of register r
2051:
1944:1980: Schönhage's 0-parameter model RAM0
1709:
1704:
1668:b. D ;delete the first letter of A
1583:
1447:
1322:
1317:
1233:
1228:
1162:Some observations about the Melzak model
927:
736:
731:
643:
638:
526:
368:
247:
215:IF = THEN 0 → < A > ELSE 1 → A
121:
2247:
2200:
1983:". The only access to address-register
444:Copy incremented contents of register r
2542:Graphschemata und rekursive Funktionen
1943:
859:indefinitely large number of locations
493:is less than or equal to contents of r
204:Jump if contents of accumulator A = 0
1991:". To store a "datum" in accumulator
1391:1963: Shepherdson and Sturgis's model
1311:is contained within the instruction.
1226:, p. 45, Abacus Computability).
1186:Both papers – that of
873:"ternary operation" he calls "XYZ":
828:In this second form the machine uses
503:
7:
1833:Unconditional jump to instruction z
881:Count the number of pebbles in hole
2487:Very Simple Bases for Computability
2483:Models Similar to Digital Computers
2237:, p. 45, Abacus Computability.
1952:. His development described a RAM (
1850:not equal to contents of register r
1224:Boolos, Burgess & Jeffrey (2007
322:Jump if contents of register r = 0
2279:(5 ed.). Cambridge, England:
2235:Boolos, Burgess & Jeffrey 2007
1665:a. P(i) ;add ai to the end of A
243:Observe that there is no decrement
25:
2412:How to Program an Infinite Abacus
1897:, (n)) is an unconditional jump.
1652:: Here they are implementing the
1343:+ 1 → r1 then go to instruction I
1544:Unconditional jump to "Exit #1"
1396:Shepherdson & Sturgis (1963)
910:and (iv) transfer them to, i.e.
846:blend of the three base models.
800:/Kj = 0 then go to instruction I
604:In his inquiry into problems of
590:IF = jump to E1 ELSE jump to E2
509:Shepherdson & Sturgis (1963)
465:Unconditional jump to "Exit #1"
364:Shepherdson & Sturgis (1963)
239:Shepherdson & Sturgis (1963)
93:Testing two numbers for equality
69:Shepherdson & Sturgis (1963)
2598:, The MIT PRESSElsevier, 1990.
2416:Introduction to Metamathematics
2410:(1961, received 15 June 1961),
2402:The Art of Computer Programming
1412:Shepherdson & Sturgis (1963
877:"XYZ" denotes the operation of
700:ELSE -1 → r and go to instr. I
51:, Shepherdson and Sturgis, and
27:There are many variants of the
2582:Machine Models and Simulations
2481:In particular see chapter 11:
2430:Canadian Mathematical Bulletin
2424:(1961, received 15 May 1961),
2223:Shepherdson & Sturgis 1963
2211:Shepherdson & Sturgis 1963
1634:IF ≠0 THEN jump to "Exit 1"
1440:Unlimited Register Machine URM
1284:else -1 → r and go to instr. I
914:them to, the quantity in hole
857:"The Q-machine consists of an
815:has no remainder then instr. I
201:IF = 0 THEN jump to "Exit 1"
115:Thus this model is actually a
1:
2562:Storage Modification Machines
2170:
2164:
2158:
2150:
2143:
2140:
2132:
2129:
2126:
2118:
2115:
2112:
2104:
2101:
2098:
2090:
2087:
2084:
2077:Clear accumulator-register z
2076:
2073:
2070:
1864:
1845:
1842:
1832:
1829:
1819:
1816:
1806:
1803:
1786:
1776:
1766:
1763:
1753:
1750:
1740:
1737:
1727:
1724:
1636:
1633:
1630:
1612:
1598:
1557:
1554:
1551:
1543:
1540:
1537:
1522:
1511:
1508:
1500:
1497:
1494:
1476:
1462:
1353:
1331:
1264:
1242:
778:
745:
678:
652:
592:
589:
586:
578:
575:
572:
564:
561:
558:
550:
547:
544:
488:
485:
472:
464:
461:
458:
443:
433:
422:
407:
397:
386:
343:
341:IF = THEN 0 → E ELSE 1 → E
340:
329:
321:
318:
315:
300:
290:
279:
271:
268:
265:
231:
228:
225:
217:
214:
211:
203:
200:
195:
187:
184:
181:
173:
170:
167:
159:
156:
153:
145:
142:
139:
55:. These are explained below.
2606:(volume A). QA 76.H279 1990.
2584:pp. 3–66, appearing in:
2544:, Dialectica 12 (1958), 373.
1920:primitive recursive function
1644:Limited Register Machine LRM
1431:). They "sum up by saying":
1254:+ 1 → r; go to instruction I
664:+ 1 → r; go to instruction I
2355:Mathematical Systems Theory
1787:Copy contents of register r
1650:Single-Register Machine SRM
1523:Copy contents of register r
906:remove the Y-quantity from
696:If ≤ 0 THEN go to instr. I
517:partial recursive functions
408:Copy contents of register r
301:Copy contents of register r
174:Zero (clear) accumulator A
2654:
2316:Cambridge University Press
2281:Cambridge University Press
1936:general recursive function
1613:
1599:
1477:
1463:
1354:
1332:
1265:
1243:
865:" (p. 283, boldface added)
779:
746:
679:
653:
1682:add card at top printed 0
1679:add card at top printed 1
1373:else -1 → r1 and go to I
863:finite number of counters
765:→ r1; go to instruction I
504:1958: PĂ©ter's "treatment"
59:The models in more detail
1893:pre-set to 0, so that (
1728:Zero (clear) register r
1501:Zero (clear) register r
551:Zero (clear) register n
232:"Set" contents of A = 1
2305:Cutland, Nigel (1980).
2277:Computability and Logic
946:Meaning of Instruction
2533:On operator algorithms
1928:mu recursive functions
1830:Jump to instruction z
1437:
1417:
1400:MIT Lincoln Laboratory
1280:If ≤ 0, go to instr.I
31:, among them those of
18:Counter machine models
2638:Models of computation
2511:10.1145/321160.321170
2441:Annals of Mathematics
2182:random-access machine
1954:random-access machine
1390:
1380:Jump to instruction I
1369:If ≤ 0 THEN go to I
1181:random-access machine
869:The instruction is a
117:random-access machine
2351:Rosenberg, Arnold L.
2297:Abacus Computability
622:Diophantine equation
63:
2578:Peter van Emde Boas
2343:Fischer, Patrick C.
1429:Post–Turing machine
1188:Z. Alexander Melzak
888:put them back into
497:, else jump to E=2
90:Successor operation
64:1954: Hermes' model
2518:Kaphengst, Heinz,
2498:Journal of the ACM
2367:10.1007/bf01694011
1930:) (p. 213)):
618:Hilbert's problems
2290:978-0-521-87752-7
2178:
2177:
1872:
1871:
1641:
1640:
1565:
1564:
1541:Jump to "Exit 1"
1388:
1387:
1294:
1293:
1159:
1158:
826:
825:
718:
717:
616:'s 10th problem (
597:
596:
501:
500:
462:Jump to "Exit 1"
356:
355:
352:, else "set" E=1
236:
235:
86:instructions are
16:(Redirected from
2645:
2526:(1959), 366-379.
2514:
2485:and chapter 14:
2480:
2478:
2464:
2385:
2336:
2334:
2332:
2313:
2294:
2273:Jeffrey, Richard
2269:Burgess, John P.
2251:
2244:
2238:
2232:
2226:
2220:
2214:
2208:
2052:
1705:
1584:
1448:
1415:
1318:
1229:
928:
797:
732:
693:
639:
527:
483:
369:
248:
198:
122:
21:
2653:
2652:
2648:
2647:
2646:
2644:
2643:
2642:
2628:
2627:
2592:Jan van Leeuwen
2568:Rich Schroeppel
2494:
2467:
2453:10.2307/1970290
2435:
2392:space hierarchy
2341:
2330:
2328:
2326:
2311:
2304:
2291:
2263:
2260:
2255:
2254:
2245:
2241:
2233:
2229:
2221:
2217:
2209:
2202:
2197:
2174:
2168:
2162:
2147:
1950:pointer machine
1946:
1853:
1849:
1794:
1790:
1784:
1780:
1692:
1530:
1526:
1519:
1515:
1423:(1957) and his
1416:
1410:
1393:
1383:
1376:
1372:
1365:
1361:
1346:
1339:
1310:
1287:
1283:
1276:
1272:
1257:
1250:
1210:
1205:
921:
838:
822:
818:
814:
807:
803:
795:
791:
787:
783:
775:
768:
764:
757:
753:
727:
713:
709:
703:
699:
691:
687:
683:
674:
667:
660:
602:
521:Turing machines
506:
496:
492:
481:
477:
473:
451:
447:
441:
437:
430:
426:
415:
411:
405:
401:
394:
390:
361:
351:
348:= contents of r
347:
337:
333:
308:
304:
298:
294:
287:
283:
196:
66:
61:
29:counter machine
23:
22:
15:
12:
11:
5:
2651:
2649:
2641:
2640:
2630:
2629:
2626:
2625:
2614:
2613:
2612:understanding.
2609:
2608:
2607:
2586:
2585:
2575:
2565:
2554:
2545:
2536:
2527:
2516:
2505:(2): 217–255.
2491:
2490:
2465:
2447:(3): 437–455.
2433:
2419:
2408:Joachim Lambek
2405:
2395:
2388:time hierarchy
2361:(3): 265–283,
2338:
2337:
2324:
2301:
2300:
2289:
2265:Boolos, George
2259:
2256:
2253:
2252:
2239:
2227:
2225:, p. 246.
2215:
2213:, p. 219.
2199:
2198:
2196:
2193:
2176:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2153:
2152:
2149:
2145:
2142:
2139:
2135:
2134:
2131:
2128:
2125:
2121:
2120:
2117:
2114:
2111:
2107:
2106:
2103:
2100:
2097:
2093:
2092:
2089:
2086:
2083:
2079:
2078:
2075:
2072:
2069:
2065:
2064:
2061:
2058:
2055:
2007:Peculiarities:
1962:
1961:
1945:
1942:
1941:
1940:
1916:
1915:
1914:
1913:
1906:
1905:
1880:
1879:
1870:
1869:
1866:
1863:
1860:
1856:
1855:
1851:
1847:
1844:
1841:
1839:
1835:
1834:
1831:
1828:
1825:
1821:
1820:
1818:
1815:
1813:
1809:
1808:
1805:
1802:
1800:
1796:
1795:
1792:
1788:
1785:
1782:
1778:
1775:
1773:
1769:
1768:
1765:
1762:
1760:
1756:
1755:
1752:
1749:
1747:
1743:
1742:
1739:
1736:
1734:
1730:
1729:
1726:
1723:
1721:
1717:
1716:
1713:
1710:
1708:
1700:
1699:
1691:
1688:
1687:
1686:
1683:
1680:
1673:
1672:
1669:
1666:
1639:
1638:
1635:
1632:
1629:
1625:
1624:
1621:
1618:
1615:
1611:
1610:
1607:
1604:
1601:
1597:
1596:
1593:
1590:
1587:
1579:
1578:
1575:
1572:
1563:
1562:
1556:
1553:
1550:
1546:
1545:
1542:
1539:
1536:
1532:
1531:
1528:
1524:
1521:
1517:
1513:
1510:
1507:
1503:
1502:
1499:
1496:
1493:
1489:
1488:
1485:
1482:
1479:
1475:
1474:
1471:
1468:
1465:
1461:
1460:
1457:
1454:
1451:
1425:Wang B-machine
1414:, p. 218)
1408:
1392:
1389:
1386:
1385:
1381:
1378:
1374:
1370:
1367:
1363:
1359:
1356:
1352:
1351:
1348:
1344:
1341:
1337:
1334:
1330:
1329:
1326:
1323:
1321:
1308:
1292:
1291:
1288:
1285:
1281:
1278:
1274:
1270:
1267:
1263:
1262:
1259:
1255:
1252:
1248:
1245:
1241:
1240:
1237:
1234:
1232:
1209:
1206:
1204:
1203:
1199:
1196:Joachim Lambek
1184:
1177:
1174:
1170:
1166:
1157:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1099:
1097:
1095:
1093:
1091:
1088:
1084:
1083:
1081:
1079:
1077:
1075:
1072:
1068:
1067:
1065:
1063:
1061:
1059:
1056:
1052:
1051:
1049:
1047:
1045:
1043:
1040:
1037:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1017:
1015:
1013:
1011:
1009:
1006:
1002:
1001:
998:
995:
992:
989:
986:
983:
982:
979:
976:
973:
970:
967:
964:
963:
961:
959:
957:
955:
952:
948:
947:
944:
941:
938:
935:
932:
923:
922:
920:
919:
904:
893:
886:
878:
867:
866:
843:
842:
837:
834:
824:
823:
820:
816:
812:
809:
805:
801:
798:
793:
789:
785:
781:
777:
776:
773:
770:
766:
762:
759:
755:
751:
748:
744:
743:
740:
737:
735:
730:
729:
728:of the forms":
725:
716:
715:
711:
707:
704:
701:
697:
694:
689:
685:
681:
677:
676:
672:
669:
665:
662:
658:
655:
651:
650:
647:
644:
642:
630:
629:
601:
598:
595:
594:
591:
588:
585:
581:
580:
577:
574:
571:
567:
566:
563:
560:
557:
553:
552:
549:
546:
543:
539:
538:
535:
532:
530:
525:
524:
505:
502:
499:
498:
494:
490:
487:
484:
479:
475:
471:
467:
466:
463:
460:
457:
453:
452:
449:
445:
442:
439:
435:
432:
428:
424:
421:
417:
416:
413:
409:
406:
403:
399:
396:
392:
388:
385:
381:
380:
377:
374:
372:
360:
357:
354:
353:
349:
345:
342:
339:
335:
331:
328:
324:
323:
320:
317:
314:
310:
309:
306:
302:
299:
296:
292:
289:
285:
281:
278:
274:
273:
270:
267:
264:
260:
259:
256:
253:
251:
234:
233:
230:
227:
224:
220:
219:
216:
213:
210:
206:
205:
202:
199:
194:
190:
189:
186:
183:
180:
176:
175:
172:
169:
166:
162:
161:
158:
155:
152:
148:
147:
144:
141:
138:
134:
133:
130:
127:
125:
113:
112:
95:
94:
91:
65:
62:
60:
57:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2650:
2639:
2636:
2635:
2633:
2623:
2619:
2616:
2615:
2610:
2605:
2604:0-444-88071-2
2601:
2597:
2593:
2590:
2589:
2588:
2587:
2583:
2579:
2576:
2573:
2569:
2566:
2563:
2559:
2555:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2531:
2530:Ershov, A. P.
2528:
2525:
2521:
2517:
2512:
2508:
2504:
2500:
2499:
2493:
2492:
2488:
2484:
2477:
2476:
2470:
2469:Marvin Minsky
2466:
2462:
2458:
2454:
2450:
2446:
2442:
2438:
2437:Marvin Minsky
2434:
2431:
2427:
2423:
2420:
2417:
2413:
2409:
2406:
2403:
2399:
2396:
2393:
2389:
2384:
2380:
2376:
2372:
2368:
2364:
2360:
2356:
2352:
2348:
2344:
2340:
2339:
2327:
2321:
2317:
2310:
2309:
2303:
2302:
2298:
2292:
2286:
2282:
2278:
2274:
2270:
2266:
2262:
2261:
2257:
2249:
2248:Cutland (1980
2243:
2240:
2236:
2231:
2228:
2224:
2219:
2216:
2212:
2207:
2205:
2201:
2194:
2192:
2189:
2187:
2183:
2154:
2136:
2122:
2108:
2094:
2080:
2066:
2063:Description:
2053:
2050:
2047:
2045:
2041:
2037:
2033:
2029:
2025:
2021:
2016:
2012:
2008:
2004:
2002:
1998:
1994:
1990:
1986:
1982:
1978:
1973:
1971:
1967:
1959:
1958:
1957:
1955:
1951:
1937:
1933:
1932:
1931:
1929:
1925:
1921:
1911:
1910:
1908:
1907:
1903:
1902:
1901:
1898:
1896:
1892:
1887:
1885:
1877:
1876:
1875:
1857:
1836:
1822:
1810:
1797:
1791:to register r
1770:
1757:
1744:
1731:
1718:
1715:Description:
1706:
1703:
1697:
1696:
1695:
1684:
1681:
1678:
1677:
1676:
1670:
1667:
1664:
1663:
1662:
1659:
1655:
1651:
1647:
1645:
1626:
1622:
1619:
1616:
1608:
1605:
1602:
1595:Description:
1589:Reduced URM:
1585:
1582:
1576:
1573:
1570:
1569:
1568:
1561:
1547:
1533:
1527:to register r
1504:
1490:
1486:
1483:
1480:
1472:
1469:
1466:
1459:Description:
1449:
1446:
1443:
1441:
1436:
1432:
1430:
1426:
1422:
1413:
1407:
1403:
1401:
1397:
1379:
1368:
1357:
1349:
1342:
1335:
1328:Description:
1319:
1316:
1312:
1304:
1300:
1298:
1289:
1279:
1268:
1260:
1253:
1246:
1239:Description:
1230:
1227:
1225:
1221:
1215:
1214:
1200:
1197:
1193:
1189:
1185:
1182:
1178:
1175:
1171:
1168:
1167:
1165:
1163:
1154:
1151:
1148:
1145:
1142:
1140:
1139:
1135:
1132:
1129:
1126:
1123:
1121:
1120:
1116:
1113:
1110:
1107:
1104:
1102:
1101:
1098:
1096:
1094:
1092:
1089:
1086:
1085:
1082:
1080:
1078:
1076:
1073:
1070:
1069:
1066:
1064:
1062:
1060:
1057:
1054:
1053:
1050:
1048:
1046:
1044:
1041:
1039:
1038:
1034:
1031:
1028:
1025:
1022:
1020:
1019:
1016:
1014:
1012:
1010:
1007:
1004:
1003:
999:
996:
993:
990:
987:
985:
984:
980:
977:
974:
971:
968:
966:
965:
962:
960:
958:
956:
953:
950:
949:
945:
942:
939:
936:
933:
930:
929:
926:
917:
913:
909:
905:
902:
898:
894:
891:
887:
884:
880:
879:
876:
875:
874:
872:
864:
860:
856:
855:
854:
852:
847:
840:
839:
835:
833:
831:
830:Gödel numbers
819:else instr. I
810:
799:
782:
771:
760:
749:
742:Description:
733:
723:
722:
721:
705:
695:
682:
670:
663:
656:
649:Description:
640:
637:
635:
627:
626:
625:
623:
619:
615:
611:
607:
582:
576:+ 1 → , →
568:
554:
540:
537:Description:
528:
522:
518:
514:
513:
512:
510:
468:
454:
448:to register r
418:
412:to register r
382:
379:Description:
370:
367:
365:
325:
311:
305:to register r
275:
261:
258:Description:
249:
246:
244:
240:
221:
207:
191:
177:
163:
149:
135:
123:
120:
118:
110:
109:
108:
105:
101:
98:
92:
89:
88:
87:
85:
82:The only two
80:
78:
74:
71:observe that
70:
58:
56:
54:
50:
46:
42:
38:
34:
30:
19:
2621:
2595:
2581:
2561:
2550:
2548:Hermes, Hans
2541:
2539:PĂ©ter, RĂłzsa
2532:
2523:
2519:
2502:
2496:
2486:
2482:
2474:
2444:
2440:
2425:
2422:Z. A. Melzak
2415:
2411:
2401:
2398:Donald Knuth
2358:
2354:
2347:Meyer, A. R.
2329:. Retrieved
2307:
2296:
2276:
2258:Bibliography
2250:, p. 9)
2242:
2230:
2218:
2190:
2185:
2181:
2179:
2057:Instruction
2048:
2043:
2039:
2035:
2031:
2027:
2023:
2019:
2014:
2010:
2006:
2005:
2000:
1996:
1992:
1988:
1984:
1980:
1976:
1974:
1969:
1965:
1963:
1947:
1917:
1899:
1894:
1890:
1888:
1883:
1881:
1873:
1701:
1693:
1674:
1649:
1648:
1643:
1642:
1580:
1566:
1560:instruction
1559:
1444:
1439:
1438:
1434:
1418:
1405:
1394:
1313:
1305:
1301:
1296:
1295:
1219:
1216:
1212:
1211:
1161:
1160:
991:( - )=0 → X
972:( - )=0 → X
934:Instruction
924:
915:
911:
907:
900:
896:
889:
882:
870:
868:
862:
858:
850:
848:
844:
827:
804:else go to I
719:
633:
631:
603:
507:
362:
242:
237:
132:Description
114:
106:
102:
99:
96:
83:
81:
76:
72:
67:
26:
2572:Frances Yao
2386:. Develops
2013:: register
1924:mu operator
1453:URM model:
2331:7 November
2325:0521223849
2195:References
2102:→ n, → z
1926:(see also
1878:{ , , , }
1654:tag system
1427:(also see
610:tag system
562:→ n, →
157:→ r, → A
143:→ A, → r
84:arithmetic
2558:SchĹŤnhage
2275:(2007) .
2246:See also
1658:Emil Post
1173:sequence.
943:Hole "Z"
940:Hole "Y"
937:Hole "X"
684:SUB (r, I
657:ADD (r, I
606:Emil Post
53:Schönhage
2632:Category
2620:(1957),
2618:Hao Wang
2560:(1980),
2471:(1967).
2400:(1968),
2383:13006433
2088:+ 1 → z
2060:Action:
1827:goto(z)
1738:+ 1 → r
1712:Action:
1620:- 1 → r
1606:+ 1 → r
1592:Action:
1484:- 1 → r
1470:+ 1 → r
1456:Action:
1421:Hao Wang
1409:—
1402:report:
1325:Action:
1269:X- (r, I
1247:X+ (r, I
1236:Action:
1130:+ → Y
1114:+ → Z
1108:- → X
1029:+ → Y
1026:- → X
975:+ → Y
931:Allowed
739:Action:
646:Action:
587:J(m, n)
573:C'(m,n)
534:Action:
376:Action:
269:+ 1 → A
255:Action:
185:+ 1 → A
171:0 → A
154:C(A, r)
140:C(r, A)
129:Action:
2461:1970290
2375:0235932
1567:Notes.
1509:C(m,n)
1498:0 → r
1202:decide.
1152:+ →
750:MULT (K
614:Hilbert
559:C(m,n)
75:, and:
2602:
2594:, ed.
2459:
2381:
2373:
2322:
2287:
2159:goto I
2116:] → z
2074:0 → z
1781:, → r
1725:0 → r
1631:J(r)
1552:J(r)
1516:, → r
1220:formal
871:single
784:DIV (K
612:) and
548:0 →
438:, → r
434:+1 → r
402:, → r
316:J(r)
295:, → r
229:1 → A
226:O'(A)
212:On(A)
49:Lambek
45:Minsky
37:Ershov
33:Hermes
2457:JSTOR
2379:S2CID
2312:(PDF)
1817:HALT
1628:~f1:
1617:D(n)
1603:P(r)
1495:O(n)
1481:D(n)
1467:P(n)
1358:1- (I
1336:1+ (I
608:(the
545:O(n)
423:C' (r
266:P(A)
197:J(A)
182:P(A)
168:O(A)
41:PĂ©ter
2600:ISBN
2390:and
2333:2023
2320:ISBN
2285:ISBN
2184:, a
2040:zero
2024:zero
1934:Any
1909:j.
1614:b1.
1600:a1.
1355:b1.
1333:a1.
1149:→ Y
1146:→ X
1143:SYZ
1133:→ Z
1127:→ X
1124:SYY
1111:→ Y
1105:XYZ
1090:XSS
1074:XSY
1058:XSX
1042:XYS
1032:→ Z
1023:XYY
1008:XYX
997:→ Z
994:→ Y
988:XXS
978:→ Z
969:XXY
954:XXX
570:d'.
470:f*:
420:d'.
223:G2:
209:G1:
193:F1:
179:A1:
165:C1:
151:D2:
137:D1:
2556:A.
2507:doi
2449:doi
2363:doi
2186:RAM
2130:→
2038:to
1904:f.
1859:j.
1838:i.
1824:h.
1812:g.
1799:f.
1777:→ r
1772:e.
1759:d.
1746:c.
1733:b.
1720:a.
1656:of
1549:f:
1535:e.
1512:→ r
1506:d.
1492:c:
1478:b.
1464:a.
1362:, I
1273:, I
1266:b.
1244:a.
1087:NO
1071:NO
1055:NO
1005:NO
951:NO
912:add
792:, I
788:, I
780:b.
754:, I
747:a.
680:b.
654:a.
634:two
584:e.
556:d.
542:c:
478:, r
474:J(r
456:e.
398:→ r
387:C(r
384:d.
334:, r
330:E(r
327:c:
313:f:
291:→ r
284:, r
280:C(r
277:d.
263:a:
2634::
2580:,
2503:10
2501:.
2455:.
2445:74
2443:.
2428:,
2377:,
2371:MR
2369:,
2357:,
2349:;
2345:;
2318:.
2314:.
2283:.
2271:;
2267:;
2203:^
2156:7
2148:)
2141:C
2138:6
2127:S
2124:5
2113:L
2110:4
2099:N
2096:3
2085:A
2082:2
2071:Z
2068:1
1862:*
1538:J
1520:,
1377:.
1366:)
1347:.
1340:)
1299::
1277:)
1258:.
1251:)
1164::
821:j2
817:j1
808:.
806:j1
802:j2
794:j2
790:j1
769:.
767:j1
761:*K
758:)
756:j1
714:.
712:j1
708:j2
702:j1
698:j2
690:j2
688:,I
686:j1
675:.
673:j1
668:.
666:j1
661:)
659:j1
620:,
459:J
431:)
427:,r
395:)
391:,r
338:)
288:)
79:.
47:,
43:,
39:,
35:,
2524:5
2513:.
2509::
2463:.
2451::
2418:.
2365::
2359:2
2335:.
2293:.
2173:λ
2167:λ
2161:λ
2146:λ
2044:z
2036:z
2032:n
2028:z
2022:=
2020:z
2015:z
2011:z
2001:z
1997:n
1993:z
1989:n
1985:n
1981:z
1977:z
1970:z
1966:n
1895:w
1891:w
1884:w
1852:k
1848:j
1793:k
1789:j
1783:j
1779:k
1529:k
1525:j
1518:j
1514:k
1382:b
1375:a
1371:b
1364:b
1360:a
1345:a
1338:a
1309:a
1286:a
1282:b
1275:b
1271:a
1256:a
1249:a
1190:(
918:.
916:Z
908:X
901:X
897:X
892:,
890:Y
885:,
883:Y
851:S
813:j
796:)
786:j
774:j
763:j
752:j
726:j
692:)
495:k
491:j
482:)
480:k
476:j
450:k
446:j
440:j
436:k
429:k
425:j
414:k
410:j
404:j
400:k
393:k
389:j
350:k
346:j
336:k
332:j
307:k
303:j
297:j
293:k
286:k
282:j
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.