1332:, and with spaghetti-code everything can be done. The article should not list lengthy example programs, but give only the code to calculate the predecessor function without using DEC(r), which is short and interesting. Maybe also the code to copy one variable to another without using CPY(m,n). And leave it there. The different models should be given in tabular form, with reference to the literature where found (this information is now in the 'Counter-machine model' article, but not nice and uniform, and very sloppy). Remove also the
416:
406:
388:
2071:" . Kleene's point seems to be that the primitive recursive functions are all elementary and vice versa ... except this: "From this it follows that there are non-elementary primitive recursive predicates..." (p. 272). Kleene refers us back to §55 where he observes: "Ackermann's investigation shows that ℰ(a) grows faster with increasing a than any primitive recursive function of a (just as 2 grows faster than any polynomial in a)...." (cf p. 272).
144:
2090:}. He develops the notions of "computable functions" from this model. Then he develops all the stuff he needs to simulate the "elementary functions" e.g. the "bounded sum Σ" and "bounded product Π", etc. and then he proves that the number 2 is not elementary (at least I think that's what he's doing, am confused here by the weird symbolism, it could be Ackermann's function, or just 2 ... cf "Lemma" on page 59.)
71:
53:
1414:
the unary number in the register is ODD or EVEN, and at the same time it counts UP a second register B to EVEN(N/2). Then depending on the ODD-EVEN outcome it either moves 3*EVEN(N/2)+2 or EVEN*(N/2) back into register A. (Thereby doing the { (3*N+1)/2, N/2 } form of
Collatz). But... a few months ago I ran into (via a bibliography of a Blass-Gurevich paper) a paper by Rich Schroeppel 1972,
1536:
to go take a peek. The impossibility argument can be summarized in a sentence or two: A 2CM that halts must map certain arithmetic progressions in a linear fashion. This is incompatible with most interesting functions like 2^N. The paper spends many pages filling in the details. You might also check with
Frances Yao (nee Chu) who discovered the result at the same time as I did.
22:
1560:
2063:, but remarks that then * and are redundant." (p. 526). Kleene refers us back to his section §57 where he is developing the μ-operator (the unbounded version). In §57 there's an extended example I. "A function is "elementary", if it can be expressed explicitly in terms of variable natural numbers, the constant 1, the functions +, * and and the operations Σ
1838:
Here's a state-machine-like version with 11 instructions (not counting HALT) if you count the "output" instruction that appears at the start. I inserted it so I could see better what was going on. I use Excel to simulate these things. So this one uses this instruction set. "Test" is really just a NOP
1535:
I don't know of a better multiplication algorithm. There hasn't been much work with counter machines, before or since my paper. There has been a fair amount of work on the 3N+1 problem; look up Jeff
Lagarias, who does a review every few years. I didn't know the 1972 paper was on the net; I'll have
2104:
Then, he discusses the class ℰ (script-E) i.e. "those number theoretic functions which can be defined from the initial functions: constant 0, successor S, projections (onto the ith coordinate), addition +, modified subtraction ∸, multiplication * and exponentiation 2, by applications of composition
1413:
I ran into something important with regards to the inadequacies of a 2-counter
Collatz counter-machine. As I noted above I've "built" in less than 16 instructions a two-counter machine that generates Collatz sequences given any starting number. In register A it counts down N by twos to find whether
2279:
Counter automata are a simpler kind of automata, but, while in theory similar structures (a finite state machine with one or more counters), the two have very different applications (counter automata in formal language theory, while counter machines are a study of computer science computations) and
2179:
Out of curiosity I've sketched an algorithm to do
Collatz on the "tag machine" using an algorithm similar to the ones posted above for the counter machine (i.e. divide by two while calculating EVEN(N/2)). (I need to simulate it to check it.) It requires about the same number of instructions (on the
1442:
Given all this, we can conclude that a 2-counter machine, while quite adequate for a single-instance
Collatz sequence (i.e. given a starting N), is insufficient to handle all sorts of computations required for Godelization, given straight-up unary-numerical inputs (i.e. not encoded at the input and
1438:
N, sqrt(N), Fib(N), Smallest_Prime_Factor(N), etc. He comes to the
Collatz question but notes it is unsolved (his 2-counter algorithm seems to be the same as the one I'm using except it is doing {(6)*EVEN(N/2)+(4), N/2} ), i.e. the classical { 3*N+1, N/2 } version. There's a lot more. He notes that
1522:
Did you ever ran into a "better" algorithm for your little challenge to write a multiply program for a 3CM? (I don't have one, but it sounds like a fun challenge. If I can figure your proof out, I may add a brief sketch of it to a wikipedia page titled "Proof of impossibility". Your observation
1433:
A Corollary is that a 2-counter machine can compute any partial recursive function if its input is coded 2 and its output is encoded as 2 (I think this is in Minsky). He goes on to his major proof ("given N, a two-counter machine cannot compute 2") and then adds more corollaries: that no 2-counter
833:
Indirect addressing must be dealt with. Any instruction can be turned into an indirect, even an unconditional jump. Here S denotes "Source-"register and "D" denotes "Destination-"register, A denotes accumulator or any other special register, "i" (or "iD", "iS") denotes "indirect", "d"= NOT(i) (or
507:
Is this a good idea? Others have tried to do something like this on wikipedia for a computer "pseudocode" and failed. They gave it up. We will just end up in argument. Do the mnemonics really matter? For example, I usually use D ("Down") for "Decrement" and U ("Up") for "Increment". But I changed
1327:
article should be merged into the 'Counter-machine' article, and deleted. To not overload the article one should remove the discussion of the Turing-equivalence, and just mention that counter machines can compute all computable functions . Which by the way is obvious, as counter machines allow
1505:
I agree with your interpretation. But there are complications ... There's more I want to write about this but it got complicated and I ran out of time. I'll go away and draw something and think about this. (See the email I sent
Schroeppel back on ~1 Aug and his response, below.)
165:
2054:
The following touches on my cryptic note and the 2 business. I don't understand it yet. In the back of Kleene 1952 p. 526 under the bibliographic reference for Laszlo Kalmar, is a note: "Kalmar takes, as his basis for elementary functions the variables, 1, +, *, |a-b|, ,
908:
indicates indirect addressing. But the "i" and "d" are pretty good because they act like parameters too. And they are
Boolean (i.e. for example, perhaps "i"=1, "d"=0). I have simulated this on a spreadsheet recently -- all four parameters describe the functions nicely.
2255:
page gives "counter machine" as a synonym, so there's no reason for two separate pages. (But maybe a "counter automaton" is a subset of "counter machine" with just one register? The page is unclear.) Moreover, "Counter automaton" is mostly a stub. Finally, the
1574:
Bill, I hope this move of the material is satisfactory. You wrote "But there are complications ... There's more I want to write about this" — I'm interested in what those complications might be. BTW, using Minsky's 2CM from his book
1512:
In a 2007 paper by
Derschowitz and Gurevich I ran into a citation to your 1972 paper (that you wrote while at the MIT AI labs) called "A Two Counter Machine Cannot Calculate 2^N". I was then able to download it off the
1477:
for a rather elaborate (unsurprisingly "obscure") coding that simulates the configuration of a UTM by means of a Gödel number, whose factorization is of form 235, in one of the registers. Although that might raise
1099:
1 CLR(rY) 9 JZ (rW,13) 2 CLR(rW) 10 INC(rX) 3 JZ (rX,8) 11 DEC(rW) 4 INC(rY) 12 J (9) 5 INC(rW) 13 CONTINUE 6 DEC(rX) 7 J (3) 8 ??
189:
468:
329:
1473:. (It's only on the basis of this inadequate i/o convention that he claims a 2CM "can't calculate" 2.) But the inadequacy is not surprising, as 2CMs were proved universal (by Minsky)
2337:
111:
1443:
output as Goedel numbers). I'm sure this has a bearing on what you've reported, but I don't know quite what it is (and suspect I don't have the know-how to figure it out). Bill
834:"dD", "dS") denotes direct. We might have to use e.g. "c" or "k" or something for "immediate constant", where "func" is some 2-parameter function such as ADD or COPY or INC r:
246:
184:
1579:, 1967), I can get an 11-instruction Collatz program, but I think it's probably just the one you have, but placing goto info in the increment instruction (as Minsky did). --
2306:: I'm convinced by your explanation that counter automata are for formal language theory while counter machines are for models of computation. I withdraw my merge support.
902:
The reason I have not used parenthesis is because the assemblers I have used for microcontrollers do not use them. But maybe parentheses are okay, like a function in EXCEL.
117:
2352:
2342:
462:
1594:
Here's one version with instruction set { INC(r), DCR(r), jZ(A,addr); j(addr) } thus it assumes that instructions are executed in sequence unless a jump occurs.
545:" means "constant k replaces contents of rS." I have also seen used in a similar way in a textbook (Boolos-Burgess-Jeffrey 2002). Except they write " → rD".
87:
2332:
291:
2119:
that tag machines are more powerful that what we need for a Collatz sequence (can a tag machine calculate 2 given N encoded as unary on its tape ??),
2082:, Schwichtenberg starts with the notion of "register machines" (aka counter machines) with three instructions { zero(x); Successor(x); IF x=y THEN I
265:
2198:
I've replied to some of your questions about tag machines, including "can a tag machine calculate 2 given N encoded as unary on its tape??" at
438:
130:
78:
58:
2347:
1419:
354:
2097:
includes "the variables", the constants 0 and 1, addition +, "modified" (proper) subtraction ∸ and bounded sums and product. He defines as
2229:
237:
2294:
1386:
429:
393:
218:
930:{ LDA r; STA r; INCA; DECA; CLRA; CPYAN (copy accum to address pointer/iNdex register; ADA r (ADD (r,A)), etc., etc. } wvbailey
310:
1430:
And by this he means 2*3*5*7, where a 4-counter machine made of counters W, X, Y, Z is simulated by the two-counter machine.
1439:
Frances Yao independently proved the major theorem in April 1971, and he claims his proof was discovered in September 1970.
1428:
Any counter machine can be simulated by a 2-counter machine, provided an obscure coding is accepted for the input and output.
2180:
order of 20) as the counter machine. I would not be surprised to find out that it can be "morphed" into the tag-algorithm.
1523:
about the Collatz Conjecture/Ulam problem really caught my eye; that problem is mentioned there too as an "open" problem).
275:
156:
33:
825:
With the "referential library" (RefLib), the "referential model" can implement ALL other instruction sets from similar
957:
to expand the RefLib script templates into standard instructions. The scripts are for explaination and demonstration.
517:
285:
199:
1299:
1279:
The CONTINUE instruction is a "template instruction" for continuing into the context where the RefLib will be used.
503:
To fix a "standard style" (and reader "see the same as the same") for the algorithms and examples into the articles.
320:
86:
related articles on Knowledge. If you would like to participate, please visit the project page, where you can join
347:
1842:{ INC(r,address_if_0,address_if_1); DCR(r,address_if_0,address_if_1); TEST(r,address_if_0,address_if_1); HALT }
512:
computer, they are common, as is CLR and CPY. Some folks use DCR for decrement. What is really important is to
1115:
1 CPY(rX,r) 6 JZ(r0,3) 2 CPY(rY,rW) 7 JZ(rW,9) 3 JZ(r,7) 8 INC(r) 4 DEC(r) 9 CONTINUE 5 DEC(rW)
2233:
529:
Also, if I had a choice I would prefer to use the authors' original mnemonics, rather than a standard set.
2290:
2257:
1374:
1312:
article with style (tables) and examples compatible with the recommendations fixed (to be consensus) here.
2311:
2269:
1337:
1323:
923:
models (ex. with stack or accumulator) may be fix, with simple changes, different "referential models".
256:
39:
1458:
Here's my take on Schroeppel's paper: I see it primarily as showing that what he so readily accepts as
1336:, because those are only beauty-problems. This information can be given elsewhere, for instance in the
415:
2149:
A weaker but Collatz-capable machine (that cannot calculate 2 given N encoded as unary on its tape),
942:
The "referential library" is a sinple list of "new instructions" implementarions, they may be see as
2225:
1357:
2202:. I prefer to avoid detailed discussion of tag machines here (or of counter machines over there). --
21:
1467:
that the argument and computed value of a function are just the numbers stored in certain registers
1392:
Sorry, but the above is bogus. I am sticking with the convention in Boolos-Burgess-Jeffrey (2002)
1276:
indicates direct addressing; k indicates immediate adddressing (constant derived from instruction)
437:
on Knowledge. If you would like to participate, please visit the project page, where you can join
2188:
2045:
1828:
1550:
1448:
421:
405:
387:
950:
strategy: each similar model with a different instruction set may be "emulated" by the RefLib.
2281:
2264:. (There wasn't a section on the talk page to discuss the merge proposal, so I created one.))
2252:
692:
175:
2222:
What does DEC(r) do if register r contains zero? This doesn't seem to be defined anywhere.
2115:
I guess all that my cryptic comment was, was this (it was lost when my Excel froze): that it
516:
in more primitive terms (somehow) before you use them in the text. This is touched on in the
2307:
2265:
2207:
1584:
1495:
1490:
i/o scheme, it may be able to compute some, but not necessarily all, recursive functions. --
920:
826:
549:
227:
83:
2199:
1407:
1317:
1309:
2261:
1418:
MIT A.I. Laboratory, Artifical Intelligence Memo #257. This is available on the web at
1329:
954:
301:
143:
166:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
2326:
2184:
2041:
1824:
1567:
1546:
1444:
1397:
931:
910:
553:
521:
1426:
counter machine can simulate a Turing machine, what he is really after here is that
848:
func( d, rs, d, rD) e.g. CPY (rS,rD), INC (d,r,d,r) = INC r; DEC (d,r,d,r)= DEC r
2203:
1580:
1491:
927:
I have not seen a stack in any models. Some other accumulator instructions are:
544:
then you can write, for immediate constants, "k → rS" or better "k → <rS: -->
508:
them because they are easier to remember as DEC and INC, Knuth used them in his
434:
953:
The scripts are "near to formal". For formal ones we can imagine the use of a
411:
1530:
The DG2007 paper has the most illustrious bibliography I've ever appeared in.
520:
article. See the four-variable table of "func(i/d,rS,i/d,rD)" below. wvbailey
2112:
All this is probably in Minsky's text but I haven't looked back at it yet.
943:
208:
2260:
has been proposed since 2021 without objection, so I'd say go ahead and be
1559:
1471:
is not adequate for universality in a CM with insufficiently-many registers
70:
52:
1282:
A convention may be to fix a "reserved register" for use as rW (wasting).
2183:
I have no idea where this is leading. I'm just following the scent. Bill
947:
730:
10 DEC (2) 20 JZ (2,50) 30 INC (1) 40 JZ (0,10) 50 HALT
2315:
2298:
2273:
2237:
2211:
2192:
2049:
1832:
1588:
1554:
1499:
1452:
1400:
934:
913:
556:
524:
1083:
1 CLR(rY) 2 JZ (rX,6) 3 INC(rY) 4 DEC(rX) 5 J (2) 6 CONTINUE
2280:
the articles appear to show them from these different points of view.
703:
The simplest and ease to write (using wiki "#" mark for auto-addres):
1161:
EXPonential, r=rX**rY; perhaps preserving the contents of rX and rY.
1558:
893:
func( d, A, k) e.g. LDA k; ADDA k; SUBA k; etc. CPY (d,k,A)= LDA k
1175:
SUBtract, r=rX-rY; perhaps preserving the contents of rX and rY.
1147:
MULtiply, r=rX*rY; perhaps preserving the contents of rX and rY.
605:. Each of the instructions in this list is one of the following:
566:" (for wikipedia articles) consists of a finite set of registers
1839:
or Turing "N", but it specifies a register to test for 0 or 1:
509:
284:
Find pictures for the biographies of computer scientists (see
15:
1420:
ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-257.pdf
691:
Here we can fix "(for articles) standards". They are like on
1881:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1394:
because it is a convention to be found in a published text
1119:
Compare rX with rY and returns on r (r=0 if rX equal rY).
987:
Go to i (unconditional jump); register #0 must contain 0.
905:
I find the following is much more expressive: <rS: -->
881:
func( i, A, i, A) e.g. LDAiA (this is used by Schonhage!)
552:, perhaps on a separate page if it gets too big. wvbailey
1133:
r=rX+rY; perhaps preserving the contents of rX and rY.
738:
For a better layout and OPTIONAL use of "goto labels":
1263:
Indirect copy Source contents to indirect Destination
1158:... in terms of JZ, DEC, J, CLR, INC, CPY, ADD, MUL.
842:
func( d, rs, i, rD) e.g. CPY (d, A, i, rD) = STAi rD,
1848:
1600:
878:
func( d, A, d, A) e.g. INCA, DECA, CLRA, LDAA = nop,
589:=0 (always zero), and a finite list of instructions
433:, a collaborative effort to improve the coverage of
82:, a collaborative effort to improve the coverage of
1845:
1597:
467:This article has not yet received a rating on the
190:Computer science articles needing expert attention
116:This article has not yet received a rating on the
582:, each of which can hold a non-negative integer,
1144:... in terms of JZ, DEC, J, CLR, INC, CPY, ADD.
1103:Copy rX into rY, rW must be free (at end rW=0).
2078:. In a book on line by Helmut Schwichtenberg,
906:means "contents of register S", <<rS: -->
857:func( d, A, i, rD) e.g. STAi rD CPY (<A: -->
695:articles. There are optional "clean styles".
548:The "RefTable", if used, probably should go on
543:means "contents of". If you write < rS : -->
2105:and bounded minimization." (p. 60). It is the
1482:issues, all recursive functions are certainly
1201:LoaDA; special register called "accumulator"
687:Algorithm presentation style (scripting style)
330:WikiProject Computer science/Unreferenced BLPs
8:
2338:Unknown-importance Computer science articles
2101:as those which omit the bounded product.
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1817:
1814:
1812:
1810:
1807:
1804:
1802:
1799:
1797:
1795:
1793:
1790:
1788:
1786:
1783:
1781:
1778:
1776:
1769:
1767:
1764:
1761:
1758:
1756:
1753:
1750:
1747:
1744:
1741:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1406:Counter machines discussion moved here from
1262:
1256:
1248:
1243:
1235:
1230:
1222:
1219:
1211:
1208:
1200:
1197:
1182:
497:To be didactic on examples and comparations;
1253:
1249:Indirect copy contents of r to accumulator
1240:
1236:Indirect copy contents of r to accumulator
1227:
1216:
1205:
1194:
1130:... in terms of JZ, DEC, J, CLR, INC, CPY.
247:Computer science articles without infoboxes
185:Computer science articles needing attention
2223:
382:
151:Here are some tasks awaiting attention:
125:
47:
2074:I wanted to find out more about Kalmar's
2000:
1962:
1924:
1886:
1773:
1718:
1659:
1334:'Problems with the counter machine model'
1275:indicates indirect addressing; <r: -->
542:(Source and Destination) where < : -->
2171:both roller-sets right- and left-capable
1416:A Two Counter Machine Cannot Calculate 2
1183:
1180:
1087:Move rX to rY, clearing contents of rX.
959:
740:
1349:
676:; otherwise go to the next instruction.
384:
49:
19:
1223:StoreA in r: store contents of A in r
1212:Immediate constant k from instruction
644:by 1, then go to the next instruction.
625:by 1, then go to the next instruction.
96:Knowledge:WikiProject Computer science
2353:Unknown-priority mathematics articles
2343:WikiProject Computer science articles
1823:I need to reboot. I'll be back. Bill
1486:by a 2CM. If a 2CM is used with some
99:Template:WikiProject Computer science
7:
2093:Schwictenberg's version of Kalmar's
1541:Rich Schroeppel rcs@cs.arizona.edu
667:is zero. If so, jump to instruction
427:This article is within the scope of
76:This article is within the scope of
727:(and to use optional "goto labels")
564:Counter machine's referencial model
490:A reference model is necessary to:
38:It is of interest to the following
635:— decrement the value of register
616:— increment the value of register
266:Timeline of computing 2020–present
14:
2333:C-Class Computer science articles
2162:single-tape with two roller-sets,
2132:single-tape with two roller-sets,
1387:Knowledge:Algorithms on Knowledge
447:Knowledge:WikiProject Mathematics
292:Computing articles needing images
1321:article has to be reworked. The
450:Template:WikiProject Mathematics
414:
404:
386:
142:
69:
51:
20:
1300:Counter machine:Reference model
875:func( d, rS, d, A) e.g. LDAi rS
869:func( i, rS, d, A) e.g. STAi rS
486:Sugestion for Referencial model
863:func( d, A, d, rD) e.g. STA rD
1:
2274:20:30, 16 February 2024 (UTC)
2238:19:23, 21 November 2020 (UTC)
2212:01:46, 29 November 2007 (UTC)
2193:22:54, 23 November 2007 (UTC)
2050:18:31, 23 November 2007 (UTC)
1833:16:41, 23 November 2007 (UTC)
1589:02:09, 23 November 2007 (UTC)
1555:22:08, 21 November 2007 (UTC)
1500:13:50, 21 November 2007 (UTC)
1453:20:01, 20 November 2007 (UTC)
1434:machine can compute N, 2, log
1401:20:56, 13 November 2006 (UTC)
441:and see a list of open tasks.
346:Tag all relevant articles in
90:and see a list of open tasks.
2348:C-Class mathematics articles
935:04:19, 25 October 2006 (UTC)
914:04:19, 25 October 2006 (UTC)
557:04:43, 25 October 2006 (UTC)
540:I would prefer < rS : -->
525:04:57, 25 October 2006 (UTC)
500:To be objective and "clean".
494:Simplify model comparations;
355:WikiProject Computer science
131:WikiProject Computer science
79:WikiProject Computer science
2138:right-hand write-only head,
1189:
1186:
518:algorithm characterizations
286:List of computer scientists
2369:
2299:09:35, 24 April 2024 (UTC)
2168:right-hand read-only head,
2141:both roller-sets left-only
839:func( iS, rS, iD, rD) e.g.
699:"Ease to write" std styles
118:project's importance scale
2165:left-hand read-only head,
1422:. While he proves that a
734:"Better layout" std style
466:
399:
348:Category:Computer science
124:
115:
102:Computer science articles
64:
46:
2155:Collatz capable machine:
2135:left-hand read-only head
1008:IF rX=0 THEN i1 ELSE i2
966:Implementation (script)
845:func( i, rs, i, rD) e.g.
682:— halts the computation.
658:— check if the value of
469:project's priority scale
350:and sub-categories with
2316:19:02, 2 May 2024 (UTC)
1305:Transfer basic to there
944:microcoded instructions
430:WikiProject Mathematics
1563:
1375:Knowledge:Lead section
1187:Implementation script
311:Computer science stubs
28:This article is rated
1562:
1463:i/o convention in CMs
1381:Style for Algorithms!
1338:Random-access machine
1324:Counter-machine model
1254:CPY ( i, rS, i, rD )
963:Emulated instruction
872:func( d, rs, i, A) ??
866:func( i, rS, i, A) ??
854:func( i, A, d, rD) ??
851:func( i, A, i, rD) ??
537:help translate them.
2109:that caught my eye.
2095:elementary functions
2080:Logic of Computation
2076:elementary functions
1358:Church-Turing thesis
1198:CPY (r) , A implied
1172:... in terms of ...
888:this is "irregular"
453:mathematics articles
129:Things you can help
1566:(Image inserted by
1257:CPY <<rS: -->
821:Referential Library
533:, a standard table
1564:
1369:Clean Lead section
1231:CPY <<r: -->
1220:CPY implied_A (r)
422:Mathematics portal
34:content assessment
2253:Counter automaton
2240:
2228:comment added by
2038:
2037:
1821:
1820:
1267:
1266:
1259:, <<rY: -->
1245:to <<r: -->
1179:
1178:
1071:CLEAR r; do r=0.
818:
817:
725:arbitrary address
693:Assembly language
483:
482:
479:
478:
475:
474:
381:
380:
377:
376:
373:
372:
369:
368:
2360:
2287:
2286:
2107:exponentiation 2
1846:
1598:
1361:
1354:
1181:
983:
960:
921:register machine
858:,<<rD: -->
827:register machine
741:
681:
657:
634:
615:
550:register machine
541:or < rD : -->
455:
454:
451:
448:
445:
424:
419:
418:
408:
401:
400:
390:
383:
359:
353:
228:Computer science
157:Article requests
146:
139:
138:
126:
104:
103:
100:
97:
94:
93:Computer science
84:Computer science
73:
66:
65:
59:Computer science
55:
48:
31:
25:
24:
16:
2368:
2367:
2363:
2362:
2361:
2359:
2358:
2357:
2323:
2322:
2284:
2282:
2246:
2220:
2200:Talk:Tag system
2089:
2085:
2070:
2066:
2062:
2058:
1849:Instruction #:
1601:Instruction #:
1437:
1411:
1408:Talk:Tag system
1383:
1371:
1366:
1365:
1364:
1355:
1351:
1318:Counter machine
1310:Counter machine
1292:
1209:constant k → A
1116:
1100:
1084:
981:
823:
736:
731:
701:
689:
679:
675:
666:
647:
643:
628:
624:
609:
604:
595:
588:
581:
572:
488:
452:
449:
446:
443:
442:
420:
413:
365:
362:
357:
351:
339:Project-related
334:
315:
296:
270:
251:
232:
213:
194:
170:
101:
98:
95:
92:
91:
32:on Knowledge's
29:
12:
11:
5:
2366:
2364:
2356:
2355:
2350:
2345:
2340:
2335:
2325:
2324:
2321:
2320:
2319:
2318:
2245:
2244:Merge proposal
2242:
2219:
2216:
2215:
2214:
2177:
2176:
2175:
2174:
2173:
2172:
2169:
2166:
2163:
2157:
2156:
2147:
2146:
2145:
2144:
2143:
2142:
2139:
2136:
2133:
2127:
2126:
2099:sub-elementary
2087:
2083:
2068:
2064:
2060:
2056:
2036:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1998:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1960:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1938:
1935:
1932:
1929:
1926:
1922:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1884:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1844:
1843:
1840:
1819:
1818:
1816:
1813:
1811:
1809:
1806:
1803:
1801:
1798:
1796:
1794:
1792:
1789:
1787:
1785:
1782:
1780:
1777:
1775:
1771:
1770:
1768:
1766:
1763:
1760:
1757:
1755:
1752:
1749:
1746:
1743:
1740:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1716:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1657:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1596:
1595:
1572:
1543:
1542:
1538:
1537:
1532:
1531:
1527:
1526:
1525:
1524:
1517:
1516:
1515:
1514:
1503:
1502:
1435:
1410:
1404:
1382:
1379:
1370:
1367:
1363:
1362:
1348:
1347:
1343:
1342:
1341:
1330:spaghetti-code
1313:
1306:
1303:
1291:
1288:
1286:
1284:
1283:
1280:
1277:
1273:<<r: -->
1265:
1264:
1261:
1255:
1251:
1250:
1247:
1244:CPY <A: -->
1242:
1241:STA ( i, r )
1238:
1237:
1234:
1229:
1228:LDA ( i, r )
1225:
1224:
1221:
1218:
1214:
1213:
1210:
1207:
1203:
1202:
1199:
1196:
1192:
1191:
1188:
1185:
1177:
1176:
1173:
1170:
1163:
1162:
1159:
1156:
1149:
1148:
1145:
1142:
1135:
1134:
1131:
1128:
1121:
1120:
1117:
1114:
1112:
1105:
1104:
1101:
1098:
1096:
1089:
1088:
1085:
1082:
1080:
1073:
1072:
1069:
1068:
1067:
1064:
1059:
1052:
1051:
1048:
1047:
1046:
1043:
1038:
1031:
1030:
1027:
1026:
1025:
1022:
1017:
1010:
1009:
1006:
1005:
1004:
1001:
996:
989:
988:
985:
978:
971:
970:
967:
964:
955:C preprocessor
940:
939:
938:
937:
917:
916:
903:
899:
898:
897:
896:
895:
894:
886:
885:
884:
883:
882:
879:
876:
873:
870:
867:
864:
861:
855:
852:
849:
846:
843:
840:
822:
819:
816:
815:
814:
810:
807:
803:
802:
801:
797:
795:
791:
790:
789:
785:
783:
779:
778:
777:
773:
771:
767:
766:
765:
761:
760:
756:
752:
751:
748:
745:
735:
732:
729:
721:
720:
717:
714:
711:
708:
700:
697:
688:
685:
684:
683:
677:
671:
662:
645:
639:
626:
620:
600:
593:
586:
577:
570:
560:
505:
504:
501:
498:
495:
487:
484:
481:
480:
477:
476:
473:
472:
465:
459:
458:
456:
439:the discussion
426:
425:
409:
397:
396:
391:
379:
378:
375:
374:
371:
370:
367:
366:
364:
363:
361:
360:
343:
335:
333:
332:
326:
316:
314:
313:
307:
297:
295:
294:
289:
281:
271:
269:
268:
262:
252:
250:
249:
243:
233:
231:
230:
224:
214:
212:
211:
205:
195:
193:
192:
187:
181:
171:
169:
168:
162:
150:
148:
147:
135:
134:
122:
121:
114:
108:
107:
105:
88:the discussion
74:
62:
61:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
2365:
2354:
2351:
2349:
2346:
2344:
2341:
2339:
2336:
2334:
2331:
2330:
2328:
2317:
2313:
2309:
2305:
2302:
2301:
2300:
2296:
2292:
2288:
2278:
2277:
2276:
2275:
2271:
2267:
2263:
2259:
2254:
2250:
2243:
2241:
2239:
2235:
2231:
2230:95.151.103.43
2227:
2217:
2213:
2209:
2205:
2201:
2197:
2196:
2195:
2194:
2190:
2186:
2181:
2170:
2167:
2164:
2161:
2160:
2159:
2158:
2154:
2153:
2152:
2151:
2150:
2140:
2137:
2134:
2131:
2130:
2129:
2128:
2124:
2123:
2122:
2121:
2120:
2118:
2113:
2110:
2108:
2102:
2100:
2096:
2091:
2081:
2077:
2072:
2052:
2051:
2047:
2043:
2001:Jump-if-1 #:
1999:
1963:Jump-if-0 #:
1961:
1923:
1887:Instruction:
1885:
1847:
1841:
1837:
1836:
1835:
1834:
1830:
1826:
1772:
1717:
1660:Instruction:
1658:
1599:
1593:
1592:
1591:
1590:
1586:
1582:
1578:
1571:
1569:
1561:
1557:
1556:
1552:
1548:
1540:
1539:
1534:
1533:
1529:
1528:
1521:
1520:
1519:
1518:
1511:
1510:
1509:
1508:
1507:
1501:
1497:
1493:
1489:
1485:
1481:
1476:
1472:
1468:
1464:
1462:
1457:
1456:
1455:
1454:
1450:
1446:
1440:
1431:
1429:
1425:
1421:
1417:
1409:
1405:
1403:
1402:
1399:
1395:
1390:
1388:
1380:
1378:
1376:
1368:
1359:
1353:
1350:
1346:
1339:
1335:
1331:
1326:
1325:
1320:
1319:
1314:
1311:
1307:
1304:
1301:
1297:
1296:
1295:
1289:
1287:
1281:
1278:
1272:
1271:
1270:
1252:
1239:
1233:to <A: -->
1226:
1215:
1204:
1193:
1174:
1171:
1168:
1165:
1164:
1160:
1157:
1154:
1151:
1150:
1146:
1143:
1140:
1137:
1136:
1132:
1129:
1126:
1123:
1122:
1118:
1113:
1110:
1107:
1106:
1102:
1097:
1094:
1091:
1090:
1086:
1081:
1078:
1075:
1074:
1070:
1065:
1062:
1061:
1060:
1057:
1054:
1053:
1049:
1044:
1041:
1040:
1039:
1036:
1033:
1032:
1028:
1023:
1020:
1019:
1018:
1015:
1012:
1011:
1007:
1002:
999:
998:
997:
994:
991:
990:
986:
984:
979:
976:
973:
972:
968:
965:
962:
961:
958:
956:
951:
949:
945:
936:
933:
929:
928:
926:
925:
924:
922:
915:
912:
904:
901:
900:
892:
891:
890:
889:
887:
880:
877:
874:
871:
868:
865:
862:
856:
853:
850:
847:
844:
841:
838:
837:
836:
835:
832:
831:
830:
828:
820:
812:
811:
808:
805:
804:
800:JZ (r0,begin)
799:
798:
796:
793:
792:
787:
786:
784:
781:
780:
775:
774:
772:
769:
768:
763:
762:
758:
757:
754:
753:
749:
746:
743:
742:
739:
733:
728:
726:
718:
715:
712:
709:
706:
705:
704:
698:
696:
694:
686:
678:
674:
670:
665:
661:
655:
651:
646:
642:
638:
632:
627:
623:
619:
613:
608:
607:
606:
603:
599:
592:
585:
580:
576:
569:
565:
559:
558:
555:
551:
546:
538:
536:
532:
527:
526:
523:
519:
515:
511:
502:
499:
496:
493:
492:
491:
485:
470:
464:
461:
460:
457:
440:
436:
432:
431:
423:
417:
412:
410:
407:
403:
402:
398:
395:
392:
389:
385:
356:
349:
345:
344:
342:
340:
336:
331:
328:
327:
325:
323:
322:
317:
312:
309:
308:
306:
304:
303:
298:
293:
290:
287:
283:
282:
280:
278:
277:
272:
267:
264:
263:
261:
259:
258:
253:
248:
245:
244:
242:
240:
239:
234:
229:
226:
225:
223:
221:
220:
215:
210:
207:
206:
204:
202:
201:
196:
191:
188:
186:
183:
182:
180:
178:
177:
172:
167:
164:
163:
161:
159:
158:
153:
152:
149:
145:
141:
140:
137:
136:
132:
128:
127:
123:
119:
113:
110:
109:
106:
89:
85:
81:
80:
75:
72:
68:
67:
63:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
2303:
2248:
2247:
2224:— Preceding
2221:
2182:
2178:
2148:
2125:Tag machine:
2116:
2114:
2111:
2106:
2103:
2098:
2094:
2092:
2079:
2075:
2073:
2053:
2039:
1822:
1576:
1573:
1565:
1544:
1504:
1487:
1483:
1480:tractability
1479:
1474:
1470:
1466:
1460:
1459:
1441:
1432:
1427:
1423:
1415:
1412:
1393:
1391:
1384:
1372:
1352:
1344:
1333:
1322:
1316:
1294:Sugestions:
1293:
1285:
1268:
1166:
1152:
1138:
1124:
1108:
1092:
1076:
1055:
1034:
1029:DEC and JZ.
1013:
995:(rX, i1,i2)
992:
980:
974:
952:
941:
918:
824:
750:Instruction
737:
724:
722:
702:
690:
672:
668:
663:
659:
653:
649:
640:
636:
630:
621:
617:
611:
601:
597:
590:
583:
578:
574:
567:
563:
561:
547:
539:
534:
530:
528:
513:
506:
489:
428:
338:
337:
321:Unreferenced
319:
318:
300:
299:
274:
273:
255:
254:
236:
235:
217:
216:
198:
197:
174:
173:
155:
154:
77:
40:WikiProjects
2308:KenShirriff
2266:KenShirriff
1774:Jump-to #:
1577:Computation
1050:INC and J.
776:JZ (r2,end)
514:define them
444:Mathematics
435:mathematics
394:Mathematics
2327:Categories
1925:Register:
1719:Register:
1484:computable
1465:— namely,
1396:. wvbailey
1345:References
1217:STA ( r )
1195:LDA ( r )
1169:(rX,rY,r)
1155:(rX,rY,r)
1141:(rX,rY,r)
1127:(rX,rX,r)
1111:(rX,rY,r)
1003:JZ (r0,i2)
1000:JZ (rX,i1)
919:Different
1298:Create a
1190:Comments
1184:Mnemonic
982:JZ (r0,i)
969:Comments
716:JZ (0,1)
710:JZ (2,5)
209:Computing
2295:contribs
2283:Chaotıċ
2226:unsigned
2185:Wvbailey
2042:Wvbailey
1825:Wvbailey
1568:Wvbailey
1547:Wvbailey
1445:Wvbailey
1398:Wvbailey
1340:article.
1302:article.
1095:(rX,rY)
1079:(rX,rY)
1066:JZ (r,1)
1024:JZ (r,i)
948:emulator
932:Wvbailey
911:Wvbailey
909:wvbailey
829:models.
723:Or, for
554:Wvbailey
522:Wvbailey
257:Maintain
200:Copyedit
2262:WP:BOLD
2249:Support
2117:appears
1360:is true
1356:if the
1308:Update
1290:Working
1269:Notes:
788:INC(r1)
764:DEC(r2)
713:INC (1)
707:DEC (2)
238:Infobox
176:Cleanup
30:C-class
2304:Oppose
2251:: The
2204:r.e.s.
2086:ELSE I
2069:y<w
2065:y<w
1581:r.e.s.
1492:r.e.s.
1206:LDA k
1063:DEC(r)
1045:J (i)
1042:INC(r)
1037:(r,i)
1021:DEC(r)
1016:(r,i)
946:for a
747:Label
219:Expand
36:scale.
2258:merge
2040:Bill
1911:test
1545:Bill
1513:'net.
1488:other
1424:three
1274:: -->
1260:: -->
1258:: -->
1246:: -->
1232:: -->
1014:DECJZ
907:: -->
859:: -->
759:begin
744:Addr
562:The "
535:would
302:Stubs
276:Photo
133:with:
2312:talk
2291:talk
2285:Enby
2270:talk
2234:talk
2208:talk
2189:talk
2046:talk
1920:dcr
1917:inc
1914:dcr
1908:inc
1905:inc
1902:inc
1899:dcr
1896:inc
1893:dcr
1890:out
1829:talk
1708:inc
1705:dcr
1696:dcr
1690:inc
1687:inc
1684:inc
1678:inc
1675:dcr
1669:dcr
1663:out
1585:talk
1551:talk
1496:talk
1475:only
1449:talk
1385:See
1373:See
1315:The
1058:(r)
1035:INCJ
977:(i)
813:HALT
809:end
719:HALT
680:HALT
648:JZ (
629:DEC(
610:INC(
596:...
573:...
2218:DEC
2067:, Π
2061:y=w
2059:, Π
2057:y=w
2034:10
2031:11
1993:11
1975:10
1882:11
1879:10
1815:14
1779:14
1702:jz
1693:jz
1672:jZ
1666:jZ
1655:18
1652:17
1649:16
1646:15
1643:14
1640:13
1637:12
1634:11
1631:10
1461:the
1167:SUB
1153:EXP
1139:MUL
1125:ADD
1109:CMP
1093:CPY
1077:MOV
1056:CLR
806:50
794:40
782:30
770:20
755:10
531:But
510:MIX
463:???
112:???
2329::
2314:)
2297:)
2293:·
2272:)
2236:)
2210:)
2191:)
2048:)
2028:5
2025:9
2022:8
2019:7
2016:6
2013:2
2010:4
2007:3
2004:2
1996:1
1990:5
1987:1
1984:8
1981:7
1978:6
1972:4
1969:6
1966:2
1958:B
1955:A
1952:B
1949:B
1946:A
1943:A
1940:A
1937:A
1934:B
1931:A
1928:A
1876:9
1873:8
1870:7
1867:6
1864:5
1861:4
1858:3
1855:2
1852:1
1831:)
1808:1
1805:8
1800:1
1791:2
1784:9
1765:A
1762:B
1759:B
1754:B
1751:B
1748:A
1745:A
1742:A
1737:B
1734:A
1731:A
1728:A
1725:A
1722:A
1714:H
1711:j
1699:j
1681:j
1628:9
1625:8
1622:7
1619:6
1616:5
1613:4
1610:3
1607:2
1604:1
1587:)
1570:)
1553:)
1498:)
1469:—
1451:)
1389:.
1377:.
993:JZ
652:,
358:}}
352:{{
2310:(
2289:(
2268:(
2232:(
2206:(
2187:(
2088:n
2084:m
2055:Σ
2044:(
1827:(
1583:(
1575:(
1549:(
1494:(
1447:(
1436:2
975:J
860:)
673:z
669:I
664:j
660:r
656:)
654:z
650:j
641:j
637:r
633:)
631:j
622:j
618:r
614:)
612:j
602:m
598:I
594:0
591:I
587:0
584:r
579:n
575:r
571:1
568:r
471:.
341::
324::
305::
288:)
279::
260::
241::
222::
203::
179::
160::
120:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.