3285:
4212:
1837:
3121:
303:"This table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the m-configuration in the final column." (Undecidable p. 121)
3094:
The basic way it works is by copying each "1" to the other side, by moving back and forth - it is intelligent enough to remember which part of the trip it is on. In more detail, it carries each "1" across to the other side, by recognizing the separating "0" in the middle, and recognizing the "0" on
676:
Thus when printing he skips every other square. The printed-on squares are called F-squares; the blank squares in between may be used for "markers" and are called "E-squares" as in "liable to erasure." The F-squares in turn are his "Figure squares" and will only bear the symbols 1 or 0 —
1857:
The example Turing machine handles a string of 0s and 1s, with 0 represented by the blank symbol. Its task is to double any series of 1s encountered on the tape by writing a 0 between them. For example, when the head reads "111", it will write a 0, then "111". The output will be "1110111".
375:
As observed by a number of commentators including Turing (1937) himself, (e.g., Post (1936), Post (1947), Kleene (1952), Wang (1954)) the Turing instructions are not atomic — further simplifications of the model can be made without reducing its computational power; see more at
3086:
Another description sees the problem as how to keep track of how many "1"s there are. We can't use one state for each possible number (a state for each of 0,1,2,3,4,5,6 etc), because then we'd need infinite states to represent all the natural numbers, and the state machine is
3109:
When it returns, the marker "0" looks like the end of the collection of "1"s to it - any "1"s that have already been taken across are invisible to it (on the other side of the marker "0") and so it is as if it is working on an (N-1) number of "1"s - similar to a proof by
3272:
The "state" drawing of the 3-state busy beaver shows the internal sequences of events required to actually perform "the state". As noted above Turing (1937) makes it perfectly clear that this is the proper interpretation of the 5-tuples that describe the instruction
311:
p. 120), but his instruction consists of 3 lines. Instruction "b" has three different symbol possibilities {None, 0, 1}. Each possibility is followed by a sequence of actions until we arrive at the rightmost column, where the final m-configuration is "b":
4207:
The full "run" of the 3-state busy beaver. The resulting Turing-states (what Turing called the "m-configurations" — "machine-configurations") are shown highlighted in grey in column A, and also under the machine's instructions (columns AF-AU)):
3095:
the other side to know it's reached the end. It comes back using the same method, detecting the middle "0", and then the "0" on the original side. This "0" on the original side is the key to the puzzle of how it keeps track of the number of 1's.
531:
Because a Turing machine's actions are not atomic, a simulation of the machine must atomize each 5-tuple into a sequence of simpler actions. One possibility — used in the following examples of "behaviors" of his machine — is as follows:
387:, Turing proposed that his table be further atomized by allowing only a single print/erase followed by a single tape movement L/R/N. He gives us this example of the first little table converted (
3135:
The following Turing table of instructions was derived from
Peterson (1988) page 198, Figure 7.15. Peterson moves the head; in the following model the tape moves.
4297:
3098:
The trick is that before carrying the "1", it marks that digit as "taken" by replacing it with an "0". When it returns, it fills that "0" back in with a "1",
1846:
For example, suppose his tape was not initially blank. What would happen? The Turing machine would read different values than the intended values.
3117:
A full "run" showing the results of the intermediate "motions". To see it better click on the image, then click on the higher resolution download:
4617:
4290:
680:
In this example the tape starts out "blank", and the "figures" are then printed on it. For brevity only the TABLE-states are shown here:
672:"The convention of writing the figures only on alternate squares is very useful: I shall always make use of it." (Undecidable p. 121)
4504:
4283:
4429:
1843:
A close look at the table reveals certain problems with Turing's own example—not all the symbols are accounted for.
4519:
4444:
4249:
editor, 1965, The
Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions
4240:
4612:
4597:
168:
4473:
201:"1. A machine can be constructed to compute the sequence 0 1 0 1 0 1..." (0 <blank> 1 <blank> 0...) (
71:
3048:
then skips over the next sequence of 1s (initially there are none) and replaces the first 0 it finds with a 1. s
4243:(pbk.). Turing machines are described on pp. 194ff, the busy beaver example is in Figure 7.15 on page 198.
507:
Turing's statement still implies five atomic operations. At a given instruction (m-configuration) the machine:
1861:
In order to accomplish its task, this Turing machine will need only 5 states of operation, which are called {s
4641:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
4490:
4415:
4246:
86:
4587:
4275:
4483:
668:
In the following example of what the machine does, we will note some peculiarities of Turing's models:
111:
96:
61:
35:
4408:
4560:
4555:
116:
106:
101:
91:
3078:
finds a 0 (this is the 0 in the middle of the two strings of 1s) at which time the machine halts.
4659:
3278:
377:
142:
81:
4571:
4509:
4434:
3111:
76:
45:
3060:
then moves to the left, skipping over 1s until it finds the 0 that was originally written by s
4514:
4462:
4211:
658:
307:
He makes this very clear when he reduces the above table to a single instruction called "b" (
66:
4607:
4582:
4439:
4400:
161:
1836:
8:
2191:
A "run" of the machine sequences through 16 machine-configurations (aka Turing states):
4592:
4534:
4478:
3102:, marking it with an "0" and repeating the cycle, carrying that "1" across and so on.
4327:
4236:
4268:
On
Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
3284:
1833:
The same "run" with all the intermediate tape-printing and movements is shown here:
4576:
4529:
4496:
4342:
662:
3104:
With each trip across and back, the marker "0" moves one step closer to the centre
4539:
4454:
4421:
4337:
4310:
4306:
154:
514:
based on the observed symbol goes to the appropriate instruction-sequence to use
4550:
4332:
4314:
4224:
3291:
The following table shows the "compressed" run — just the Turing states:
384:
182:
21:
3120:
4653:
4635:
3052:
moves back to the left, skipping over 1s until it finds a 0 and switches to s
3036:
The behavior of this machine can be described as a loop: it starts out in s
121:
4602:
4524:
4449:
4305:
3129:
3067:
It replaces that 0 with a 1, moves one position to the right and enters s
194:
137:
4261:
On
Computable Numbers, with an Application to the Entscheidungsproblem
3277:, p. 119). For more about the atomization of Turing 5-tuples see
295:
With regard to what actions the machine actually does, Turing (1936) (
3106:. This is how it keeps track of how many "1"'s it has taken across.
3044:
to move to the right, skipping over 1s and the first 0 encountered. s
1854:
This is a very important subroutine used in the "multiply" routine.
1891:
Move the tape to the left or to the right decided by the state
4565:
4634:
Each category of languages, except those marked by a , is a
1894:
Switch to the following state decided by the current state
646:.22) move tape left or right nor not at all then go to qm2
618:.12) move tape left or right nor not at all then go to qm1
590:.02) move tape left or right nor not at all then go to qm0
4251:, Raven Press, New York, no ISBN, no card catalog number.
4233:
4263:, pp. 116ff, with brief commentary by Davis on page 115.
3091:- we'll have to track this using the tape in some way.
677:
symbols he called "figures" (as in "binary numbers").
181:
The following are examples to supplement the article
193:
The following table is Turing's very first example (
540:) Test tape-symbol under head: If the symbol is S
527:goes to the final m-configuration for that symbol
4651:
661:do the symbol tests "in parallel"; see more at
653:(etc — all symbols must be accounted for)
188:
4291:
162:
3040:, replaces the first 1 with a 0, then uses s
1888:Write the output symbol decided by the state
511:observes the tape-symbol underneath the head
4613:Counter-free (with aperiodic finite monoid)
4298:
4284:
3081:
169:
155:
4235:, W. H. Freeman and Company, New York,
397:Current m-configuration (Turing state)
4652:
4505:Linear context-free rewriting language
3127:
318:Current m-configuration (instruction)
4430:Linear context-free rewriting systems
4279:
3071:again for another round of the loop.
635:2 or erase or do nothing then go to q
607:1 or erase or do nothing then go to q
579:0 or erase or do nothing then go to q
409:Final m-configuration (Turing state)
1849:
524:moves tape left, right or not at all
327:Final m-configuration (instruction)
299:p. 121) states the following:
13:
4638:of the category directly above it.
4210:
3283:
3119:
1835:
14:
4671:
2159:
2156:
2153:
72:Nondeterministic Turing machine
1885:Read the symbol under the head
1881:}. Each state does 4 actions:
1:
4218:
3100:then moves on to the next one
4223:For complete references see
87:Probabilistic Turing machine
7:
189:Turing's very first example
10:
4676:
4520:Deterministic context-free
4445:Deterministic context-free
112:Unambiguous Turing machine
97:Multi-track Turing machine
62:Alternating Turing machine
36:Turing machine equivalents
4631:
4593:Nondeterministic pushdown
4321:
3155:
3149:
3143:
521:or erases or does nothing
383:As stated in the article
214:
211:
1901:Initial m-configuration
117:Universal Turing machine
102:Symmetric Turing machine
92:Multitape Turing machine
3300:Instruction identifier
3082:Alternative description
2200:Instruction identifier
689:Instruction identifier
324:Operations on the tape
143:Category:Turing machine
41:Turing machine examples
4598:Deterministic pushdown
4474:Recursively enumerable
4231:Ivars Peterson, 1988,
4215:
3288:
3124:
3112:mathematical induction
3074:This continues until s
1916:Final m-configuration
1903:(current instruction)
1840:
657:So-called "canonical"
77:Quantum Turing machine
46:Turing machine gallery
4214:
3287:
3123:
1839:
659:finite state machines
231:Final m-configuration
67:Neural Turing machine
4583:Tree stack automaton
107:Total Turing machine
4491:range concatenation
4416:range concatenation
4266:Alan Turing, 1937,
4259:Alan Turing, 1937,
3279:Post–Turing machine
1918:(next instruction)
631:.21) print symbol S
603:.11) print symbol S
575:.01) print symbol S
378:Post–Turing machine
82:Post–Turing machine
4216:
3289:
3125:
2177:rints symbol S or
1841:
4647:
4646:
4626:
4625:
4588:Embedded pushdown
4484:Context-sensitive
4409:Context-sensitive
4343:Abstract machines
4328:Chomsky hierarchy
4205:
4204:
3270:
3269:
3034:
3033:
2187:
2166:
2165:
1850:A copy subroutine
1831:
1830:
505:
504:
373:
372:
293:
292:
179:
178:
4667:
4642:
4639:
4603:Visibly pushdown
4577:Thread automaton
4525:Visibly pushdown
4493:
4450:Visibly pushdown
4418:
4405:(no common name)
4324:
4323:
4311:formal languages
4300:
4293:
4286:
4277:
4276:
3294:
3293:
3138:
3137:
2194:
2193:
2168:
1910:Print operation
1898:
1897:
683:
682:
663:microprogramming
556:.11, if symbol S
548:.01, if symbol S
492:P blank, i.e. E
446:P blank, i.e. E
403:Print-operation
394:
393:
391:, p. 127):
315:
314:
228:Tape operations
209:
208:
171:
164:
157:
18:
17:
4675:
4674:
4670:
4669:
4668:
4666:
4665:
4664:
4650:
4649:
4648:
4643:
4640:
4633:
4627:
4622:
4544:
4488:
4467:
4413:
4394:
4317:
4315:formal grammars
4307:Automata theory
4304:
4221:
3133:
3084:
3077:
3070:
3063:
3059:
3055:
3051:
3047:
3043:
3039:
2936:
2884:
2832:
2780:
2730:
2680:
2630:
2578:
2528:
2478:
2428:
2380:
2332:
2284:
2234:
2190:
2171:Print Operation
2146:
2131:
2123:
2108:
2100:
2085:
2077:
2062:
2054:
2039:
2031:
2016:
2008:
1993:
1985:
1970:
1962:
1947:
1927:
1880:
1876:
1872:
1868:
1864:
1852:
645:
638:
634:
630:
617:
610:
606:
602:
589:
582:
578:
574:
563:
559:
555:
551:
547:
543:
539:
520:
517:prints symbol S
501:
486:
478:
463:
455:
440:
432:
417:
232:
221:
220:m-configuration
191:
175:
22:Turing machines
12:
11:
5:
4673:
4663:
4662:
4660:Turing machine
4645:
4644:
4632:
4629:
4628:
4624:
4623:
4621:
4620:
4618:Acyclic finite
4615:
4610:
4605:
4600:
4595:
4590:
4585:
4579:
4574:
4569:
4568:Turing Machine
4563:
4561:Linear-bounded
4558:
4553:
4551:Turing machine
4547:
4545:
4543:
4542:
4537:
4532:
4527:
4522:
4517:
4512:
4510:Tree-adjoining
4507:
4502:
4499:
4494:
4486:
4481:
4476:
4470:
4468:
4466:
4465:
4460:
4457:
4452:
4447:
4442:
4437:
4435:Tree-adjoining
4432:
4427:
4424:
4419:
4411:
4406:
4403:
4397:
4395:
4393:
4392:
4389:
4386:
4383:
4380:
4377:
4374:
4371:
4368:
4365:
4362:
4359:
4356:
4353:
4349:
4346:
4345:
4340:
4335:
4330:
4322:
4319:
4318:
4303:
4302:
4295:
4288:
4280:
4274:
4273:
4272:
4271:
4264:
4254:
4253:
4244:
4225:Turing machine
4220:
4217:
4203:
4202:
4199:
4196:
4193:
4190:
4185:
4180:
4175:
4168:
4163:
4158:
4155:
4152:
4149:
4146:
4141:
4137:
4136:
4133:
4130:
4127:
4124:
4119:
4114:
4109:
4102:
4097:
4092:
4089:
4086:
4083:
4080:
4075:
4071:
4070:
4067:
4064:
4061:
4056:
4051:
4046:
4041:
4034:
4029:
4026:
4023:
4020:
4017:
4014:
4011:
4007:
4006:
4003:
4000:
3995:
3990:
3985:
3980:
3975:
3968:
3965:
3962:
3959:
3956:
3953:
3950:
3945:
3941:
3940:
3937:
3934:
3931:
3926:
3921:
3916:
3911:
3904:
3901:
3898:
3895:
3892:
3889:
3886:
3881:
3877:
3876:
3873:
3870:
3867:
3864:
3859:
3854:
3849:
3842:
3837:
3834:
3831:
3828:
3825:
3822:
3817:
3813:
3812:
3809:
3806:
3803:
3800:
3797:
3792:
3787:
3780:
3775:
3770:
3767:
3764:
3761:
3758:
3753:
3749:
3748:
3745:
3742:
3739:
3736:
3733:
3730:
3727:
3720:
3715:
3710:
3705:
3702:
3699:
3696:
3691:
3687:
3686:
3683:
3680:
3677:
3674:
3671:
3668:
3665:
3658:
3653:
3648:
3643:
3638:
3635:
3632:
3627:
3623:
3622:
3619:
3616:
3613:
3610:
3607:
3604:
3601:
3594:
3589:
3584:
3579:
3576:
3573:
3570:
3565:
3561:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3532:
3527:
3522:
3519:
3516:
3513:
3510:
3505:
3501:
3500:
3497:
3494:
3491:
3488:
3485:
3482:
3479:
3472:
3467:
3464:
3461:
3458:
3455:
3452:
3447:
3443:
3442:
3439:
3436:
3433:
3430:
3427:
3424:
3421:
3414:
3411:
3408:
3405:
3402:
3399:
3396:
3391:
3387:
3386:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3335:
3331:
3330:
3328:
3326:
3324:
3322:
3320:
3318:
3316:
3313:
3311:
3309:
3307:
3305:
3303:
3301:
3298:
3268:
3267:
3262:
3259:
3256:
3251:
3248:
3245:
3240:
3237:
3234:
3230:
3229:
3224:
3221:
3218:
3213:
3210:
3207:
3202:
3199:
3196:
3192:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3160:
3156:Current state
3154:
3150:Current state
3148:
3144:Current state
3142:
3132:
3126:
3083:
3080:
3075:
3068:
3061:
3057:
3053:
3049:
3045:
3041:
3037:
3032:
3031:
3028:
3025:
3022:
3017:
3012:
3007:
3002:
2997:
2994:
2991:
2988:
2985:
2981:
2980:
2977:
2974:
2971:
2966:
2961:
2956:
2951:
2946:
2943:
2940:
2937:
2934:
2931:
2927:
2926:
2923:
2920:
2917:
2914:
2909:
2904:
2901:
2896:
2891:
2888:
2885:
2882:
2879:
2875:
2874:
2871:
2868:
2865:
2860:
2857:
2852:
2847:
2842:
2839:
2836:
2833:
2830:
2827:
2823:
2822:
2819:
2816:
2811:
2808:
2805:
2798:
2793:
2790:
2787:
2784:
2781:
2778:
2775:
2771:
2770:
2767:
2762:
2759:
2756:
2751:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2721:
2720:
2717:
2714:
2709:
2706:
2703:
2696:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2671:
2670:
2667:
2664:
2661:
2656:
2653:
2648:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2621:
2620:
2617:
2614:
2611:
2608:
2603:
2596:
2593:
2588:
2585:
2582:
2579:
2576:
2573:
2569:
2568:
2565:
2562:
2559:
2556:
2553:
2548:
2543:
2540:
2535:
2532:
2529:
2526:
2523:
2519:
2518:
2515:
2512:
2509:
2506:
2503:
2496:
2493:
2488:
2485:
2482:
2479:
2476:
2473:
2469:
2468:
2465:
2462:
2459:
2456:
2451:
2446:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2419:
2418:
2415:
2412:
2409:
2404:
2401:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2371:
2370:
2367:
2364:
2361:
2358:
2353:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2323:
2322:
2319:
2316:
2313:
2310:
2307:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2275:
2274:
2271:
2268:
2265:
2262:
2259:
2252:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2225:
2224:
2222:
2220:
2218:
2216:
2214:
2211:
2209:
2207:
2205:
2203:
2201:
2198:
2181:rases or does
2164:
2163:
2161:
2158:
2155:
2152:
2148:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2125:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2102:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2079:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2056:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2033:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2010:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1987:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1964:
1963:
1960:
1957:
1954:
1951:
1948:
1945:
1941:
1940:
1937:
1934:
1931:
1928:
1925:
1921:
1920:
1914:
1911:
1908:
1905:
1896:
1895:
1892:
1889:
1886:
1878:
1874:
1870:
1866:
1862:
1851:
1848:
1829:
1828:
1823:
1820:
1815:
1812:
1807:
1804:
1799:
1796:
1791:
1788:
1783:
1780:
1775:
1770:
1767:
1764:
1761:
1758:
1753:
1749:
1748:
1745:
1740:
1737:
1732:
1729:
1724:
1721:
1716:
1713:
1708:
1705:
1700:
1697:
1692:
1689:
1686:
1683:
1680:
1675:
1671:
1670:
1667:
1664:
1659:
1656:
1651:
1648:
1643:
1640:
1635:
1632:
1627:
1624:
1619:
1614:
1611:
1608:
1605:
1602:
1597:
1593:
1592:
1589:
1586:
1583:
1578:
1575:
1570:
1567:
1562:
1559:
1554:
1551:
1546:
1543:
1538:
1535:
1532:
1529:
1526:
1521:
1517:
1516:
1513:
1510:
1507:
1504:
1499:
1496:
1491:
1488:
1483:
1480:
1475:
1472:
1467:
1462:
1459:
1456:
1453:
1450:
1445:
1441:
1440:
1437:
1434:
1431:
1428:
1425:
1420:
1417:
1412:
1409:
1404:
1401:
1396:
1393:
1388:
1385:
1382:
1379:
1376:
1371:
1367:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1343:
1340:
1335:
1332:
1327:
1324:
1319:
1314:
1311:
1308:
1305:
1302:
1297:
1293:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1266:
1263:
1258:
1255:
1250:
1247:
1242:
1239:
1236:
1233:
1230:
1225:
1221:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1191:
1188:
1183:
1180:
1175:
1170:
1167:
1164:
1161:
1158:
1153:
1149:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1116:
1113:
1108:
1105:
1100:
1097:
1094:
1091:
1088:
1083:
1079:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1043:
1040:
1035:
1030:
1027:
1024:
1021:
1018:
1013:
1009:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
970:
967:
962:
959:
956:
953:
950:
945:
941:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
899:
894:
891:
888:
885:
882:
877:
873:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
828:
825:
822:
819:
816:
811:
807:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
762:
759:
756:
753:
750:
748:
745:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
674:
673:
655:
654:
650:
649:
648:
647:
643:
640:
636:
632:
628:
622:
621:
620:
619:
615:
612:
608:
604:
600:
594:
593:
592:
591:
587:
584:
580:
576:
572:
566:
565:
561:
557:
553:
549:
545:
541:
537:
529:
528:
525:
522:
518:
515:
512:
503:
502:
499:
496:
493:
490:
487:
484:
480:
479:
476:
473:
470:
467:
464:
461:
457:
456:
453:
450:
447:
444:
441:
438:
434:
433:
430:
427:
424:
421:
418:
415:
411:
410:
407:
404:
401:
398:
385:Turing machine
371:
370:
367:
364:
361:
357:
356:
353:
350:
347:
343:
342:
339:
336:
333:
329:
328:
325:
322:
319:
305:
304:
291:
290:
287:
284:
281:
277:
276:
273:
270:
267:
263:
262:
259:
256:
253:
249:
248:
245:
242:
239:
235:
234:
229:
226:
223:
217:
216:
213:
212:Configuration
207:
206:
190:
187:
183:Turing machine
177:
176:
174:
173:
166:
159:
151:
148:
147:
146:
145:
140:
132:
131:
127:
126:
125:
124:
119:
114:
109:
104:
99:
94:
89:
84:
79:
74:
69:
64:
56:
55:
51:
50:
49:
48:
43:
38:
30:
29:
25:
24:
9:
6:
4:
3:
2:
4672:
4661:
4658:
4657:
4655:
4637:
4636:proper subset
4630:
4619:
4616:
4614:
4611:
4609:
4606:
4604:
4601:
4599:
4596:
4594:
4591:
4589:
4586:
4584:
4580:
4578:
4575:
4573:
4570:
4567:
4564:
4562:
4559:
4557:
4554:
4552:
4549:
4548:
4546:
4541:
4538:
4536:
4533:
4531:
4528:
4526:
4523:
4521:
4518:
4516:
4513:
4511:
4508:
4506:
4503:
4500:
4498:
4495:
4492:
4487:
4485:
4482:
4480:
4477:
4475:
4472:
4471:
4469:
4464:
4463:Non-recursive
4461:
4458:
4456:
4453:
4451:
4448:
4446:
4443:
4441:
4438:
4436:
4433:
4431:
4428:
4425:
4423:
4420:
4417:
4412:
4410:
4407:
4404:
4402:
4399:
4398:
4396:
4390:
4387:
4384:
4381:
4378:
4375:
4372:
4369:
4366:
4363:
4360:
4357:
4354:
4351:
4350:
4348:
4347:
4344:
4341:
4339:
4336:
4334:
4331:
4329:
4326:
4325:
4320:
4316:
4312:
4308:
4301:
4296:
4294:
4289:
4287:
4282:
4281:
4278:
4270:, p. 152-154.
4269:
4265:
4262:
4258:
4257:
4256:
4255:
4252:
4248:
4245:
4242:
4241:0-7167-2064-7
4238:
4234:
4230:
4229:
4228:
4226:
4213:
4209:
4200:
4197:
4194:
4191:
4189:
4186:
4184:
4181:
4179:
4176:
4174:
4173:
4169:
4167:
4164:
4162:
4159:
4156:
4153:
4150:
4147:
4145:
4142:
4139:
4138:
4134:
4131:
4128:
4125:
4123:
4120:
4118:
4115:
4113:
4110:
4108:
4107:
4103:
4101:
4098:
4096:
4093:
4090:
4087:
4084:
4081:
4079:
4076:
4073:
4072:
4068:
4065:
4062:
4060:
4057:
4055:
4052:
4050:
4047:
4045:
4042:
4040:
4039:
4035:
4033:
4030:
4027:
4024:
4021:
4018:
4015:
4012:
4009:
4008:
4004:
4001:
3999:
3996:
3994:
3991:
3989:
3986:
3984:
3981:
3979:
3976:
3974:
3973:
3969:
3966:
3963:
3960:
3957:
3954:
3951:
3949:
3946:
3943:
3942:
3938:
3935:
3932:
3930:
3927:
3925:
3922:
3920:
3917:
3915:
3912:
3910:
3909:
3905:
3902:
3899:
3896:
3893:
3890:
3887:
3885:
3882:
3879:
3878:
3874:
3871:
3868:
3865:
3863:
3860:
3858:
3855:
3853:
3850:
3848:
3847:
3843:
3841:
3838:
3835:
3832:
3829:
3826:
3823:
3821:
3818:
3815:
3814:
3810:
3807:
3804:
3801:
3798:
3796:
3793:
3791:
3788:
3786:
3785:
3781:
3779:
3776:
3774:
3771:
3768:
3765:
3762:
3759:
3757:
3754:
3751:
3750:
3746:
3743:
3740:
3737:
3734:
3731:
3728:
3726:
3725:
3721:
3719:
3716:
3714:
3711:
3709:
3706:
3703:
3700:
3697:
3695:
3692:
3689:
3688:
3684:
3681:
3678:
3675:
3672:
3669:
3666:
3664:
3663:
3659:
3657:
3654:
3652:
3649:
3647:
3644:
3642:
3639:
3636:
3633:
3631:
3628:
3625:
3624:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3600:
3599:
3595:
3593:
3590:
3588:
3585:
3583:
3580:
3577:
3574:
3571:
3569:
3566:
3563:
3562:
3558:
3555:
3552:
3549:
3546:
3543:
3540:
3538:
3537:
3533:
3531:
3528:
3526:
3523:
3520:
3517:
3514:
3511:
3509:
3506:
3503:
3502:
3498:
3495:
3492:
3489:
3486:
3483:
3480:
3478:
3477:
3473:
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3451:
3448:
3445:
3444:
3440:
3437:
3434:
3431:
3428:
3425:
3422:
3420:
3419:
3415:
3412:
3409:
3406:
3403:
3400:
3397:
3395:
3392:
3389:
3388:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3364:
3363:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3339:
3336:
3333:
3332:
3329:
3327:
3325:
3323:
3321:
3319:
3317:
3314:
3312:
3310:
3308:
3306:
3304:
3302:
3299:
3296:
3295:
3292:
3286:
3282:
3280:
3276:
3266:
3263:
3260:
3257:
3255:
3252:
3249:
3246:
3244:
3241:
3238:
3235:
3232:
3231:
3228:
3225:
3222:
3219:
3217:
3214:
3211:
3208:
3206:
3203:
3200:
3197:
3194:
3193:
3189:
3186:
3184:Write symbol
3183:
3180:
3177:
3175:Write symbol
3174:
3171:
3168:
3166:Write symbol
3165:
3163:
3162:
3159:
3153:
3147:
3140:
3139:
3136:
3131:
3122:
3118:
3115:
3113:
3107:
3105:
3101:
3096:
3092:
3090:
3079:
3072:
3065:
3029:
3026:
3023:
3021:
3018:
3016:
3013:
3011:
3008:
3006:
3003:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2982:
2978:
2975:
2972:
2970:
2967:
2965:
2962:
2960:
2957:
2955:
2952:
2950:
2947:
2944:
2941:
2938:
2932:
2929:
2928:
2924:
2921:
2918:
2915:
2913:
2910:
2908:
2905:
2902:
2900:
2897:
2895:
2892:
2889:
2886:
2880:
2877:
2876:
2872:
2869:
2866:
2864:
2861:
2858:
2856:
2853:
2851:
2848:
2846:
2843:
2840:
2837:
2834:
2828:
2825:
2824:
2820:
2817:
2815:
2812:
2809:
2806:
2804:
2803:
2799:
2797:
2794:
2791:
2788:
2785:
2782:
2776:
2773:
2772:
2768:
2766:
2763:
2760:
2757:
2755:
2752:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2726:
2723:
2722:
2718:
2715:
2713:
2710:
2707:
2704:
2702:
2701:
2697:
2694:
2691:
2688:
2685:
2682:
2676:
2673:
2672:
2668:
2665:
2662:
2660:
2657:
2654:
2652:
2649:
2647:
2644:
2641:
2638:
2635:
2632:
2626:
2623:
2622:
2618:
2615:
2612:
2609:
2607:
2604:
2602:
2601:
2597:
2594:
2592:
2589:
2586:
2583:
2580:
2574:
2571:
2570:
2566:
2563:
2560:
2557:
2554:
2552:
2549:
2547:
2544:
2541:
2539:
2536:
2533:
2530:
2524:
2521:
2520:
2516:
2513:
2510:
2507:
2504:
2502:
2501:
2497:
2494:
2492:
2489:
2486:
2483:
2480:
2474:
2471:
2470:
2466:
2463:
2460:
2457:
2455:
2452:
2450:
2447:
2445:
2442:
2439:
2436:
2433:
2430:
2424:
2421:
2420:
2416:
2413:
2410:
2408:
2405:
2402:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2376:
2373:
2372:
2368:
2365:
2362:
2359:
2357:
2354:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2328:
2325:
2324:
2320:
2317:
2314:
2311:
2308:
2306:
2305:
2301:
2298:
2295:
2292:
2289:
2286:
2280:
2277:
2276:
2272:
2269:
2266:
2263:
2260:
2258:
2257:
2253:
2251:
2248:
2245:
2242:
2239:
2236:
2230:
2227:
2226:
2223:
2221:
2219:
2217:
2215:
2212:
2210:
2208:
2206:
2204:
2202:
2199:
2196:
2195:
2192:
2188:
2186:
2184:
2180:
2176:
2172:
2162:
2150:
2149:
2142:
2139:
2136:
2133:
2127:
2126:
2119:
2116:
2113:
2110:
2104:
2103:
2096:
2093:
2090:
2087:
2081:
2080:
2073:
2070:
2067:
2064:
2058:
2057:
2050:
2047:
2044:
2041:
2035:
2034:
2027:
2024:
2021:
2018:
2012:
2011:
2004:
2001:
1998:
1995:
1989:
1988:
1981:
1978:
1975:
1972:
1966:
1965:
1958:
1955:
1952:
1949:
1943:
1942:
1938:
1935:
1932:
1929:
1923:
1922:
1919:
1915:
1912:
1909:
1906:
1904:
1900:
1899:
1893:
1890:
1887:
1884:
1883:
1882:
1859:
1855:
1847:
1844:
1838:
1834:
1827:
1824:
1821:
1819:
1816:
1813:
1811:
1808:
1805:
1803:
1800:
1797:
1795:
1792:
1789:
1787:
1784:
1781:
1779:
1776:
1774:
1771:
1768:
1765:
1762:
1759:
1757:
1754:
1751:
1750:
1746:
1744:
1741:
1738:
1736:
1733:
1730:
1728:
1725:
1722:
1720:
1717:
1714:
1712:
1709:
1706:
1704:
1701:
1698:
1696:
1693:
1690:
1687:
1684:
1681:
1679:
1676:
1673:
1672:
1668:
1665:
1663:
1660:
1657:
1655:
1652:
1649:
1647:
1644:
1641:
1639:
1636:
1633:
1631:
1628:
1625:
1623:
1620:
1618:
1615:
1612:
1609:
1606:
1603:
1601:
1598:
1595:
1594:
1590:
1587:
1584:
1582:
1579:
1576:
1574:
1571:
1568:
1566:
1563:
1560:
1558:
1555:
1552:
1550:
1547:
1544:
1542:
1539:
1536:
1533:
1530:
1527:
1525:
1522:
1519:
1518:
1514:
1511:
1508:
1505:
1503:
1500:
1497:
1495:
1492:
1489:
1487:
1484:
1481:
1479:
1476:
1473:
1471:
1468:
1466:
1463:
1460:
1457:
1454:
1451:
1449:
1446:
1443:
1442:
1438:
1435:
1432:
1429:
1426:
1424:
1421:
1418:
1416:
1413:
1410:
1408:
1405:
1402:
1400:
1397:
1394:
1392:
1389:
1386:
1383:
1380:
1377:
1375:
1372:
1369:
1368:
1364:
1361:
1358:
1355:
1352:
1349:
1347:
1344:
1341:
1339:
1336:
1333:
1331:
1328:
1325:
1323:
1320:
1318:
1315:
1312:
1309:
1306:
1303:
1301:
1298:
1295:
1294:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1270:
1267:
1264:
1262:
1259:
1256:
1254:
1251:
1248:
1246:
1243:
1240:
1237:
1234:
1231:
1229:
1226:
1223:
1222:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1195:
1192:
1189:
1187:
1184:
1181:
1179:
1176:
1174:
1171:
1168:
1165:
1162:
1159:
1157:
1154:
1151:
1150:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1120:
1117:
1114:
1112:
1109:
1106:
1104:
1101:
1098:
1095:
1092:
1089:
1087:
1084:
1081:
1080:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1047:
1044:
1041:
1039:
1036:
1034:
1031:
1028:
1025:
1022:
1019:
1017:
1014:
1011:
1010:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
974:
971:
968:
966:
963:
960:
957:
954:
951:
949:
946:
943:
942:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
903:
900:
898:
895:
892:
889:
886:
883:
881:
878:
875:
874:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
832:
829:
826:
823:
820:
817:
815:
812:
809:
808:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
766:
763:
760:
757:
754:
751:
749:
747:
746:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
684:
681:
678:
671:
670:
669:
666:
664:
660:
652:
651:
641:
626:
625:
624:
623:
613:
598:
597:
596:
595:
585:
570:
569:
568:
567:
535:
534:
533:
526:
523:
516:
513:
510:
509:
508:
497:
494:
491:
488:
482:
481:
474:
471:
468:
465:
459:
458:
451:
448:
445:
442:
436:
435:
428:
425:
422:
419:
413:
412:
408:
405:
402:
399:
396:
395:
392:
390:
386:
381:
379:
368:
365:
362:
359:
358:
354:
351:
348:
345:
344:
340:
337:
334:
331:
330:
326:
323:
320:
317:
316:
313:
310:
302:
301:
300:
298:
288:
285:
282:
279:
278:
274:
271:
268:
265:
264:
260:
257:
254:
251:
250:
246:
243:
240:
237:
236:
230:
227:
224:
219:
218:
210:
204:
200:
199:
198:
196:
186:
184:
172:
167:
165:
160:
158:
153:
152:
150:
149:
144:
141:
139:
136:
135:
134:
133:
129:
128:
123:
120:
118:
115:
113:
110:
108:
105:
103:
100:
98:
95:
93:
90:
88:
85:
83:
80:
78:
75:
73:
70:
68:
65:
63:
60:
59:
58:
57:
53:
52:
47:
44:
42:
39:
37:
34:
33:
32:
31:
27:
26:
23:
20:
19:
16:
4572:Nested stack
4515:Context-free
4440:Context-free
4401:Unrestricted
4267:
4260:
4250:
4247:Martin Davis
4232:
4222:
4206:
4187:
4182:
4177:
4171:
4170:
4165:
4160:
4143:
4121:
4116:
4111:
4105:
4104:
4099:
4094:
4077:
4058:
4053:
4048:
4043:
4037:
4036:
4031:
3997:
3992:
3987:
3982:
3977:
3971:
3970:
3947:
3928:
3923:
3918:
3913:
3907:
3906:
3883:
3861:
3856:
3851:
3845:
3844:
3839:
3819:
3794:
3789:
3783:
3782:
3777:
3772:
3755:
3723:
3722:
3717:
3712:
3707:
3693:
3661:
3660:
3655:
3650:
3645:
3640:
3629:
3597:
3596:
3591:
3586:
3581:
3567:
3535:
3534:
3529:
3524:
3507:
3475:
3474:
3469:
3449:
3417:
3416:
3393:
3361:
3360:
3337:
3290:
3274:
3271:
3264:
3253:
3242:
3226:
3215:
3204:
3157:
3151:
3145:
3141:Tape symbol
3134:
3116:
3108:
3103:
3099:
3097:
3093:
3088:
3085:
3073:
3066:
3035:
3019:
3014:
3009:
3004:
2999:
2968:
2963:
2958:
2953:
2948:
2911:
2906:
2898:
2893:
2862:
2854:
2849:
2844:
2813:
2801:
2800:
2795:
2764:
2753:
2748:
2711:
2699:
2698:
2658:
2650:
2645:
2605:
2599:
2598:
2590:
2550:
2545:
2537:
2499:
2498:
2490:
2453:
2448:
2443:
2406:
2398:
2355:
2350:
2303:
2302:
2255:
2254:
2249:
2189:
2182:
2178:
2174:
2170:
2169:
2167:
1917:
1913:Tape motion
1907:Tape symbol
1902:
1860:
1856:
1853:
1845:
1842:
1832:
1825:
1817:
1809:
1801:
1793:
1785:
1777:
1772:
1755:
1742:
1734:
1726:
1718:
1710:
1702:
1694:
1677:
1661:
1653:
1645:
1637:
1629:
1621:
1616:
1599:
1580:
1572:
1564:
1556:
1548:
1540:
1523:
1501:
1493:
1485:
1477:
1469:
1464:
1447:
1422:
1414:
1406:
1398:
1390:
1373:
1345:
1337:
1329:
1321:
1316:
1299:
1268:
1260:
1252:
1244:
1227:
1193:
1185:
1177:
1172:
1155:
1118:
1110:
1102:
1085:
1045:
1037:
1032:
1015:
972:
964:
947:
901:
896:
879:
830:
813:
764:
679:
675:
667:
656:
530:
506:
406:Tape-motion
400:Tape symbol
388:
382:
374:
321:Tape symbol
308:
306:
296:
294:
225:Tape symbol
202:
192:
180:
122:Zeno machine
40:
15:
4581:restricted
3275:Undecidable
3190:Next state
3181:Next state
3172:Next state
3130:Busy Beaver
389:Undecidable
309:Undecidable
297:Undecidable
203:Undecidable
195:Alan Turing
138:Alan Turing
4219:References
3187:Move tape
3178:Move tape
3169:Move tape
4535:Star-free
4489:Positive
4479:Decidable
4414:Positive
4338:Languages
3297:Sequence
2197:Sequence
686:Sequence
564:.21, etc.
366:R, R, P0
352:R, R, P1
215:Behavior
4654:Category
4333:Grammars
3128:3-state
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
701:
698:
695:
692:
233:(state)
222:(state)
54:Variants
4556:Decider
4530:Regular
4497:Indexed
4455:Regular
4422:Indexed
560:go to q
552:go to q
544:go to q
205:p. 119)
197:1937):
130:Science
28:Machine
4608:Finite
4540:Finite
4385:Type-3
4376:Type-2
4358:Type-1
4352:Type-0
4239:
3089:finite
2185:othing
489:blank
466:blank
443:blank
420:blank
283:blank
272:P1, R
269:blank
255:blank
244:P0, R
241:blank
4566:PTIME
3315:Head
2213:Head
704:Head
335:None
4313:and
4237:ISBN
3265:HALT
4140:14
4074:13
4010:12
3944:11
3880:10
3056:. s
2984:16
2930:15
2878:14
2826:13
2774:12
2724:11
2674:10
2137:P1
2114:P1
2091:P1
2045:P1
2022:P1
1999:P1
1877:, s
1873:, s
1869:, s
1865:, s
1752:14
1674:13
1596:12
1520:11
1444:10
639:.22
611:.12
583:.02
469:P1
423:P0
338:P0
4656::
4309::
4227:.
4201:0
4198:0
4195:0
4192:0
4157:0
4154:0
4151:0
4148:0
4135:0
4132:0
4129:0
4126:0
4091:0
4088:0
4085:0
4082:0
4069:0
4066:0
4063:0
4028:0
4025:0
4022:0
4019:0
4016:0
4013:A
4005:0
4002:0
3967:0
3964:0
3961:0
3958:0
3955:0
3952:0
3939:0
3936:0
3933:0
3903:0
3900:0
3897:0
3894:0
3891:0
3888:0
3875:0
3872:0
3869:0
3866:0
3836:0
3833:0
3830:0
3827:0
3824:0
3816:9
3811:0
3808:0
3805:0
3802:0
3799:0
3769:0
3766:0
3763:0
3760:0
3752:8
3747:0
3744:0
3741:0
3738:0
3735:0
3732:0
3729:1
3704:0
3701:0
3698:0
3690:7
3685:0
3682:0
3679:0
3676:0
3673:0
3670:0
3667:0
3637:0
3634:0
3626:6
3621:0
3618:0
3615:0
3612:0
3609:0
3606:0
3603:0
3578:0
3575:0
3572:0
3564:5
3559:0
3556:0
3553:0
3550:0
3547:0
3544:0
3541:0
3521:0
3518:0
3515:0
3512:0
3504:4
3499:0
3496:0
3493:0
3490:0
3487:0
3484:0
3481:0
3466:0
3463:0
3460:0
3457:0
3454:0
3446:3
3441:0
3438:0
3435:0
3432:0
3429:0
3426:0
3423:1
3413:0
3410:0
3407:0
3404:0
3401:0
3398:0
3390:2
3385:0
3382:0
3379:0
3376:0
3373:0
3370:0
3367:0
3357:0
3354:0
3351:0
3348:0
3345:0
3342:0
3334:1
3281::
3261:N
3258:1
3250:R
3247:1
3239:L
3236:1
3233:1
3223:L
3220:1
3212:L
3209:1
3201:R
3198:1
3195:0
3114:.
3064:.
3030:0
3027:0
3024:0
2996:0
2993:0
2990:0
2987:H
2979:0
2976:0
2973:0
2945:0
2942:0
2939:0
2925:0
2922:0
2919:0
2916:0
2903:0
2890:0
2887:0
2873:0
2870:0
2867:0
2859:0
2841:0
2838:0
2835:0
2821:0
2818:0
2810:0
2807:0
2792:0
2789:0
2786:0
2783:0
2769:0
2761:0
2758:0
2745:0
2742:0
2739:0
2736:0
2733:0
2719:0
2716:0
2708:0
2705:0
2695:0
2692:0
2689:0
2686:0
2683:0
2669:0
2666:0
2663:0
2655:0
2642:0
2639:0
2636:0
2633:0
2624:9
2619:0
2616:0
2613:0
2610:0
2595:0
2587:0
2584:0
2581:0
2572:8
2567:0
2564:0
2561:0
2558:0
2555:0
2542:0
2534:0
2531:0
2522:7
2517:0
2514:0
2511:0
2508:0
2505:0
2495:0
2487:0
2484:0
2481:0
2472:6
2467:0
2464:0
2461:0
2458:0
2440:0
2437:0
2434:0
2431:0
2422:5
2417:0
2414:0
2411:0
2403:0
2395:0
2392:0
2389:0
2386:0
2383:0
2374:4
2369:0
2366:0
2363:0
2360:0
2347:0
2344:0
2341:0
2338:0
2335:0
2326:3
2321:0
2318:0
2315:0
2312:0
2309:0
2299:0
2296:0
2293:0
2290:0
2287:0
2278:2
2273:0
2270:0
2267:0
2264:0
2261:0
2246:0
2243:0
2240:0
2237:0
2228:1
2173::
2160:—
2157:—
2154:—
2151:H
2140:L
2134:1
2117:R
2111:0
2094:L
2088:1
2071:L
2068:E
2065:0
2048:R
2042:1
2025:L
2019:0
2002:R
1996:1
1979:R
1976:E
1973:0
1956:R
1953:E
1950:1
1939:H
1936:N
1933:N
1930:0
1822:.
1814:.
1806:.
1798:.
1790:.
1782:.
1769:.
1766:.
1763:.
1760:.
1747:.
1739:.
1731:.
1723:.
1715:.
1707:.
1699:.
1691:.
1688:.
1685:.
1682:.
1669:.
1666:.
1658:.
1650:.
1642:.
1634:.
1626:.
1613:.
1610:.
1607:.
1604:.
1591:.
1588:.
1585:.
1577:.
1569:.
1561:.
1553:.
1545:.
1537:.
1534:.
1531:.
1528:.
1515:.
1512:.
1509:.
1506:.
1498:.
1490:.
1482:.
1474:.
1461:.
1458:.
1455:.
1452:.
1439:.
1436:.
1433:.
1430:.
1427:.
1419:.
1411:.
1403:.
1395:.
1387:.
1384:.
1381:.
1378:.
1370:9
1365:.
1362:.
1359:.
1356:.
1353:.
1350:.
1342:.
1334:.
1326:.
1313:.
1310:.
1307:.
1304:.
1296:8
1291:.
1288:.
1285:.
1282:.
1279:.
1276:.
1273:.
1265:.
1257:.
1249:.
1241:.
1238:.
1235:.
1232:.
1224:7
1219:.
1216:.
1213:.
1210:.
1207:.
1204:.
1201:.
1198:.
1190:.
1182:.
1169:.
1166:.
1163:.
1160:.
1152:6
1147:.
1144:.
1141:.
1138:.
1135:.
1132:.
1129:.
1126:.
1123:.
1115:.
1107:.
1099:.
1096:.
1093:.
1090:.
1082:5
1077:.
1074:.
1071:.
1068:.
1065:.
1062:.
1059:.
1056:.
1053:.
1050:.
1042:.
1029:.
1026:.
1023:.
1020:.
1012:4
1007:.
1004:.
1001:.
998:.
995:.
992:.
989:.
986:.
983:.
980:.
977:.
969:.
961:.
958:.
955:.
952:.
944:3
939:.
936:.
933:.
930:.
927:.
924:.
921:.
918:.
915:.
912:.
909:.
906:.
893:.
890:.
887:.
884:.
876:2
871:.
868:.
865:.
862:.
859:.
856:.
853:.
850:.
847:.
844:.
841:.
838:.
835:.
827:.
824:.
821:.
818:.
810:1
805:.
802:.
799:.
796:.
793:.
790:.
787:.
784:.
781:.
778:.
775:.
772:.
769:.
761:.
758:.
755:.
752:.
665:.
642:(q
627:(q
614:(q
599:(q
586:(q
571:(q
536:(q
495:R
472:R
449:R
426:R
380:.
369:b
363:1
360:b
355:b
349:0
346:b
341:b
332:b
289:b
286:R
280:f
275:f
266:e
261:e
258:R
252:c
247:c
238:b
185:.
4501:—
4459:—
4426:—
4391:—
4388:—
4382:—
4379:—
4373:—
4370:—
4367:—
4364:—
4361:—
4355:—
4299:e
4292:t
4285:v
4188:1
4183:1
4178:1
4172:1
4166:1
4161:1
4144:H
4122:1
4117:1
4112:1
4106:1
4100:1
4095:1
4078:C
4059:1
4054:1
4049:1
4044:1
4038:1
4032:1
3998:1
3993:1
3988:1
3983:1
3978:1
3972:0
3948:B
3929:1
3924:1
3919:1
3914:1
3908:1
3884:B
3862:1
3857:1
3852:1
3846:1
3840:1
3820:B
3795:1
3790:1
3784:1
3778:1
3773:1
3756:B
3724:1
3718:1
3713:1
3708:1
3694:B
3662:0
3656:1
3651:1
3646:1
3641:1
3630:A
3598:0
3592:1
3587:1
3582:1
3568:B
3536:0
3530:1
3525:1
3508:C
3476:1
3470:1
3450:A
3418:0
3394:B
3362:0
3338:b
3273:(
3254:B
3243:C
3227:B
3216:A
3205:B
3158:C
3152:B
3146:A
3076:1
3069:1
3062:1
3058:5
3054:5
3050:4
3046:3
3042:2
3038:1
3020:1
3015:1
3010:0
3005:1
3000:1
2969:1
2964:1
2959:0
2954:1
2949:1
2935:1
2933:s
2912:1
2907:0
2899:1
2894:1
2883:5
2881:s
2863:1
2855:0
2850:1
2845:1
2831:4
2829:s
2814:1
2802:1
2796:1
2779:4
2777:s
2765:1
2754:1
2749:0
2729:3
2727:s
2712:1
2700:1
2679:3
2677:s
2659:1
2651:0
2646:1
2629:2
2627:s
2606:1
2600:1
2591:1
2577:1
2575:s
2551:0
2546:1
2538:1
2527:5
2525:s
2500:1
2491:1
2477:5
2475:s
2454:1
2449:0
2444:1
2427:4
2425:s
2407:1
2399:0
2379:3
2377:s
2356:1
2351:0
2331:2
2329:s
2304:1
2283:2
2281:s
2256:1
2250:1
2233:1
2231:s
2183:N
2179:E
2175:P
2145:5
2143:s
2130:5
2128:s
2122:1
2120:s
2107:5
2105:s
2099:4
2097:s
2084:4
2082:s
2076:5
2074:s
2061:4
2059:s
2053:3
2051:s
2038:3
2036:s
2030:4
2028:s
2015:3
2013:s
2007:2
2005:s
1992:2
1990:s
1984:3
1982:s
1969:2
1967:s
1961:2
1959:s
1946:1
1944:s
1926:1
1924:s
1879:5
1875:4
1871:3
1867:2
1863:1
1826:0
1818:1
1810:0
1802:1
1794:0
1786:1
1778:0
1773:.
1756:2
1743:0
1735:1
1727:0
1719:1
1711:0
1703:1
1695:.
1678:1
1662:0
1654:1
1646:0
1638:1
1630:0
1622:1
1617:.
1600:4
1581:0
1573:1
1565:0
1557:1
1549:0
1541:.
1524:3
1502:0
1494:1
1486:0
1478:1
1470:0
1465:.
1448:2
1423:0
1415:1
1407:0
1399:1
1391:.
1374:1
1346:0
1338:1
1330:0
1322:1
1317:.
1300:4
1269:0
1261:1
1253:0
1245:.
1228:3
1194:0
1186:1
1178:0
1173:.
1156:2
1119:0
1111:1
1103:.
1086:1
1046:0
1038:1
1033:.
1016:4
973:0
965:.
948:3
902:0
897:.
880:2
831:.
814:1
765:.
644:i
637:i
633:j
629:i
616:i
609:i
605:j
601:i
588:i
581:i
577:j
573:i
562:i
558:2
554:i
550:1
546:i
542:0
538:i
519:j
500:1
498:q
485:4
483:q
477:4
475:q
462:3
460:q
454:3
452:q
439:2
437:q
431:2
429:q
416:1
414:q
170:e
163:t
156:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
