81:
1357: – by using a primitive recursive "operator" called "definition by cases" (defined in Kleene (1952) p. 229 and Boolos-Burgess-Jeffrey p. 74). Such a "bounded indirection" is a laborious, tedious affair. "Definition by cases" requires the machine to determine/distinguish the contents of the pointer register by attempting, time after time until success, to match this contents against a number/name that the case operator
2077:= { r0, r1, r2, ... } to an unbounded string of (very-) bounded-capacity pigeon-holes. These will do nothing but hold (very-) bounded numbers e.g. a lone bit with value { 0, 1 }. Likewise we shrink the accumulator to a single bit. We restrict any arithmetic to the registers { A, N }, use indirect operations to pull the contents of registers into the accumulator and write 0 or 1 from the accumulator to a register:
2138:
square" that "the head" is currently observing. The "head" can be thought of as being in the conditional jump – observe that it uses indirect addressing (cf Elgot-Robinson p. 398). As we decrement or increment "N" the (apparent) head will "move left" or "right" along the squares. We will move the contents of "E"=0 or "P"=1 to the "scanned square" as pointed to by N, using the indirect CPY.
1554:: Because any instruction acting on a single register can be augmented with its indirect "dual" (including conditional and unconditional jumps, cf the Elgot-Robinson model), the inclusion of indirect instructions will double the number of single parameter/register instructions (e.g. INC (d, r), INC (i, r)). Worse, every two parameter/register instruction will have 4 possible varieties, e.g.:
1157: – it has no indirection capability – cannot compute all "recursive sequential functions" (ones that have parameters of arbitrary length) if it does not have the capability of modifying its own instructions, but it can via Gödel numbers if it does (p. 395-397; in particular figure 2 and footnote p. 395). On the other hand their RASP model P'
40:
198:
143:
1443:
register – in some models every register can be a pointer register – is specified by the instruction). This "mutually exclusive but exhaustive choice" is yet another example of "definition by cases", and the arithmetic equivalent shown in the example below is derived from the definition in Kleene (1952) p. 229.
1310:
model – quite similar to Melzak's (1961) model – uses two and three-register adds and subtracts and two parameter copies; Cook and
Reckhow's model reduce the number of parameters (registers called out in the program instructions) to one call-out by use of an accumulator "AC".
1771:
If we designate one register to be the "accumulator" (see below) and place strong restrictions on the various instructions allowed then we can greatly reduce the plethora of direct and indirect operations. However, one must be sure that the resulting reduced instruction-set is sufficient, and we must
1196:
finite both in the number of "states" (instructions) and the instructions' sizes (their capacity to hold symbols/signs). So how does a state machine move an arbitrarily large constant directly into a register, e.g. MOVE (k, r) (Move constant k to register r)? If huge constants are necessary they must
997:
of instructions created from the base set and given a mnemonic. In a formal sense, to use these blocks we need to either (i) "expand" them into their base-instruction equivalents – they will require the use of temporary or "auxiliary" registers so the model must take this into account,
600:
of a tape's "head" from its left end, measured in numbers of tape-squares, represents the natural number in "the register". To DECrement the count of squares the tape head moves left; INCrement it moves right. There is no need to print or erase marks on the tape; the only conditional instructions are
584:
Melzak (1961) provides an easy visualization of a counter machine: its "registers" are holes in the ground, and these holes hold pebbles. Per an instruction, into and out of these holes "the computer" (person or machine) adds (INCrements) or removes (DECrements) a single pebble. As needed, additional
2985:
We will build the indirect CPY ( i, q, d, φ ) with the CASE operator. The address of the target register will be specified by the contents of register "q"; once the CASE operator has determined what this number is, CPY will directly deposit the contents of the register with that number into register
2045:
For maximum flexibility, as we have done for the accumulator A – we will consider N just another register subject to increment, decrement, clear, test, direct copy, etc. Again we can shrink the instruction to a single-parameter that provides for direction and indirection, for example.
1270:-instructions (the ones stored in the registers) so that they contain more than one command. But this too can be exhausted unless an instruction is of (potentially) unbounded size. So why not use just one "ĂĽber-instruction" – one really really big number – that contains
1205:
Sometimes the constant k will be created by use of CLR ( r ) followed by INC ( r ) repeated k times – e.g. to put the constant k=3 into register r, i.e. 3 → r, so at the end of the instruction =3: CLR (r), INC (r), INC (r), INC (r). This trick is mentioned by Kleene (1952) p. 223. The
2991:
So the following is actually a constructive demonstration or proof that we can indeed simulate the indirect CPY ( i, q, d, φ ) without a "hardware" design change to our counter machine/model. However, note that because this indirect CPY is "bounded" by the size/extent of the finite state machine, a
2137:
We give here a slightly more formal demonstration. Begin by designing our model with three reserved registers "E", "P", and "N", plus an unbounded set of registers 1, 2, ..., n to the right. The registers 1, 2, ..., n will be considered "the squares of the tape". Register "N" points to "the scanned
2041:
Another approach (Schönhage does this too) is to declare a specific register the "indirect address register" and confine indirection relative to this register (Schonhage's RAM0 model uses both A and N registers for indirect as well as direct instructions). Again our new register has no conventional
1967:
The typical accumulator-based model will have all its two-variable arithmetic and constant operations (e.g. ADD (A, r), SUB (A, r) ) use (i) the accumulator's contents, together with (ii) a specified register's contents. The one-variable operations (e.g. INC (A), DEC (A) and CLR (A) ) require only
1133:
In the following one must remember that these models are abstract models with two fundamental differences from anything physically real: unbounded numbers of registers each with unbounded capacities. The problem appears most dramatically when one tries to use a counter-machine model to build a RASP
964:
The three base sets 1, 2, or 3 above are equivalent in the sense that one can create the instructions of one set using the instructions of another set (an interesting exercise: a hint from Minsky (1967) – declare a reserved register e.g. call it "0" (or Z for "zero" or E for "erase")
2141:
The fact that our tape is left-ended presents us with a minor problem: Whenever LEFT occurs our instructions will have to test to determine whether or not the contents of "N" is zero; if so we should leave its count at "0" (this is our choice as designers – for example we might have
491:
Example: → 5; means "The contents of source register with address "3" is put into destination register with address "5". If =38, that is, the contents of register 3 is the number 38, then this number will be put into register 5. The contents of register 3 are not disturbed by this operation, so
3112:
We begin with a number in register q that represents the address of the target register. But what is this number? The "predicates" will test it to find out, one trial after another: JE (q, y, z) followed by INC (y). Once the number is identified explicitly, the CASE operator directly/explicitly
1792:
However, the accumulator comes at the expense of more instructions per arithmetic "operation", in particular with respect to what are called 'read-modify-write' instructions such as "Increment indirectly the contents of the register pointed to by register r2 ". "A" designates the "accumulator"
1442:
need to specify an additional parameter "i/d" – "indirect/direct". In a sense this new "i/d" parameter is a "switch" that flips one way to get the direct address as specified in the instruction or the other way to get the indirect address from the pointer register (which pointer
1147:
Melzak (1961) added indirection to his "hole-and-pebble" model so that his model could modify itself with a "computed goto" and provides two examples of its use ("Decimal representation in the scale of d" and "Sorting by magnitude", whether these are used in his proof that the model is Turing
1309:
From the references in
Hartmanis (1971) it appears that Cook (in his lecture notes while at UC Berkeley, 1970) has firmed up the notion of indirect addressing. This becomes clearer in the paper of Cook and Reckhow (1973) – Cook is Reckhow's Master's thesis advisor. Hartmanis'
481:
Example: +1 → 3; means "The contents of source register with address "3", plus 1, is put into destination register with address "3" (here source and destination are the same place). If =37, that is, the contents of register 3 is the number "37", then 37+1 = 38 will be put into register
3643:: Schönhage's RAM0 machine has 6 instructions indicated by a single letter (the 6th "C xxx" seems to involve 'skip over next parameter'. Schönhage designated the accumulator with "z", "N" with "n", etc. Rather than Schönhage's mnemonics we will use the mnemonics developed above.
621:
capacity, called "registers". These registers hold only natural numbers (zero and positive integers). Per a list of sequential instructions in the finite state machine's TABLE, a few (e.g. 2) types of primitive operations operate on the contents of these "registers". Finally, a
1788:. It is quite conventional in principle in past and present computing machines of the most varied types, e.g. desk multipliers, standard IBM counters, more modern relay machines, the ENIAC" (boldface in original: Goldstine and von Neumann, 1946; p. 98 in Bell and Newell 1971).
1152:
encoding, the register model did not need indirection to be Turing equivalent; but it did need at least one unbounded register. As noted below, Minsky (1967) hints at the problem for a RASP but doesn't offer a solution. Elgot and
Robinson (1964) proved that their RASP model
4165:(volume A). QA 76.H279 1990. van Emde Boas's 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.
987:
will be discussed in context of indirect addressing). However, building the primitive recursive functions is difficult because the instruction sets are so ... primitive (tiny). One solution is to expand a particular set with "convenience instructions" from another set:
510:
is one that specifies a "pointer register", the contents of which is the address of a "target" register. The target register can be either a source or a destination (the various COPY instructions provide examples of this). A register can address itself indirectly.
1294:"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 of the computer . RPT operations require infinite registers of their own." (p. 214).
3005:
The CASE "operator" is described in Kleene (1952) (p. 229) and in Boolos-Burgess-Jeffrey (2002) (p. 74); the latter authors emphasize its utility. The following definition is per Kleene but modified to reflect the familiar "IF-THEN-ELSE" construction.
1332:
that can, if necessary, hunt ad infinitum along the unbounded string of registers until it finds what it is looking for. The pointer register is exactly like any other register with one exception: under the circumstances called "indirect addressing" it provides
1281:
Elgot and
Robinson (1964) come to a similar conclusion with respect to a RASP that is "finitely determined". Indeed it can access an unbounded number of registers (e.g. to fetch instructions from them) but only if the RASP allows "self modification" of its
4081:, 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".
3009:
The CASE operator "returns" a natural number into φ depending on which "case" is satisfied, starting with "case_0" and going successively through "case_last"; if no case is satisfied then the number called "default" (aka "woops") is returned into φ (here
573:
is where the instruction deposits its result. The source register's address can be specified either (i) directly by the instruction, or (ii) indirectly by the pointer register specified by the instruction. The source and destination registers can be one.
1784:"The first part of our arithmetic organ ... should be a parallel storage organ which can receive a number and add it to the one already in it, which is also able to clear its contents and which can store what it contains. We will call such an organ an
1384:
Suppose we had been able to continue on to number 65367, and in fact that register had what we were looking for. Then we could have completed our calculation successfully! But suppose 65367 didn't have what we needed. How far should we continue to
4013:, 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."
391:
varies depending on the author; common instructions include: increment, decrement, clear to zero, copy, conditional jump, halt; other instructions are unnecessary because they can be created by combinations of instructions from the instruction
2154:
The following table both defines the Post-Turing instructions in terms of their RAM equivalent instructions and gives an example of their functioning. The (apparent)location of the head along the tape of registers r0-r5 . . . is shown shaded:
1345:
If we eschew the Minsky approach of one monster number in one register, and specify that our machine model will be "like a computer" we have to confront this problem of indirection if we are to compute the recursive functions (also called the
301:
of a common computer, except for the additional ability of registers to store natural numbers of any size. Like the counter machine, the RA-machine contains the execution instructions in the finite-state portion of the machine (the so-called
1398:
method, or be augmented with an ability to explore the ends of its register string, ad infinitum if necessary. (A failure to find something "out there" defines what it means for an algorithm to fail to terminate; cf Kleene (1952) pp. 316ff
3853:, 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
3713:, although it is "unbounded" in the sense that the model implies no upper limit to the number of registers necessary to do its job(s). For example, we do not require r < 83,617,563,821,029,283,746 nor r < 2^1,000,001, etc.
1306:, and he offers the unbounded RPT quoted above that as playing the role of ÎĽ operator; it together with CLR (r) and INC (r) can compute the mu recursive functions. But he does not discuss "indirection" or the RAM model per se.
423:
model. Two additions move it away from the counter machine, however. The first enhances the machine with the convenience of indirect addressing; the second moves the model toward the more conventional accumulator-based
3108:
that doing the testing are all mutually exclusive – "predicates" are functions that produce only { true, false } for output; Boolos-Burgess-Jeffrey add the requirement that the cases are "exhaustive".
3377:
The commonly encountered Cook and
Rechkow model is a bit like the ternary-register Malzek model (written with Knuth mnemonics – the original instructions had no mnemonics excepting TRA, Read, Print).
1197:
either start out in the registers themselves or be created by the state machine using a finite number of instructions e.g. multiply and add subroutines using INC and DEC (but not a quasi-infinite number of these!).
1547:
with the COPY instructions, and Cook-Reckhow (1973) provide their accumulator-based model with only two indirect instructions – COPY to accumulator indirectly, COPY from accumulator indirectly.
4135:, 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.
1289:
In the context of a more computer-like model using his RPT (repeat) instruction Minsky (1967) tantalizes us with a solution to the problem (cf p. 214, p. 259) but offers no firm resolution. He asserts:
467: – a single natural number. For precision we will use the quasi-formal symbolism from Boolos-Burgess-Jeffrey (2002) to specify a register, its contents, and an operation on a register:
1258:
state machine to address them, then registers outside the bounds will be unreachable. For example, if the finite state machine can only reach 65,536 = 2 registers then how can it reach the 65,537th?
1148:
equivalent is unclear since "the program itself is left to the reader as an exercise" (p. 292)). Minsky (1961, 1967) was able to demonstrate that, with suitable (but difficult-to-use)
544:
is used by the instruction. The source register's address can be specified either (i) directly by the instruction, or (ii) indirectly by the pointer register specified by the instruction.
3995:, 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)
1366:
Is the number in register N equal to 0? If not then is it equal to 1? 2? 3? ... 65364? If not then we're at the last number 65365 and this had better be the one, else we have a problem!
3709:
The definitional fact that any sort of counter machine without an unbounded register-"address" register must specify a register "r" by name indicates that the model requires "r" to be
1075:
Most authors pick one or the other of the conditional jumps, e.g. Shepherdson-Sturgis (1963) use the above set minus JE (to be perfectly accurate they use JNZ – Jump if
617:
has, for a memory external to its finite-state machine – an unbounded (cf: footnote|countable and unbounded) collection of discrete and uniquely labelled locations with
3985:, 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."
1328:
register requires an ability to be cleared and then incremented (and, possibly, decremented) by a potentially infinite loop. In this sense the solution represents the unbounded
3522:
Conditional jump if is positive; i.e. IF > 0 THEN jump to instruction z else continue in sequence (Cook and
Reckhow call this: "TRAnsfer control to line m if Xj > 0")
4067:. 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.
1780:
Historical convention dedicates a register to the accumulator, an "arithmetic organ" that literally accumulates its number during a sequence of arithmetic operations:
1415:
indirection we require a "hardware" change in our machine model. Once we make this change the model is no longer a counter machine, but rather a random-access machine.
1233:) that uses its finite-state machine to interpret a "program of instructions" located in its registers – i.e. we are building what is nowadays called a
161:
3857:; 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.
1990:
If we so choose, we can abbreviate the mnemonics because at least one source-register and the destination register is always the accumulator A. Thus we have :
1361:
declares. Thus the definition by cases starts from e.g. the lower bound address and continues ad nauseam toward the upper bound address attempting to make a match:
1161:
equipped with an "index register" (indirect addressing) can compute all the "partial recursive sequential functions" (the mu recursive functions) (p. 397-398).
596:
with as many left-ended tapes as "registers". Each tape's length is unbounded to the right, and every square is blank except for the left end, which is marked. The
585:
pebbles come from, and excess pebbles go back into, an infinite supply; if the hole is too small to accommodate the pebbles the "computer" digs the hole bigger.
1229:: This is more severe than the first problem. In particular, this problem arises when we attempt to build a so-called RASP, a "universal machine" (see more at
2109:
Rename the COPY instructions and call INC (N) = RIGHT, DEC (N) = LEFT and we have the same instructions as the Post-Turing machine, plus an extra CLRN :
847:: Used by Elgot-Robinson (1964) in their investigation of bounded and unbounded RASPs – the "successor" model with COPY in the place of CLEAR:
471:
means "the contents of register with address r". The label "r" here is a "variable" that can be filled with a natural number or a letter (e.g. "A") or a name.
3583:: Schönhage demonstrates how his construction can be used to form the more common, usable form of "successor"-like RAM (using this article's mnemonics):
515:
For want of a standard/convention this article will specify "direct/indirect", abbreviated as "d/i", as a parameter (or parameters) in the instruction:
2974:
which gives a sequence of operations for solving a specific type of problem, an algorithm has five important features " (italics added, Knuth p. 4-7).
3692:
Indirection comes (i) from CPYAN (copy/transfer contents A to N) working with store_A_via_N STAN, and from (ii) the peculiar indirection instruction
1468:
Assign a code to specify direct addressing as d="0" and indirect addressing as i="1". Then our machine can determine the source address as follows:
1002:
Example: Base set 1. To create CLR (r) use the block of instructions to count down register r to zero. Observe the use of the hint mentioned above:
534:
get the destination address from pointer-register N. Suppose =3, then register 3 is the destination and the instruction will do the following: → 3.
1913:
However, when we write the CPY instructions without the accumulator called out the instructions are ambiguous or they must have empty parameters:
1278:
he uses represents a great inconvenience to the model, and the result is nothing at all like our intuitive notion of a "stored program computer".
2980:
The difficulty arises because the registers have explicit "names" (numbers) and our machine must call each out by name in order to "access" it.
1337:
contents, rather than the address-operand in the state machine's TABLE, to be the address of the target register (including possibly itself!).
53:
630:
is available to test the contents of one or two registers and "branch/jump" the finite state machine out of the default instruction-sequence.
3733:
We can escape this restriction by providing an unbounded register to provide the address of the register that specifies an indirect address.
1924:
Historically what has happened is these two CPY instructions have received distinctive names; however, no convention exists. Tradition (e.g.
1173:
The indirect instructions are necessary in order for a fixed program to access an unbounded number of registers as the inputs vary." (p. 73)
1108:(3) We go to location "under_Thatcher's_front_porch", jackhammer away the concrete, and discover "the treasure": a sack of rusty door-knobs.
318:
3356:. But it can't – its finite state machine's "state register" has reached its maximum count (e.g. 65365 = 11111111,11111111
1592:) = COPY contents of source-register indirectly into register using destination address to be found in the destination-pointer register r
448:'s TABLE, the machine derives a "target" register's address either (i) directly from the instruction itself, or (ii) indirectly from the
965:
to contain the number 0). The choice of model will depend on which an author finds easiest to use in a demonstration, or a proof, etc.
3935:(1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
3817:
Goldstine, Herman H., and von
Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947,
1968:
the accumulator. Both instruction-types deposit the result (e.g. sum, difference, product, quotient or remainder) in the accumulator.
1324:"address" register that can potentially name (call out) any register no matter how many there are. For this to work, in general, the
4175:, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23–25, 1954.
4162:
3972:
3954:
3892:
3830:
3216:
Case_n (the induction step) looks like this; remember, each instance of "n", "n+1", ..., "last" must be an explicit natural number:
341:
252:
234:
216:
208:
179:
124:
102:
67:
1051:
For example: the most expanded set would include each unique instruction from the three sets, plus unconditional jump J (z) i.e.:
2035:
all the other registers? Not until we provide for at least one unbounded register from which we derive our indirect addresses.
1905:
If we stick with a specific name for the accumulator, e.g. "A", we can imply the accumulator in the instructions, for example,
1353:
Our simpler counter-machine model can do a "bounded" form of indirection – and thereby compute the sub-class of
4010:
349:
2993:
3908:
3818:
1354:
1303:
973:
506:
the address of the source or destination register whose contents will be the subject of the instruction. Definition: An
428:
with the addition of one or more auxiliary (dedicated) registers, the most common of which is called "the accumulator".
388:
297:
but with the added capability of 'indirect addressing' of its registers. The 'registers' are intuitively equivalent to
2093:
We push further and eliminate A altogether by the use of two "constant" registers called "ERASE" and "PRINT": =0, =1.
1371:"Bounded" indirection will not allow us to compute the partial recursive functions – for those we need
2134:. The Post–Turing machine is Turing equivalent, so we have shown that the RAM with indirection is Turing equivalent.
1479:
For example, suppose the contents of register 3 are "5" (i.e. =5 ) and the contents of register 4 are "2" (i.e. =2 ):
1099:
At location "Tom_&_Becky's_cave_in_pirate_chest" will be where we can find a map directing us to "the treasure":
1192:
state part of the machine is supposed to be – by the normal definition of algorithm –
4188:
2958:
Throughout this demonstration we have to keep in mind that the instructions in the finite state machine's TABLE is
59:
3717:
Thus our model can "expand" the number of registers, if necessary to perform a certain computation. However this
1577:) = COPY to destination-register indirectly using the source address to be found in the source-pointer register r
3790:
1539:
Probably the most useful of the added instructions is COPY. Indeed, Elgot-Robinson (1964) provide their models P
3560:
Schönhage (1980) describes a very primitive, atomized model chosen for his proof of the equivalence of his SMM
2073:
Posing as minimalists, we reduce all the registers excepting the accumulator A and indirection register N e.g.
1238:
1230:
601:
to check to see if the head is at the left end, by testing a left-end mark with a "Jump-if-marked instruction".
322:
310:
95:
89:
3957:. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
3281:
Case_last stops the induction and bounds the CASE operator (and thereby bounds the "indirect copy" operator):
2131:
1607:) = COPY indirectly the contents of the source register with address to be found in source-pointer register r
4020:(1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines".
2986:"φ". We will need an additional register that we will call "y" – it serves as an up-counter.
1347:
3747:
1929:
106:
4070:
2130:
In the section above we informally showed that a RAM with an unbounded indirection capability produces a
1266:
we address a register beyond the bounds of the finite state machine? One approach would be to modify the
2997:
1139:
1121:
to any other location (including itself): its contents (the treasure map) provides the "address" of the
984:
337:
4105:, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
3929:, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
1772:
be aware that the reduction will come at the expense of more instructions per "significant" operation.
445:
365:
303:
298:
282:
28:
4168:
4146:
4128:
4074:
1391:
1135:
4002:
3932:
3918:
1210:
state machine; there is always a bigger constant than the number of instructions available to the
1206:
problem arises when the number to be created exhausts the number of instructions available to the
1117:
specifies a location identified as the pirate chest in "Tom_&_Becky's_cave..." that acts as a
4037:
1048:
Again, all of this is for convenience only; none of this increases the model's intrinsic power.
976:( cf Minsky (1967), Boolos-Burgess-Jeffrey (2002) ). (How to cast the net wider to capture the
4158:
4108:
3968:
3950:
3888:
3826:
1611:, into the destination register with address to be found in the destination-pointer register r
1438:
is the address of interest. Whenever an instruction specifies a register address it now will
1418:
Now when e.g. INC is specified, the finite state machine's instruction will have to specify
4029:
3922:
3868:
3864:
3808:
614:
530:
get the source register's address (register "A") from the instruction itself but indirectly
403:
For a description of a similar concept, but humorous, see the esoteric programming language
314:
290:
286:
266:
3675:; contents of N points to register address; put contents of A into register pointed to by N
1105:(2) Inside the box is a map to the location of the treasure: "under_Thatcher's_front_porch"
1102:(1) We go to location "Tom_&_Becky's_cave..." and dig around until we find a wooden box
4150:
3846:
3842:
3561:
3014:
designates some selection of parameters, e.g. register q and the string r0, ... rlast )):
441:
420:
345:
294:
1619:
In a similar manner every three-register instruction that involves two source registers r
1395:
1275:
1274:
the program instructions encoded into it! This is how Minsky solves the problem, but the
1149:
1129:
Why the need for an indirect operation: Two major problems with the counter-machine model
1932:
computer) uses two names called LOAD and STORE. Here we are adding the "i/d" parameter:
592:
Minsky (1961) and
Hopcroft-Ullman 1979 (p. 171) offer the visualization of a multi-tape
4051:
3988:
3960:
3942:
3821:, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971),
608:
The following instruction "mnemonics" e.g. "CLR (r)" are arbitrary; no standard exists.
593:
399:" (IR); this register points to the instruction being executed in the instruction table
377:
373:
333:
3769:
3568:"In order to avoid any explicit addressing the RAM0 has the accumulator with contents
3486:, Indirectly copy the contents of the source-register pointed to by pointer-register r
4182:
4099:
4017:
3938:
3838:
1376:
1329:
463:(a unique, distinguishable designation/locator equivalent to a natural number) and a
416:
17:
2097:{ CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I
444:
with the addition of indirect addressing. At the discretion of instruction from its
3978:
3898:
3880:
3860:
2042:
name – perhaps "N" from "iNdex", or "iNdirect" or "address Number".
1925:
737:
3873:
Preliminary discussion of the logical design of an electronic computing instrument
440:(RAM) is an abstract computational-machine model identical to a multiple-register
380:
or zero; each register can store exactly one natural number of any size, or a zero
3764:
1246:
Observe that the counter machine's finite state machine must call out a register
566: – the "target" may be either a source or a destination register.
474:→ means "copy/deposit into", or "replaces", but without destruction of the source
3876:
3353:
1114:
1394:
the counter machine needs to either use the unfortunate single-register Minsky
1250:(directly) by its name/number: INC (65,356) calls out register number "65,365"
3759:
4155:
Handbook of
Theoretical Computer Science. Volume A: Algorithms and Complexity
452:(e.g. number, label) of the "pointer" register specified in the instruction.
2065:
Schönhage does this to produce his RAM0 instruction set. See section below.
1286:
instructions, and has encoded its "data" in a Gödel number (Fig. 2 p. 396).
1125:
location "under_Thatcher's_front_porch" where the real action is occurring.
404:
3927:
Random-Access Stored-Program
Machines, an Approach to Programming Languages
3373:
Register-to-register ("read-modify-write") model of Cook and Reckhow (1973)
2954:
Example: Bounded indirection yields a machine that is not Turing equivalent
2053:
STAN (i/d) = CPY (d, A, i/d, N). STore Accumulator via iNdirection register
636:: The model closest to Minsky's (1961) visualization and to Lambek (1961):
3669:; contents of A points to register address; put register's contents into A
2050:
LDAN (i/d) = CPY (i/d, N, d, A); LoaD Accumulator via iNdirection register
744:{ INCrement the contents of register r, CLeaR the contents of register r,
3742:
1234:
1092:
In our daily lives the notion of an "indirect operation" is not unusual.
425:
326:
4041:
1566:) = COPY directly from source-register directly to destination-register
851:{ INCrement the contents of register r, COPY the contents of register r
3142:
case_last: IF INC (y), = ="last" THEN CPY ( rlast, φ ), J (exit) ELSE
640:{ INCrement contents of register r, DECrement contents of register r,
2146:
Instruction set 1 (augmented): { INC (N), DEC (N), CLR (N), CPY (d, r
1857:
Contents of r2 points to r378,426 with contents "17": copy this to A
1486:
Example: CPY ( 1, 3, 0, 4 ) = CPY ( indirect, reg 3, direct, reg 4 )
4092:, Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:
4033:
1899:
Contents of r2 points to r378,426: copy contents of A into r378,426
1403:, in particular p. 323-325.) See more on this in the example below.
1186:
of registers versus bounded capacities of state-machine instructions
1079:
Zero in place of JZ; yet another possible convenience instruction).
998:
or (ii) design our machines/models with the instructions 'built in'.
317:
in the registers as well as its data – is called the
1426:
can be either (i) the state machine's instruction that provides an
993:
These will not be subroutines in the conventional sense but rather
736:: The "successor" model (named after the successor function of the
419:
machine (RAM) starts with the simplest model of all, the so-called
4007:
An informal Arithmetical Approach to Computability and Computation
3508:
into the destination-register pointed to by the pointer-register r
2081:{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I
3807:
With a few exceptions, these references are the same as those at
2057:
Why is this such an interesting approach? At least two reasons:
2038:
The minimalist approach is to use itself (Schönhage does this).
387:, or just "table", containing execution instructions; the exact
3151:
Case_0 ( the base step of the recursion on y) looks like this:
3725: – it must be indexable with a natural number:
191:
136:
74:
33:
1422:
the address of the register of interest will come from. This
4057:(1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc.
3967:, North-Holland Publishing Company, Amsterdam, Netherlands.
3136:
case_n: IF INC (y), = =n THEN CPY ( rn, φ ), J (exit) ELSE
3130:
case_1: IF INC (y), = =1 THEN CPY ( r1, φ ), J (exit) ELSE
3127:
case_0: IF CLR (y), - =0 THEN CPY ( r0, φ ), J (exit) ELSE
3068:
cases_2 through case_next_to_last: etc. . . . . . . . . ELSE
1302:
RPT that together with CLR (r) and INC (r) can compute any
1254:. If the number of registers exceeds the capability of the
344:. Van Emde Boas (1990) calls these three together with the
3947:
Introduction to Automata Theory, Languages and Computation
897:
Action on finite state machine's Instruction Register, IR
782:
Action on finite state machine's Instruction Register, IR
671:
Action on finite state machine's Instruction Register, IR
4028:(3). The Annals of Mathematics, Vol. 74, No. 3: 437–455.
3572:
and an additional address register with current contents
2613:
1407:
Unbounded indirection and the partial recursive functions
1341:
Bounded indirection and the primitive recursive functions
348:, "sequential machine" models, to distinguish them from "
4121:
Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.
3352:
If the CASE could continue ad infinitum it would be the
3721:
mean that whatever number the model expands to must be
2206:
Action on finite state machine Instruction Register IR
2142:
the machine/model "trigger an event" of our choosing).
157:
4149:, "Machine Models and Simulations" pp. 3–66, in:
4119:
Die Universalität programmgesteuerter Rechenmaschinen.
1631:
will result in 8 varieties, for example the addition:
1227:
of registers versus bounded state-machine instructions
960:
Creating "convenience instructions" from the base sets
340:, the RA-machine and RASP-machine models are used for
1350:) – both total and partial varieties.
3360:) or its table has run out of instructions; it is a
2992:
RASP using this indirect CPY can only calculate the
3905:, Journal of Computer Systems Science 7(4):354-375.
321:or RASP-machine. It is an example of the so-called
152:
may be too technical for most readers to understand
4173:A Variant to Turing's Theory of Computing Machines
4050:
3594:, k is a constant, an explicit number such as "47"
968:Moreover, from base sets 1, 2, or 3 we can create
4090:Eine Abstrakte programmgesteuerte Rechenmaschine'
3139:case_n+1 to case_last: IF . . . THEN . . . ELSE
3133:case_2 through case n: IF . . . THEN . . . ELSE
1168:Cook and Reckhow (1973) say it most succinctly:
2126:Turing equivalence of the RAM with indirection
2113:{ ERASE, PRINT, CLRN, RIGHT, LEFT, JZ (i, N, I
3791:"From Register Machines to Brainfuck, part 1"
3458:, the registers can be the same or different:
3426:, the registers can be the same or different;
1509:0* + 1*4 = 4 = destination-register address 4
1492:0* + 1*4 = 4 = destination-register address 4
8:
3532:copy "the input" into destination register r
1526:1* + 0*4 = = destination-register address 2
3113:copies the contents of this register to φ:
2023:The notion of indirect address register "N"
68:Learn how and when to remove these messages
3915:, McGraw-Hill Book Company, Inc. New York.
3885:Computer Structures: Readings and Examples
3823:Computer Structures: Readings and Examples
3340:how do we handle an out-of-bounds attempt?
2823:IF N =r3] =0 THEN "end" → IR else +1 → IR
2741:IF N =r3] =0 THEN "end" → IR else +1 → IR
2157:
2069:(2) Reduce a RAM to a Post-Turing machine:
2061:(1) An instruction set with no parameters:
4053:Computation: Finite and Infinite Machines
3949:, 1st ed., Reading Mass: Addison-Wesley.
360:An RA-machine consists of the following:
325:and is closest to the common notion of a
253:Learn how and when to remove this message
235:Learn how and when to remove this message
180:Learn how and when to remove this message
164:, without removing the technical details.
125:Learn how and when to remove this message
3504:. Copy the contents of source register r
1795:
1523:0* + 1*3 = 3 = source-register address 3
1506:0* + 1*3 = 3 = source-register address 3
1316:Design our machine/model with unbounded
884:
769:
658:
293:. The RA-machine is very similar to the
88:This article includes a list of general
3851:Computability and Logic: Fourth Edition
3781:
3435:will double the contents of register A.
1489:1* + 0*3 = = source-register address 5
1401:Chapter XII Partial Recursive Functions
4112:Graphschemata und rekursive Funktionen
3887:, mcGraw-Hill Book Company, New York.
3825:, McGraw-Hill Book Company, New York.
3545:copy the contents of source register r
3104:Kleene require that the "predicates" Q
1920:CPY ( d, A, d, r2 ) = CPY ( , , d, r2)
2616:=r4] =0 THEN "end" → IR else +1 → IR
1917:CPY ( d, r2, d, A ) = CPY (d, r2, , )
492:continues to be 38, now the same as .
162:make it understandable to non-experts
7:
4079:Computability of Recursive Functions
3555:
1055:{ CLR (r), DEC (r), INC (r), CPY ( r
713:IF = 0 THEN z → IR ELSE + 1 → IR
578:Refresher: The counter-machine model
319:random-access stored-program machine
4065:Very Simple Bases for Computability
4061:Models Similar to Digital Computers
3903:Time-bounded random access machines
3167:CLR ( y ) ; set register y = 0
939:IF = THEN z → IR ELSE + 1 → IR
824:IF = THEN z → IR ELSE + 1 → IR
309:The RA-machine's equivalent of the
502:instruction is one that specifies
207:tone or style may not reflect the
94:it lacks sufficient corresponding
25:
3993:How to Program an Infinite Abacus
3913:Computability & Unsolvability
3679:(C), JAZ ( z ): = 0 then go to I
3622:JEA ( r, z ) ; IF = then I
867:Equals the contents of register r
752:Equals the contents of register r
395:one special register called the "
342:computational complexity analysis
49:This article has multiple issues.
4157:, The MIT PRESS/Elsevier, 1990.
3789:Érdi, Gergő (6 September 2010).
3604:LDA ( i, r ) ; ] → A ;
3556:Schönhage's RAM0 and RAM1 (1980)
558:Definition: The contents of the
547:Definition: The contents of the
217:guide to writing better articles
196:
141:
79:
38:
3997:Introduction to Metamathematics
3991:(1961, received 15 June 1961),
3983:The Art of Computer Programming
3965:Introduction to Metamathematics
3610:STA ( d, r ) ; → r ;
3598:LDA ( d, r ) ; → A ;
655:continue to next instruction }:
644:contents of register r is Zero
57:or discuss these issues on the
4077:(1961) received December 1961
4059:In particular see chapter 11:
4011:Canadian Mathematical Bulletin
4005:(1961, received 15 May 1961),
3901:and Robert A. Reckhow (1973),
3770:Random Access Machine Emulator
3765:Random Access Machine Emulator
3760:Random Access Machine Emulator
3616:STA ( i, r ) ; → ;
3490:into the destination register.
2150:,i, N), JZ ( i, r, z ), HALT }
1088:Example of indirect addressing
350:parallel random-access machine
1:
4137:Storage Modification Machines
4133:Storage Modification Machines
3875:, reprinted pp. 92ff in
2994:primitive recursive functions
1776:The notion of "accumulator A"
1535:The indirect COPY instruction
1355:primitive recursive functions
1320: – provide an
1138:and thus compute any partial
974:primitive recursive functions
4141:Theoretical Computer Science
4114:, Dialectica 12 (1958), 373.
3819:Institute for Advanced Study
3684:; ambiguous in his treatment
2002:), CLRA, INCA, DECA, ADDA (r
1627:and a destination register r
1520:Example: CPY ( 0, 3, 1, 4 )
1503:Example: CPY ( 0, 3, 0, 4 )
1304:primitive recursive function
540:Definition: The contents of
3124:φ (q, r0, ..., rlast, y) =
1314:The solution in a nutshell:
459:is a location with both an
313: – with its
4205:
3631:INCA ; + 1 --> A
2970:"Besides a merely being a
1552:A plethora of instructions
894:Action on register(s) "r"
881:goto to next instruction }
779:Action on register(s) "r"
766:goto to next instruction }
668:Action on register(s) "r"
555:of the "target" register.
26:
1096:Example: A treasure hunt.
504:in the instruction itself
411:Introduction to the model
3592:LDA k ; k --> A
2996:, not the full suite of
1239:von Neumann architecture
1231:Universal Turing machine
1083:The "indirect" operation
372:"; each register has an
323:von Neumann architecture
311:universal Turing machine
289:in the general class of
27:Not to be confused with
3576:(initially 0)" (p. 494)
1972:Example: INCA = +1 → A
1878:Incement contents of A
1447:Example: CPY ( indirect
109:more precise citations.
4143:(1979), pp. 36–37
4103:On operator algorithms
4049:Marvin Minsky (1967).
3748:Transdichotomous model
3467:will clear register 3.
3403:will clear register 5.
2998:mu recursive functions
985:mu recursive functions
863:contents of register r
748:contents of register r
624:conditional-expression
364:an infinite number of
338:counter-machine models
4022:Annals of Mathematics
2029:unbounded accumulator
1348:ÎĽ-recursive functions
1140:mu recursive function
874:Jump to instruction I
759:Jump to instruction I
648:Jump to instruction I
526:, N ) means directly
438:random-access machine
271:random-access machine
18:Random Access Machine
3855:Abacus Computability
3364:machine, after all.
2203:Action on registers
2027:If our model has an
1928:'s (1973) imaginary
1885:CPY ( d, A, i, r2 )
1843:CPY ( i, r2, d, A )
1375:indirection aka the
1063:), JZ (r, z), JE ( r
571:destination register
508:indirect instruction
446:finite state machine
397:instruction register
356:Informal description
304:Harvard architecture
283:model of computation
29:Random-access memory
4147:Peter van Emde Boas
4071:John C. Shepherdson
3705:Finite vs unbounded
3657:(A), INCA: +1 → A
3118:Definition by cases
3079:, y) is true THEN φ
3057:, y) is true THEN φ
3038:, y) is true THEN φ
3018:Definition by cases
2972:finite set of rules
2495:CPY ( d, E, i, N )
2413:CPY ( d, P, i, N )
2132:Post–Turing machine
4088:Kaphengst, Heinz,
3727:ω is not an option
3618:indirectly store A
3394:, C is any integer
3368:Examples of models
3321:: CPY ( rlast, φ )
3120:CPY (i, q, d, φ) =
2788:JZ ( i, N, halt )
1959:CPY ( d, A, d/i, r
626:in the form of an
332:Together with the
285:that describes an
4189:Register machines
3667:(A), LDAA: ] → A
3662:(N), CPYAN: → N
3652:(Z), CLRA: 0 → A
3606:indirectly load A
2951:
2950:
2706:JZ ( i, N, end )
2577:JZ ( i, N, end )
1903:
1902:
1392:Turing equivalent
1136:Turing equivalent
957:
956:
842:
841:
731:
730:
455:By definition: A
432:Formal definition
415:The concept of a
385:instruction table
291:register machines
263:
262:
255:
245:
244:
237:
211:used on Knowledge
209:encyclopedic tone
190:
189:
182:
135:
134:
127:
72:
16:(Redirected from
4196:
4129:Arnold Schönhage
4096:(1959), 366-379.
4063:and chapter 14:
4058:
4056:
4045:
3923:Abraham Robinson
3869:John von Neumann
3865:Herman Goldstine
3809:Register machine
3801:
3800:
3798:
3797:
3786:
3695:
3683:
3674:
3668:
3663:
3658:
3653:
3632:
3627:
3617:
3612:directly store A
3611:
3605:
3599:
3593:
3549:to "the output."
3544:
3531:
3521:
3503:
3485:
3481:) ; ] → r
3466:
3457:
3453:) ; - → r
3434:
3425:
3421:) ; + → r
3402:
3393:
2158:
1982:Example: MULA (r
1975:Example: ADDA (r
1909:INC ( A ) = INCA
1796:
1432:pointer-register
1188:: The so-called
885:
770:
659:
615:register machine
569:Definition: The
560:pointer register
549:pointer register
518:Example: COPY (
366:memory locations
287:abstract machine
267:computer science
258:
251:
240:
233:
229:
226:
220:
219:for suggestions.
215:See Knowledge's
200:
199:
192:
185:
178:
174:
171:
165:
145:
144:
137:
130:
123:
119:
116:
110:
105:this article by
96:inline citations
83:
82:
75:
64:
42:
41:
34:
21:
4204:
4203:
4199:
4198:
4197:
4195:
4194:
4193:
4179:
4178:
4151:Jan van Leeuwen
4048:
4034:10.2307/1970290
4016:
3899:Stephen A. Cook
3847:Richard Jeffrey
3843:John P. Burgess
3805:
3804:
3795:
3793:
3788:
3787:
3783:
3778:
3756:
3739:
3707:
3702:
3693:
3682:
3678:
3673:(S), STAN: →
3672:
3666:
3661:
3656:
3651:
3630:
3625:
3621:
3615:
3609:
3603:
3600:directly load A
3597:
3591:
3562:pointer machine
3558:
3548:
3542:
3538:
3535:
3529:
3525:
3519:
3515:
3511:
3507:
3501:
3497:
3493:
3489:
3484:
3480:
3476:
3472:
3465:SUB ( 3, 3, 3 )
3464:
3456:
3452:
3448:
3444:
3440:
3433:ADD ( A, A, A )
3432:
3424:
3420:
3416:
3412:
3408:
3400:
3392:
3388:
3384:
3375:
3370:
3359:
3123:
3107:
3093:
3082:
3074:
3071:case_last: IF Q
3060:
3052:
3041:
3033:
2956:
2703:jump_if_blank:
2149:
2128:
2120:
2116:
2104:
2100:
2088:
2084:
2025:
2017:
2013:
2009:
2005:
2001:
1997:
1985:
1978:
1962:
1958:
1954:
1947:
1943:
1939:
1778:
1766:
1762:
1758:
1751:
1747:
1743:
1736:
1732:
1728:
1721:
1717:
1713:
1706:
1702:
1698:
1691:
1687:
1683:
1676:
1672:
1668:
1661:
1657:
1653:
1640:
1630:
1626:
1622:
1614:
1610:
1606:
1602:
1595:
1591:
1587:
1580:
1576:
1572:
1565:
1561:
1546:
1542:
1537:
1474:
1462:
1458:
1454:
1450:
1409:
1343:
1298:He offers us a
1276:Gödel numbering
1160:
1156:
1131:
1090:
1085:
1070:
1066:
1062:
1058:
1008:
962:
933:JE (r1, r2, z)
877:
870:
866:
858:
854:
818:JE (r1, r2, z)
762:
755:
751:
651:
580:
564:target register
542:source register
442:counter machine
434:
421:counter machine
413:
389:instruction set
358:
346:pointer machine
295:counter machine
259:
248:
247:
246:
241:
230:
224:
221:
214:
205:This article's
201:
197:
186:
175:
169:
166:
158:help improve it
155:
146:
142:
131:
120:
114:
111:
101:Please help to
100:
84:
80:
43:
39:
32:
23:
22:
15:
12:
11:
5:
4202:
4200:
4192:
4191:
4181:
4180:
4177:
4176:
4166:
4144:
4125:
4124:
4123:
4122:
4115:
4106:
4097:
4083:
4082:
4068:
4046:
4014:
4000:
3989:Joachim Lambek
3986:
3976:
3961:Stephen Kleene
3958:
3943:Jeffrey Ullman
3936:
3930:
3916:
3906:
3896:
3858:
3836:
3835:
3834:
3803:
3802:
3780:
3779:
3777:
3774:
3773:
3772:
3767:
3762:
3755:
3754:External links
3752:
3751:
3750:
3745:
3738:
3735:
3731:
3730:
3706:
3703:
3701:
3698:
3690:
3689:
3688:
3687:
3686:
3685:
3680:
3676:
3670:
3664:
3659:
3654:
3638:
3637:
3636:
3635:
3634:
3633:
3628:
3623:
3619:
3613:
3607:
3601:
3595:
3578:
3577:
3557:
3554:
3553:
3552:
3551:
3550:
3546:
3540:
3536:
3533:
3527:
3523:
3517:
3513:
3509:
3505:
3499:
3495:
3491:
3487:
3482:
3478:
3474:
3469:
3468:
3460:
3459:
3454:
3450:
3446:
3442:
3437:
3436:
3428:
3427:
3422:
3418:
3414:
3410:
3405:
3404:
3396:
3395:
3390:
3389:) ; C → r
3386:
3374:
3371:
3369:
3366:
3357:
3350:
3349:
3348:
3347:
3341:
3334:
3333:
3332:
3331:
3330:
3329:
3322:
3313:
3312:
3305:
3298:
3292:
3291:
3279:
3278:
3277:
3276:
3269:
3268:
3267:
3266:
3265:
3264:
3257:
3248:
3247:
3240:
3233:
3227:
3226:
3214:
3213:
3212:
3211:
3204:
3203:
3202:
3201:
3200:
3199:
3192:
3183:
3182:
3175:
3168:
3162:
3161:
3149:
3148:
3147:
3146:
3145:default: woops
3143:
3140:
3137:
3134:
3131:
3128:
3121:
3105:
3102:
3101:
3100:
3099:
3091:
3088:
3080:
3072:
3069:
3066:
3058:
3050:
3047:
3039:
3031:
3003:
3002:
2983:
2982:
2976:
2975:
2955:
2952:
2949:
2948:
2945:
2942:
2940:
2938:
2935:
2932:
2930:
2928:
2926:
2924:
2921:
2918:
2915:
2913:
2910:
2907:
2904:
2903:
2901:
2899:
2897:
2895:
2893:
2891:
2889:
2887:
2885:
2883:
2881:
2879:
2877:
2875:
2873:
2871:
2868:
2867:
2865:
2863:
2861:
2859:
2856:
2853:
2851:
2849:
2847:
2845:
2842:
2839:
2836:
2834:
2831:
2828:
2825:
2824:
2821:
2818:
2816:
2814:
2811:
2808:
2806:
2804:
2802:
2800:
2797:
2794:
2791:
2789:
2786:
2785:jump_if_mark:
2783:
2779:
2778:
2776:
2774:
2772:
2770:
2768:
2766:
2764:
2762:
2760:
2758:
2756:
2754:
2752:
2750:
2748:
2746:
2743:
2742:
2739:
2736:
2734:
2732:
2729:
2726:
2724:
2722:
2720:
2718:
2715:
2712:
2709:
2707:
2704:
2701:
2697:
2696:
2694:
2692:
2690:
2688:
2686:
2684:
2682:
2680:
2678:
2676:
2674:
2672:
2670:
2668:
2666:
2664:
2661:
2660:
2658:
2655:
2653:
2651:
2648:
2645:
2643:
2641:
2639:
2637:
2634:
2631:
2628:
2626:
2623:
2621:
2618:
2617:
2610:
2607:
2605:
2603:
2600:
2597:
2595:
2593:
2591:
2589:
2586:
2583:
2580:
2578:
2575:
2572:
2568:
2567:
2565:
2563:
2561:
2559:
2557:
2555:
2553:
2551:
2549:
2547:
2545:
2543:
2541:
2539:
2537:
2535:
2532:
2531:
2528:
2525:
2523:
2521:
2518:
2515:
2513:
2511:
2509:
2507:
2504:
2501:
2498:
2496:
2493:
2490:
2486:
2485:
2483:
2481:
2479:
2477:
2475:
2473:
2471:
2469:
2467:
2465:
2463:
2461:
2459:
2457:
2455:
2453:
2450:
2449:
2446:
2443:
2441:
2439:
2436:
2433:
2431:
2429:
2427:
2425:
2422:
2419:
2416:
2414:
2411:
2408:
2404:
2403:
2401:
2399:
2397:
2395:
2393:
2391:
2389:
2387:
2385:
2383:
2381:
2379:
2377:
2375:
2373:
2371:
2368:
2367:
2364:
2361:
2359:
2357:
2354:
2351:
2349:
2347:
2345:
2343:
2340:
2337:
2334:
2332:
2329:
2326:
2322:
2321:
2319:
2317:
2315:
2313:
2311:
2309:
2307:
2305:
2303:
2301:
2299:
2297:
2295:
2293:
2291:
2289:
2286:
2285:
2283:
2281:
2279:
2277:
2274:
2271:
2269:
2267:
2265:
2263:
2260:
2257:
2254:
2252:
2250:
2247:
2244:
2243:
2241:
2239:
2237:
2235:
2233:
2231:
2229:
2227:
2225:
2223:
2221:
2219:
2217:
2215:
2213:
2211:
2208:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2178:
2175:
2172:
2169:
2167:
2165:
2162:
2152:
2151:
2147:
2127:
2124:
2123:
2122:
2118:
2114:
2107:
2106:
2102:
2098:
2091:
2090:
2086:
2082:
2055:
2054:
2051:
2024:
2021:
2020:
2019:
2015:
2011:
2007:
2003:
1999:
1998:), STA (i/d, r
1995:
1988:
1987:
1983:
1980:
1976:
1973:
1965:
1964:
1960:
1956:
1952:
1949:
1945:
1941:
1937:
1922:
1921:
1918:
1911:
1910:
1901:
1900:
1897:
1894:
1891:
1888:
1886:
1883:
1880:
1879:
1876:
1873:
1870:
1867:
1865:
1862:
1859:
1858:
1855:
1852:
1849:
1846:
1844:
1841:
1837:
1836:
1834:
1831:
1828:
1825:
1823:
1821:
1818:
1817:
1814:
1811:
1808:
1805:
1803:
1800:
1790:
1789:
1777:
1774:
1769:
1768:
1764:
1760:
1756:
1753:
1749:
1745:
1741:
1738:
1734:
1730:
1726:
1723:
1719:
1715:
1711:
1708:
1704:
1700:
1696:
1693:
1689:
1685:
1681:
1678:
1674:
1670:
1666:
1663:
1659:
1655:
1651:
1644:
1643:
1642:
1641:
1638:
1628:
1624:
1620:
1617:
1616:
1612:
1608:
1604:
1600:
1597:
1593:
1589:
1585:
1582:
1578:
1574:
1570:
1567:
1563:
1559:
1544:
1540:
1536:
1533:
1532:
1531:
1530:
1529:
1528:
1527:
1524:
1515:
1514:
1513:
1512:
1511:
1510:
1507:
1498:
1497:
1496:
1495:
1494:
1493:
1490:
1481:
1480:
1477:
1476:
1475:
1472:
1465:
1464:
1460:
1456:
1452:
1448:
1430:, or (ii) the
1428:explicit label
1408:
1405:
1388:
1387:
1369:
1368:
1342:
1339:
1296:
1295:
1260:
1259:
1243:
1242:
1219:
1218:
1217:
1216:
1214:state machine.
1199:
1198:
1178:
1177:
1176:
1175:
1164:
1163:
1158:
1154:
1130:
1127:
1112:
1111:
1110:
1109:
1106:
1103:
1097:
1089:
1086:
1084:
1081:
1073:
1072:
1068:
1064:
1060:
1056:
1046:
1045:
1044:
1043:
1036:
1035:
1034:
1033:
1026:
1020:
1019:
1009:
1006:
1000:
961:
958:
955:
954:
951:
948:
945:
941:
940:
937:
934:
931:
930:Jump if Equal
927:
926:
923:
920:
917:
913:
912:
909:
906:
905:COPY (r1, r2)
903:
899:
898:
895:
892:
889:
883:
882:
875:
868:
864:
856:
852:
840:
839:
836:
833:
830:
826:
825:
822:
819:
816:
815:Jump if Equal
812:
811:
808:
805:
802:
798:
797:
794:
791:
788:
784:
783:
780:
777:
774:
768:
767:
760:
753:
749:
729:
728:
725:
722:
719:
715:
714:
711:
708:
705:
701:
700:
697:
694:
691:
687:
686:
683:
680:
677:
673:
672:
669:
666:
663:
657:
656:
649:
611:
610:
604:
603:
594:Turing machine
588:
587:
579:
576:
562:points to the
538:
537:
536:
535:
498:Definition: A
496:
495:
494:
493:
486:
485:
484:
483:
476:
475:
472:
433:
430:
412:
409:
401:
400:
393:
381:
378:natural number
357:
354:
334:Turing machine
261:
260:
243:
242:
204:
202:
195:
188:
187:
149:
147:
140:
133:
132:
87:
85:
78:
73:
47:
46:
44:
37:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4201:
4190:
4187:
4186:
4184:
4174:
4170:
4167:
4164:
4163:0-444-88071-2
4160:
4156:
4152:
4148:
4145:
4142:
4138:
4134:
4130:
4127:
4126:
4120:
4117:Hermes, Hans
4116:
4113:
4110:
4107:
4104:
4101:
4100:Ershov, A. P.
4098:
4095:
4091:
4087:
4086:
4085:
4084:
4080:
4076:
4075:H. E. Sturgis
4072:
4069:
4066:
4062:
4055:
4054:
4047:
4043:
4039:
4035:
4031:
4027:
4023:
4019:
4018:Marvin Minsky
4015:
4012:
4008:
4004:
4001:
3998:
3994:
3990:
3987:
3984:
3980:
3977:
3974:
3973:0-7204-2103-9
3970:
3966:
3962:
3959:
3956:
3955:0-201-02988-X
3952:
3948:
3944:
3940:
3939:John Hopcroft
3937:
3934:
3931:
3928:
3924:
3920:
3917:
3914:
3910:
3907:
3904:
3900:
3897:
3894:
3893:0-07-004357-4
3890:
3886:
3882:
3878:
3874:
3870:
3866:
3862:
3859:
3856:
3852:
3848:
3844:
3840:
3839:George Boolos
3837:
3832:
3831:0-07-004357-4
3828:
3824:
3820:
3816:
3815:
3814:
3813:
3812:
3810:
3792:
3785:
3782:
3775:
3771:
3768:
3766:
3763:
3761:
3758:
3757:
3753:
3749:
3746:
3744:
3741:
3740:
3736:
3734:
3728:
3724:
3720:
3716:
3715:
3714:
3712:
3704:
3699:
3697:
3694:LDAA ( ] → )
3677:
3671:
3665:
3660:
3655:
3650:
3649:
3648:
3647:
3646:
3645:
3644:
3642:
3629:
3626:else continue
3620:
3614:
3608:
3602:
3596:
3590:
3589:
3588:
3587:
3586:
3585:
3584:
3582:
3575:
3571:
3567:
3566:
3565:
3563:
3537:
3524:
3514:
3492:
3471:
3470:
3462:
3461:
3439:
3438:
3430:
3429:
3407:
3406:
3401:LOAD ( 0, 5 )
3398:
3397:
3383:
3382:
3381:
3380:
3379:
3372:
3367:
3365:
3363:
3355:
3345:
3342:
3339:
3336:
3335:
3327:
3323:
3320:
3317:
3316:
3315:
3314:
3310:
3306:
3303:
3299:
3296:
3295:
3294:
3293:
3289:
3286:
3285:
3284:
3283:
3282:
3274:
3271:
3270:
3262:
3258:
3256:CPY ( rn, φ )
3255:
3252:
3251:
3250:
3249:
3245:
3241:
3238:
3234:
3231:
3230:
3229:
3228:
3224:
3221:
3220:
3219:
3218:
3217:
3209:
3206:
3205:
3197:
3193:
3191:CPY ( r0, φ )
3190:
3187:
3186:
3185:
3184:
3180:
3176:
3173:
3169:
3166:
3165:
3164:
3163:
3159:
3156:
3155:
3154:
3153:
3152:
3144:
3141:
3138:
3135:
3132:
3129:
3126:
3125:
3119:
3116:
3115:
3114:
3110:
3097:
3090:default: do φ
3089:
3086:
3078:
3070:
3067:
3064:
3056:
3048:
3045:
3037:
3029:
3028:
3027:
3026:
3025:
3023:
3019:
3015:
3013:
3007:
3001:
2999:
2995:
2989:
2988:
2987:
2981:
2978:
2977:
2973:
2969:
2968:
2967:
2965:
2961:
2953:
2946:
2943:
2941:
2939:
2936:
2933:
2931:
2929:
2927:
2925:
2922:
2919:
2916:
2914:
2911:
2908:
2906:
2905:
2902:
2900:
2898:
2896:
2894:
2892:
2890:
2888:
2886:
2884:
2882:
2880:
2878:
2876:
2874:
2872:
2870:
2869:
2866:
2864:
2862:
2860:
2857:
2854:
2852:
2850:
2848:
2846:
2843:
2840:
2837:
2835:
2832:
2829:
2827:
2826:
2822:
2819:
2817:
2815:
2812:
2809:
2807:
2805:
2803:
2801:
2798:
2795:
2792:
2790:
2787:
2784:
2781:
2780:
2777:
2775:
2773:
2771:
2769:
2767:
2765:
2763:
2761:
2759:
2757:
2755:
2753:
2751:
2749:
2747:
2745:
2744:
2740:
2737:
2735:
2733:
2730:
2727:
2725:
2723:
2721:
2719:
2716:
2713:
2710:
2708:
2705:
2702:
2699:
2698:
2695:
2693:
2691:
2689:
2687:
2685:
2683:
2681:
2679:
2677:
2675:
2673:
2671:
2669:
2667:
2665:
2663:
2662:
2659:
2656:
2654:
2652:
2649:
2646:
2644:
2642:
2640:
2638:
2635:
2632:
2629:
2627:
2624:
2622:
2620:
2619:
2615:
2611:
2608:
2606:
2604:
2601:
2598:
2596:
2594:
2592:
2590:
2587:
2584:
2581:
2579:
2576:
2573:
2570:
2569:
2566:
2564:
2562:
2560:
2558:
2556:
2554:
2552:
2550:
2548:
2546:
2544:
2542:
2540:
2538:
2536:
2534:
2533:
2529:
2526:
2524:
2522:
2519:
2516:
2514:
2512:
2510:
2508:
2505:
2502:
2499:
2497:
2494:
2491:
2488:
2487:
2484:
2482:
2480:
2478:
2476:
2474:
2472:
2470:
2468:
2466:
2464:
2462:
2460:
2458:
2456:
2454:
2452:
2451:
2447:
2444:
2442:
2440:
2437:
2434:
2432:
2430:
2428:
2426:
2423:
2420:
2417:
2415:
2412:
2409:
2406:
2405:
2402:
2400:
2398:
2396:
2394:
2392:
2390:
2388:
2386:
2384:
2382:
2380:
2378:
2376:
2374:
2372:
2370:
2369:
2365:
2362:
2360:
2358:
2355:
2352:
2350:
2348:
2346:
2344:
2341:
2338:
2335:
2333:
2330:
2327:
2324:
2323:
2320:
2318:
2316:
2314:
2312:
2310:
2308:
2306:
2304:
2302:
2300:
2298:
2296:
2294:
2292:
2290:
2288:
2287:
2284:
2282:
2280:
2278:
2275:
2272:
2270:
2268:
2266:
2264:
2261:
2258:
2255:
2253:
2251:
2248:
2246:
2245:
2242:
2240:
2238:
2236:
2234:
2232:
2230:
2228:
2226:
2224:
2222:
2220:
2218:
2216:
2214:
2212:
2210:
2209:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2179:
2176:
2173:
2170:
2168:
2166:
2163:
2160:
2159:
2156:
2145:
2144:
2143:
2139:
2135:
2133:
2125:
2112:
2111:
2110:
2096:
2095:
2094:
2080:
2079:
2078:
2076:
2071:
2070:
2066:
2063:
2062:
2058:
2052:
2049:
2048:
2047:
2043:
2039:
2036:
2034:
2030:
2022:
1994:{ LDA (i/d, r
1993:
1992:
1991:
1981:
1974:
1971:
1970:
1969:
1950:
1935:
1934:
1933:
1931:
1927:
1919:
1916:
1915:
1914:
1908:
1907:
1906:
1898:
1895:
1892:
1889:
1887:
1884:
1882:
1881:
1877:
1874:
1871:
1868:
1866:
1863:
1861:
1860:
1856:
1853:
1850:
1847:
1845:
1842:
1840:INCi ( r2 ):
1839:
1838:
1835:
1832:
1829:
1826:
1824:
1822:
1820:
1819:
1815:
1812:
1809:
1806:
1804:
1801:
1798:
1797:
1794:
1787:
1783:
1782:
1781:
1775:
1773:
1754:
1739:
1724:
1709:
1694:
1679:
1664:
1649:
1648:
1647:
1636:
1635:
1634:
1633:
1632:
1598:
1583:
1568:
1557:
1556:
1555:
1553:
1549:
1534:
1525:
1522:
1521:
1519:
1518:
1517:
1516:
1508:
1505:
1504:
1502:
1501:
1500:
1499:
1491:
1488:
1487:
1485:
1484:
1483:
1482:
1478:
1470:
1469:
1467:
1466:
1446:
1445:
1444:
1441:
1437:
1433:
1429:
1425:
1421:
1416:
1414:
1406:
1404:
1402:
1397:
1393:
1386:
1382:
1381:
1380:
1378:
1374:
1367:
1364:
1363:
1362:
1360:
1356:
1351:
1349:
1340:
1338:
1336:
1331:
1327:
1323:
1319:
1315:
1311:
1307:
1305:
1301:
1293:
1292:
1291:
1287:
1285:
1279:
1277:
1273:
1269:
1265:
1257:
1253:
1249:
1245:
1244:
1240:
1236:
1232:
1228:
1226:
1221:
1220:
1215:
1211:
1207:
1203:
1202:
1201:
1200:
1195:
1191:
1187:
1185:
1180:
1179:
1174:
1171:
1170:
1169:
1166:
1165:
1162:
1151:
1145:
1144:
1143:
1141:
1137:
1128:
1126:
1124:
1120:
1116:
1107:
1104:
1101:
1100:
1098:
1095:
1094:
1093:
1087:
1082:
1080:
1078:
1071:, z ), J(z) }
1054:
1053:
1052:
1049:
1041:
1038:
1037:
1031:
1027:
1024:
1023:
1022:
1021:
1017:
1013:
1010:
1004:
1003:
1001:
999:
994:
991:
990:
989:
986:
983:
979:
975:
971:
966:
959:
952:
949:
946:
943:
942:
938:
935:
932:
929:
928:
924:
921:
918:
915:
914:
910:
907:
904:
901:
900:
896:
893:
890:
887:
886:
880:
873:
862:
855:to register r
850:
849:
848:
846:
837:
834:
831:
828:
827:
823:
820:
817:
814:
813:
809:
806:
803:
800:
799:
795:
792:
789:
786:
785:
781:
778:
775:
772:
771:
765:
758:
747:
743:
742:
741:
739:
735:
726:
723:
720:
717:
716:
712:
709:
706:
704:Jump if Zero
703:
702:
698:
695:
692:
689:
688:
684:
681:
678:
675:
674:
670:
667:
664:
661:
660:
654:
647:
643:
639:
638:
637:
635:
631:
629:
625:
620:
616:
609:
606:
605:
602:
597:
595:
590:
589:
586:
582:
581:
577:
575:
572:
567:
565:
561:
556:
554:
550:
545:
543:
533:
529:
525:
521:
517:
516:
514:
513:
512:
509:
505:
501:
490:
489:
488:
487:
480:
479:
478:
477:
473:
470:
469:
468:
466:
462:
458:
453:
451:
447:
443:
439:
431:
429:
427:
422:
418:
417:random-access
410:
408:
406:
398:
394:
390:
386:
382:
379:
375:
371:
367:
363:
362:
361:
355:
353:
351:
347:
343:
339:
335:
330:
328:
324:
320:
316:
312:
307:
305:
300:
296:
292:
288:
284:
280:
276:
272:
268:
257:
254:
239:
236:
228:
225:December 2017
218:
212:
210:
203:
194:
193:
184:
181:
173:
170:December 2017
163:
159:
153:
150:This article
148:
139:
138:
129:
126:
118:
115:December 2017
108:
104:
98:
97:
91:
86:
77:
76:
71:
69:
62:
61:
56:
55:
50:
45:
36:
35:
30:
19:
4172:
4154:
4140:
4136:
4132:
4118:
4111:
4109:PĂ©ter, RĂłzsa
4102:
4093:
4089:
4078:
4064:
4060:
4052:
4025:
4021:
4006:
4003:Z. A. Melzak
3996:
3992:
3982:
3979:Donald Knuth
3964:
3946:
3933:J. Hartmanis
3926:
3919:Calvin Elgot
3912:
3909:Martin Davis
3902:
3884:
3881:Allen Newell
3872:
3861:Arthur Burks
3854:
3850:
3822:
3806:
3794:. Retrieved
3784:
3732:
3726:
3722:
3718:
3710:
3708:
3691:
3640:
3639:
3580:
3579:
3573:
3569:
3559:
3502:) ; →
3376:
3361:
3351:
3343:
3337:
3325:
3318:
3308:
3301:
3287:
3280:
3272:
3260:
3253:
3243:
3236:
3222:
3215:
3207:
3195:
3188:
3178:
3171:
3157:
3150:
3117:
3111:
3103:
3095:
3084:
3076:
3062:
3054:
3049:case_1: IF Q
3043:
3035:
3030:case_0: IF Q
3021:
3017:
3016:
3011:
3008:
3004:
2990:
2984:
2979:
2971:
2963:
2959:
2957:
2782:J1 ( halt )
2700:J0 ( halt )
2153:
2140:
2136:
2129:
2108:
2092:
2074:
2072:
2068:
2067:
2064:
2060:
2059:
2056:
2044:
2040:
2037:
2032:
2028:
2026:
1989:
1966:
1951:STA ( d/i, r
1944:CPY ( d/i, r
1936:LDA ( d/i, r
1923:
1912:
1904:
1816:Description
1802:Instruction
1793:register A:
1791:
1785:
1779:
1770:
1646:will yield:
1645:
1618:
1551:
1550:
1538:
1471:i* + (1-i)*r
1439:
1435:
1431:
1427:
1423:
1419:
1417:
1412:
1410:
1400:
1396:Gödel number
1389:
1383:
1372:
1370:
1365:
1358:
1352:
1344:
1334:
1325:
1321:
1317:
1313:
1312:
1308:
1299:
1297:
1288:
1283:
1280:
1271:
1267:
1263:
1261:
1255:
1251:
1247:
1224:
1222:
1213:
1209:
1204:
1193:
1189:
1183:
1181:
1172:
1167:
1150:Gödel number
1146:
1132:
1122:
1118:
1113:
1091:
1076:
1074:
1050:
1047:
1039:
1029:
1015:
1011:
996:
992:
981:
977:
969:
967:
963:
888:Instruction
878:
871:
860:
845:Base model 3
844:
843:
773:Instruction
763:
756:
745:
738:Peano axioms
734:Base model 2
733:
732:
707:JZ ( r, z )
662:Instruction
652:
645:
641:
634:Base model 1
633:
632:
628:IF-THEN-ELSE
627:
623:
618:
612:
607:
599:
591:
583:
570:
568:
563:
559:
557:
552:
548:
546:
541:
539:
531:
527:
523:
519:
507:
503:
499:
497:
464:
460:
456:
454:
449:
437:
435:
414:
402:
396:
384:
369:
359:
331:
308:
278:
274:
270:
264:
249:
231:
222:
206:
176:
167:
151:
121:
112:
93:
65:
58:
52:
51:Please help
48:
3877:Gordon Bell
3494:COPY ( d, r
3473:COPY ( i, r
3385:LOAD ( C, r
3354:mu operator
3300:JE ( q, y,
3235:JE ( q, y,
3170:JE ( q, y,
2833:. . . etc.
2820:N =r3] → A
1986:) = * → A
1979:) = + → A
1786:Accumulator
1461:destination
1457:destination
1318:indirection
1115:Indirection
376:which is a
299:main memory
107:introducing
3796:2024-02-07
3776:References
3641:RAM0 model
3581:RAM1 model
3516:JNZ ( r, I
3273:case__n+1:
2625:DEC ( N )
2331:INC ( N )
2014:), DIVA (r
2010:), MULA (r
2006:), SUBA (r
1864:INC ( A )
1755:ADD ( i, r
1740:ADD ( d, r
1725:ADD ( i, r
1710:ADD ( d, r
1695:ADD ( i, r
1680:ADD ( d, r
1665:ADD ( i, r
1650:ADD ( d, r
1377:ÎĽ operator
1359:explicitly
1330:ÎĽ operator
1252:explicitly
1248:explicitly
1223:Unbounded
1184:capacities
1182:Unbounded
919:INC ( r )
916:INCrement
804:INC ( r )
801:INCrement
790:CLR ( r )
693:DEC ( r )
690:DECrement
679:INC ( r )
676:INCrement
352:" models.
279:RA-machine
90:references
54:improve it
3700:Footnotes
3539:PRINT ( r
3463:Example:
3431:Example:
3399:Example:
3297:INC ( y )
3288:case_last
3232:INC ( y )
3087:, y) ELSE
3065:, y) ELSE
3046:, y) ELSE
2527:=0 → =r4
2445:=1 → =r4
2161:Mnemonic
1813:r378,426
1599:CPY (i, r
1584:CPY (d, r
1569:CPY (i, r
1558:CPY (d, r
1413:unbounded
1373:unbounded
1326:unbounded
1322:unbounded
1237:with the
1014:: JZ (r,
1005:CLR (r) =
925:+ 1 → IR
911:+ 1 → IR
891:Mnemonic
810:+ 1 → IR
796:+ 1 → IR
776:Mnemonic
699:+ 1 → IR
685:+ 1 → IR
665:Mnemonic
619:unbounded
405:Brainfuck
370:registers
60:talk page
4183:Category
4171:(1957),
4169:Hao Wang
4131:(1980),
3981:(1968),
3963:(1952),
3945:(1979).
3925:(1964),
3911:(1958),
3883:(1971),
3871:(1946),
3849:(2002),
3743:Real RAM
3737:See also
3543:) ;
3530:) ;
3526:READ ( r
3520:) ;
3244:case_n+1
2947:+1 → IR
2530:+1 → IR
2448:+1 → IR
2366:+1 → IR
2117:), JZ (I
2101:), JZ (I
2085:), JZ (I
2018:), etc.)
1948:, d, A )
1893:378,426
1872:378,426
1851:378,426
1830:378,426
1455:, direct
1436:contents
1235:computer
1134:that is
922:+ 1 → r
807:+ 1 → r
696:- 1 → r
682:+ 1 → r
598:distance
457:register
450:contents
426:computer
368:called "
327:computer
4042:1970290
3564:model:
3441:SUB ( r
3409:ADD ( r
3208:case_1:
3092:default
2962:, i.e.
2960:bounded
2657:-1 → N
2492:erase:
2410:print:
2363:+1 → N
2328:right:
2249:start:
2164:label:
2031:can we
1300:bounded
1284:program
1268:program
1262:So how
1225:numbers
1119:pointer
1028:JZ (0,
1025:DEC (r)
982:partial
972:of the
553:address
551:is the
465:content
461:address
374:address
315:program
281:) is a
156:Please
103:improve
4161:
4153:, ed.
4040:
3971:
3953:
3891:
3829:
3723:finite
3711:finite
3498:, i, r
3477:, d, r
3362:finite
3338:woops:
3319:_φlast
3302:_φlast
3223:case_n
3179:case_1
3158:case_0
3024:, y):
2964:finite
2909:halt:
2574:left:
2121:), H }
2105:), H }
2089:), H }
1827:. . .
1799:Label
1763:, i, r
1759:, i, r
1748:, i, r
1744:, i, r
1733:, i, r
1729:, d, r
1718:, i, r
1714:, d, r
1703:, d, r
1699:, i, r
1688:, d, r
1684:, i, r
1673:, d, r
1669:, d, r
1658:, d, r
1654:, d, r
1637:+ → r
1603:, i, r
1588:, i, r
1573:, d, r
1562:, d, r
1543:and P'
1453:source
1449:source
1434:whose
1390:To be
1256:finite
1212:finite
1208:finite
1190:finite
1123:target
1042:: etc.
995:blocks
793:0 → r
787:CLeaR
500:direct
92:, but
4139:, in
4038:JSTOR
3344:exit:
3309:woops
2944:none
2738:none
2609:none
2200:etc.
2033:bound
1926:Knuth
1424:where
1420:where
1007:equiv
978:total
953:→ IR
950:none
944:Halt
936:none
908:→ r2
902:COPY
838:→ IR
835:none
829:Halt
821:none
727:→ IR
724:none
718:Halt
710:none
522:, A,
4159:ISBN
4073:and
3969:ISBN
3951:ISBN
3921:and
3889:ISBN
3879:and
3827:ISBN
3719:does
3346:etc.
3326:exit
3324:J (
3307:J (
3275:etc.
3261:exit
3259:J (
3254:_φn:
3242:J (
3210:etc.
3196:exit
3194:J (
3189:_φ0:
3177:J (
3098:, y)
3081:last
3073:last
2830:end
1440:also
1411:For
1194:very
1040:exit
1030:loop
1016:exit
1012:loop
980:and
879:ELSE
872:then
764:ELSE
757:THEN
653:ELSE
646:THEN
613:The
383:the
336:and
4030:doi
3449:, r
3445:, r
3417:, r
3413:, r
3237:_φn
3172:_φ0
3122:def
3020:φ (
2612:IF
2197:r5
2194:r4
2191:r3
2188:r2
2185:r1
2182:r0
1957:def
1955:) =
1942:def
1940:) =
1930:MIX
1896:18
1890:18
1875:17
1869:18
1854:17
1848:17
1833:17
1810:r2
1761:sp2
1757:sp1
1746:sp2
1727:sp1
1701:sp2
1697:sp1
1686:sp2
1667:sp1
1459:, r
1451:, r
1385:go?
1335:its
1272:all
1077:Not
1067:, r
1059:, r
970:any
740:):
392:set
306:).
277:or
275:RAM
265:In
160:to
4185::
4036:.
4026:74
4024:.
4009:,
3941:,
3867:,
3863:,
3845:,
3841:,
3833:}.
3811:.
3696:.
3447:s2
3443:s1
3415:s2
3411:s1
2966::
2937:0
2934:1
2923:3
2920:1
2917:0
2912:H
2858:0
2855:1
2844:3
2841:1
2838:0
2813:0
2810:1
2799:3
2796:1
2793:0
2731:0
2728:1
2717:3
2714:1
2711:0
2650:0
2647:1
2636:3
2633:1
2630:0
2602:0
2599:1
2588:4
2585:1
2582:0
2571:L
2520:0
2517:1
2506:4
2503:1
2500:0
2489:E
2438:1
2435:1
2424:4
2421:1
2418:0
2407:P
2356:0
2353:1
2342:4
2339:1
2336:0
2325:R
2276:0
2273:1
2262:3
2259:1
2256:0
2177:N
2174:P
2171:E
1807:A
1765:dp
1750:dp
1742:s1
1735:dp
1731:s2
1720:dp
1716:s2
1712:s1
1682:s1
1671:s2
1656:s2
1652:s1
1625:s2
1621:s1
1613:dp
1609:sp
1605:dp
1601:sp
1594:dp
1590:dp
1579:sp
1571:sp
1379:.
1264:do
1142::
947:H
861:IF
859:,
832:H
746:IF
721:H
642:IF
482:3.
436:A
407:.
329:.
269:,
63:.
4094:5
4044:.
4032::
3999:.
3975:.
3895:.
3799:.
3729:.
3681:z
3624:z
3574:n
3570:z
3547:s
3541:s
3534:d
3528:d
3518:z
3512:.
3510:p
3506:s
3500:p
3496:s
3488:p
3483:d
3479:d
3475:p
3455:d
3451:d
3423:d
3419:d
3391:d
3387:d
3358:2
3328:)
3311:)
3304:)
3290::
3263:)
3246:)
3239:)
3225::
3198:)
3181:)
3174:)
3160::
3106:n
3096:x
3094:(
3085:x
3083:(
3077:x
3075:(
3063:x
3061:(
3059:1
3055:x
3053:(
3051:1
3044:x
3042:(
3040:0
3036:x
3034:(
3032:0
3022:x
3012:x
3000:.
2614:N
2148:s
2119:z
2115:z
2103:z
2099:z
2087:z
2083:z
2075:r
2016:s
2012:s
2008:s
2004:s
2000:d
1996:s
1984:s
1977:s
1963:)
1961:d
1953:d
1946:s
1938:s
1767:)
1752:)
1737:)
1722:)
1707:)
1705:d
1692:)
1690:d
1677:)
1675:d
1662:)
1660:d
1639:d
1629:d
1623:r
1615:)
1596:.
1586:s
1581:.
1575:d
1564:d
1560:s
1545:0
1541:0
1473:s
1463:)
1241:.
1159:0
1155:0
1153:P
1069:k
1065:j
1061:d
1057:s
1032:)
1018:)
876:z
869:k
865:j
857:k
853:j
761:z
754:k
750:j
650:z
532:i
528:d
524:i
520:d
273:(
256:)
250:(
238:)
232:(
227:)
223:(
213:.
183:)
177:(
172:)
168:(
154:.
128:)
122:(
117:)
113:(
99:.
70:)
66:(
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.