2118:). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set
766:
A great deal of research has been conducted into the structure of the Turing degrees. The following survey lists only some of the many known results. One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated.
77:
if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are
2122:
is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result.
1901:
3524:
2090:, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set
1835:
1759:
70:. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set.
1589:
1471:
408:. (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with , the boldface is not necessary.)
1530:
1954:
861:
755:
687:
1238:
1208:
1168:
888:
547:
503:
406:
360:
993:
650:
1840:
3152:
1927:
1323:
1299:
3574:
3457:
2788:
2720:
2641:
2611:
3545:
109:. The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the
3552:
3531:
1405:
can be embedded in the r.e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right.
1254:
380:. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted
2822:
2766:
2683:
2585:
2532:
2520:
2498:
2801:(1993). "The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond". In Univ. Nac. del Sur, Bahía Blanca (ed.).
1974:
2114:
to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be
3602:
2004:
3597:
3266:
2738:
1803:
1688:
3027:
Lachlan, Alistair H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees",
1270:
3450:
2891:
1546:
965:
2007:). Their proofs each developed the same new method for constructing r.e. degrees, which came to be known as the
2671:
564:′ denotes the set of indices of oracle machines that halt (when given their index as input) when using
2929:
98:. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.
3070:
3105:
3005:
1432:
1126:
3569:
3271:
2952:
2629:
2595:
146:
1484:
3150:
Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems",
2815:
Recursively
Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets
3607:
3443:
2776:
1996:
1932:
1392:
1381:
832:
726:
658:
231:
63:
3010:
1219:
1189:
1149:
869:
528:
484:
387:
341:
3538:
3477:
3110:
2131:
1385:
2154:
be the output (binary) tape, identified with the set of cell indices where we placed 1 so far (so
3361:
3353:
3296:
3210:
3139:
3052:
3044:
2977:
2916:
2908:
2866:
2803:
Proceedings of the IX Latin
American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992)
2726:
2659:
1983:
studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between
1179:
1143:
971:
628:
622:
582:. The Turing jump of a degree is defined to be the degree ; this is a valid definition because
470:
35:
2636:. Studies in Logic and the Foundations of Mathematics. Vol. 143. Amsterdam: North-Holland.
2606:. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam: North-Holland.
2546:
3497:
3288:
3247:
3171:
3123:
2969:
2818:
2784:
2762:
2716:
2689:
2679:
2637:
2607:
2581:
2528:
2516:
2494:
1122:
327:
3502:
3345:
3325:
3280:
3237:
3202:
3161:
3115:
3079:
3036:
3015:
2961:
2900:
2848:
2754:
2011:. The priority method is now the main technique for establishing results about r.e. sets.
506:
137:
122:
90:, then any (possibly noncomputable) procedure that correctly decides whether numbers are in
67:
31:
3308:
3259:
3183:
3135:
2989:
2862:
2651:
2621:
1896:{\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}
3304:
3255:
3225:
3179:
3131:
3093:
3065:
2996:
Lachlan, Alistair H. (1966a), "Lower Bounds for Pairs of
Recursively Enumerable Degrees",
2985:
2858:
2832:
2810:
2647:
2617:
1991:. The problem of constructing such a degree (or showing that none exist) became known as
1422:
1410:
1402:
1388:
1183:
891:
609:
550:
94:
can be effectively converted to a procedure that correctly decides whether numbers are in
3068:(1980), "Not every finite lattice is embeddable in the recursively enumerable degrees",
2950:; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability",
1332:: The r.e. degrees are dense; between any two r.e. degrees there is a third r.e. degree.
3492:
3487:
2947:
2600:
2471:
2000:
1912:
1406:
1308:
1284:
51:
17:
2758:
2567:
Epstein, R.L.; Haas, R; Kramer, L.R. (1981). Leman, M; Schmerl, J.; Soare, R. (eds.).
2141:′=0′) can be constructed in infinitely many stages as follows. At the start of stage
3591:
3221:
3084:
2798:
2664:
2508:
716:
366:
79:
3365:
3166:
3143:
3056:
2920:
2870:
2853:
2836:
1473:
iff there is a "recursive approximation" to its characteristic function: a function
3190:
3096:(1998), "Interpretability and definability in the recursively enumerable degrees",
2708:
3507:
3466:
1017:. In fact, there is a countable family of pairwise incomparable degrees between
801:
574:
43:
3242:
3019:
3119:
2127:
1342:: There are two r.e. degrees with no greatest lower bound in the r.e. degrees.
914:, ... of Turing degrees cannot have a least upper bound, but it always has an
3329:
3292:
3251:
3175:
3127:
2973:
2904:
2693:
3316:
Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees",
2730:
2675:
1980:
897:
Every countable partially ordered set can be embedded in the Turing degrees.
1216:
showed that the jump operator is definable in the first-order structure of
3336:
Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees",
3269:(1977b). "First-order theory of the degrees of recursive unsolvability".
2750:
2912:
2886:
2003:
in the 1950s, who showed that these intermediate r.e. degrees do exist (
1352:: There is a pair of nonzero r.e. degrees whose greatest lower bound is
3357:
3300:
3214:
3048:
2981:
1417:): The first-order theory of the r.e. degrees in the language ⟨
1973:"Post's problem" redirects here. For the other "Post's problem", see
3349:
3284:
3206:
3040:
2965:
968:, it can be shown there is a maximal chain of degrees of order type
1429:
Additionally, there is
Shoenfield's limit lemma, a set A satisfies
1253:
2378:
from disrupting the halt; all priorities are eventually constant.
2211:, if possible (otherwise do nothing in the stage), pick the least
2110:
has been enumerated). Sometimes, a number can be enumerated into
1362:: There is no pair of r.e. degrees whose greatest lower bound is
2426:
is noncomputable since otherwise a Turing machine could halt on
3439:
3422:
3420:
3418:
2817:. Perspectives in Mathematical Logic. Berlin: Springer-Verlag.
2571:. Lecture Notes in Mathematics. Vol. 859. Springer-Verlag.
2515:. Cambridge-New York: Cambridge University Press. p. 251.
866:
There are pairs of degrees with no greatest lower bound. Thus
334:. The notation denotes the equivalence class containing a set
3435:
1421:, ≤, = ⟩ is many-one equivalent to the theory of
1384:
can be embedded into the r.e. degrees. In fact, the countable
553:, as there are pairs of degrees with no greatest lower bound.
2715:. Annals of Mathematics Studies. Princeton University Press.
2422:
steps (by recursion, this is uniformly computable from 0′).
2578:
Degrees of unsolvability. Perspectives in
Mathematical Logic
2358:
to ∞, and then set one priority ∞ cell (any will do) not in
2014:
The idea of the priority method for constructing a r.e. set
1257:
A finite lattice that can't be embedded in the r.e. degrees.
1225:
1195:
1155:
875:
534:
490:
393:
347:
54:
measures the level of algorithmic unsolvability of the set.
2513:
Computability, an introduction to recursive function theory
1777:-r.e. degree is a strict subclass of the class of sets of (
2741:(1977a). "Degrees of Unsolvability: A Survey of Results".
2666:
Theory of
Recursive Functions and Effective Computability
3193:(1964), "The recursively enumerable degrees are dense",
2745:. Studies in Logic and the Foundations of Mathematics.
2493:. Boca Raton, FL: Chapman & Hall/CRC. p. 424.
2094:
is enumerated. At each stage, numbers may be put into
2370:
halt if we can do so without upsetting priorities <
2106:
requirements (that is, force them to hold once all of
807:
The Turing degrees are not linearly ordered by ≤
66:, where sets of natural numbers are often regarded as
1935:
1915:
1843:
1806:
1691:
1549:
1487:
1435:
1311:
1287:
1222:
1192:
1152:
974:
961:), and thus it has (non-unique) minimal upper bounds.
872:
835:
729:
661:
631:
531:
487:
390:
344:
338:. The entire collection of Turing degrees is denoted
2098:
or forever (if not injured) prevented from entering
1129:
and finitely iterated Turing jumps of the empty set.
384:(zero) because it is the least element of the poset
3562:
3516:
2930:"The Turing degrees and their lack of linear order"
2192:) be the priority for not outputting 1 at location
2026:must satisfy. For example, to construct a r.e. set
2663:
2599:
2545:Ambos-Spies, Klaus; Fejer, Peter (20 March 2006).
2438:is nonempty, contradicting the construction since
2374:, and then set priorities to prevent machines >
1948:
1921:
1895:
1829:
1753:
1583:
1524:
1465:
1317:
1293:
1232:
1202:
1162:
987:
882:
855:
800:. Thus the order relation on the degrees is not a
749:
681:
644:
541:
497:
400:
354:
3426:
2805:. Notas Lógica Mat. Vol. 38. pp. 61–70.
1830:{\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }
1754:{\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}
369:≤ defined so that ≤ if and only if
105:and many fundamental results were established by
2539:Monographs and survey articles (graduate level)
1968:
1644:(Removing this condition yields a definition of
1414:
1125:establishes a close correspondence between the
131:will refer to a set of natural numbers. A set
62:The concept of Turing degree is fundamental in
3098:Proceedings of the London Mathematical Society
2998:Proceedings of the London Mathematical Society
3451:
3153:Bulletin of the American Mathematical Society
8:
2078:requires that the Turing machine with index
2063:requires that the oracle machine with index
1995:. This problem was solved independently by
1890:
1844:
1748:
1692:
1398:
226:are Turing equivalent. The relation ≡
1584:{\displaystyle (A_{s})_{s\in \mathbb {N} }}
1391:can be embedded in a manner that preserves
1213:
3458:
3444:
3436:
792:is nonzero and there is no degree between
106:
3409:
3385:
3241:
3165:
3109:
3083:
3009:
2852:
2837:"Recursively enumerable sets and degrees"
2038:it is enough to satisfy the requirements
1936:
1934:
1914:
1885:
1879:
1870:
1864:
1855:
1847:
1842:
1822:
1816:
1807:
1805:
1727:
1705:
1690:
1575:
1574:
1567:
1557:
1548:
1507:
1486:
1449:
1434:
1310:
1286:
1224:
1223:
1221:
1194:
1193:
1191:
1154:
1153:
1151:
979:
973:
900:An infinite strictly increasing sequence
874:
873:
871:
845:
840:
834:
739:
734:
728:
671:
666:
660:
636:
630:
533:
532:
530:
489:
488:
486:
431:, is defined to be the union of the sets
392:
391:
389:
346:
345:
343:
86:is less than the Turing degree of a set
2885:Chong, C.T.; Yu, Liang (December 2007).
1543:-r e. if there is a family of functions
1377:
1359:
1345:
1335:
1252:
1186:. This indicates that the structure of
1139:
82:, so that if the Turing degree of a set
3397:
3378:
2928:DeAntonio, Jasper (24 September 2010).
2569:Hierarchies of sets and degrees below 0
1370:. This result is informally called the
153:when given an oracle for membership in
127:For the rest of this article, the word
2887:"Maximal Chains in the Turing Degrees"
1969:Post's problem and the priority method
616:Basic properties of the Turing degrees
101:The Turing degrees were introduced by
2086:. These requirements are put into a
1349:
1339:
1329:
1249:Recursively enumerable Turing degrees
1176:⟨ ≤, ′, = ⟩
863:pairwise incomparable Turing degrees.
7:
3546:Computing Machinery and Intelligence
3228:(1999), "Defining the Turing jump",
1466:{\displaystyle \leq _{T}\emptyset '}
102:
3553:The Chemical Basis of Morphogenesis
2634:Classical recursion theory. Vol. II
2018:is to list a countable sequence of
1009:there is a degree strictly between
719:. The set of degrees greater than
509:. The least upper bound of degrees
3532:Systems of Logic Based on Ordinals
1960:+1)-r.e. iff both sets are weakly-
1642:with its characteristic function.
1456:
842:
814:In fact, for every nonzero degree
736:
668:
633:
25:
2082:(and no oracle) does not compute
1525:{\displaystyle g(s)=\chi _{A}(s)}
1477:such that for sufficiently large
3092:Nies, André; Shore, Richard A.;
2483:Monographs (undergraduate level)
2366:. Essentially, we make machine
1886:
1871:
1856:
1848:
1823:
1808:
1601:is a recursive approximation of
234:, which means that for all sets
3427:Epstein, Haas & Kramer 1981
3167:10.1090/S0002-9904-1944-08111-1
2854:10.1090/S0002-9904-1978-14552-2
2354:)), and set all priorities >
2130:(and hence noncomputable r.e.)
2067:does not compute 0′ from
1949:{\displaystyle {\overline {A}}}
1415:Nies, Shore & Slaman (1998)
1366:and whose least upper bound is
856:{\displaystyle 2^{\aleph _{0}}}
762:Structure of the Turing degrees
750:{\displaystyle 2^{\aleph _{0}}}
682:{\displaystyle 2^{\aleph _{0}}}
625:, that is, it contains exactly
3318:Z. Math. Logik Grundlag. Math.
1745:
1739:
1717:
1711:
1564:
1550:
1519:
1513:
1497:
1491:
1442:
1436:
1233:{\displaystyle {\mathcal {D}}}
1203:{\displaystyle {\mathcal {D}}}
1163:{\displaystyle {\mathcal {D}}}
1086:There is an infinite sequence
883:{\displaystyle {\mathcal {D}}}
542:{\displaystyle {\mathcal {D}}}
498:{\displaystyle {\mathcal {D}}}
401:{\displaystyle {\mathcal {D}}}
355:{\displaystyle {\mathcal {D}}}
1:
3230:Mathematical Research Letters
2759:10.1016/S0049-237X(08)71117-0
2743:Annals of Mathematics Studies
1975:Post's correspondence problem
1277:, but not every degree below
1273:. Every r.e. degree is below
1000:Properties involving the jump
3085:10.1016/0001-8708(80)90027-4
2446:cells for arbitrarily large
2293:. Choose any such (finite)
1941:
1638:), in particular conflating
1242:⟨ ≤, = ⟩
1184:true second-order arithmetic
1172:⟨ ≤, = ⟩
2580:. Berlin: Springer-Verlag.
2454:is simple because for each
1685:)=0 and the cardinality of
1670:-trial predicate": for all
1423:true first-order arithmetic
988:{\displaystyle \omega _{1}}
711:, the set of degrees below
645:{\displaystyle \aleph _{0}}
608:′, the degree of the
149:that decides membership in
3624:
3243:10.4310/mrl.1999.v6.n6.a10
2783:. North-Holland/Elsevier.
2602:Classical Recursion Theory
2547:"Degrees of Unsolvability"
1972:
1399:Lachlan & Soare (1980)
1271:recursively enumerable set
365:The Turing degrees have a
120:
3473:
3338:Journal of Symbolic Logic
3120:10.1112/S002461159800046X
2892:Journal of Symbolic Logic
2005:Friedberg–Muchnik theorem
1301:is many-one reducible to
1214:Shore & Slaman (1999)
1210:is extremely complicated.
1028:Jump inversion: a degree
966:axiom of constructibility
3330:10.1002/malq.19710170131
3020:10.1112/plms/s3-16.1.537
2781:Degrees of Unsolvability
2713:Degrees of Unsolvability
2672:Cambridge, Massachusetts
2052:for each natural number
1837:, such that the segment
1281:is r.e.. However, a set
1269:(c.e.) if it contains a
689:distinct Turing degrees.
461:}. The Turing degree of
107:Kleene & Post (1954)
27:Measure of unsolvability
3071:Advances in Mathematics
2458:the number of priority
2442:excludes some priority
2406:such that machines <
621:Every Turing degree is
568:as an oracle. The set
330:of the relation ≡
203:is Turing reducible to
195:is Turing reducible to
172:is Turing reducible to
48:degree of unsolvability
18:Degree of unsolvability
3064:Lachlan, Alistair H.;
2905:10.2178/jsl/1203350783
2630:Odifreddi, Piergiorgio
2596:Odifreddi, Piergiorgio
1950:
1923:
1897:
1831:
1755:
1585:
1526:
1467:
1319:
1295:
1263:recursively enumerable
1258:
1234:
1204:
1164:
1127:arithmetical hierarchy
989:
884:
857:
751:
696:the strict inequality
683:
646:
572:′ is called the
543:
499:
402:
356:
3603:Theory of computation
3570:Legacy of Alan Turing
3539:Intelligent Machinery
3525:On Computable Numbers
3272:Annals of Mathematics
3195:Annals of Mathematics
2953:Annals of Mathematics
2841:Bull. Amer. Math. Soc
2777:Shoenfield, Joseph R.
2489:Cooper, S.B. (2004).
2311:, and for every cell
1951:
1924:
1898:
1832:
1788:>1 there are two (
1773:The class of sets of
1756:
1586:
1527:
1468:
1320:
1296:
1267:computably enumerable
1256:
1235:
1205:
1165:
1095:of degrees such that
990:
885:
858:
752:
684:
647:
544:
500:
403:
357:
230:can be seen to be an
147:oracle Turing machine
3598:Computability theory
3066:Soare, Robert Irving
2948:Kleene, Stephen Cole
2833:Soare, Robert Irving
2811:Soare, Robert Irving
2491:Computability theory
2393:iff it halts in <
2247:steps on some input
1933:
1913:
1841:
1804:
1689:
1547:
1485:
1433:
1382:distributive lattice
1309:
1285:
1220:
1190:
1150:
972:
870:
833:
727:
659:
629:
529:
525:. It is known that
485:
388:
342:
232:equivalence relation
64:computability theory
3478:Turing completeness
3412:, p. 252, 258.
3398:Chong & Yu 2007
3267:Simpson, Stephen G.
3226:Slaman, Theodore A.
3094:Slaman, Theodore A.
2576:Lerman, M. (1983).
2315:visited by machine
2239:and Turing machine
1261:A degree is called
1180:many-one equivalent
604:. A key example is
2739:Simpson, Steven G.
1946:
1919:
1893:
1827:
1751:
1581:
1522:
1463:
1393:suprema and infima
1372:nondiamond theorem
1315:
1291:
1259:
1240:with the language
1230:
1200:
1160:
1144:first-order theory
1134:Logical properties
1051:there is a degree
985:
880:
853:
829:There is a set of
822:incomparable with
818:there is a degree
747:
679:
642:
623:countably infinite
539:
495:
473:of the degrees of
398:
352:
187:are defined to be
117:Turing equivalence
36:mathematical logic
3585:
3584:
3275:. Second Series.
3222:Shore, Richard A.
3197:, Second Series,
2956:, Second Series,
2790:978-0-7204-2061-6
2722:978-0-6910-7941-7
2643:978-0-444-50205-6
2613:978-0-444-87295-1
2509:Cutland, Nigel J.
2462:cells is finite.
2102:in an attempt to
2088:priority ordering
1944:
1922:{\displaystyle A}
1792:+1)-r.e. degrees
1401:: Not all finite
1318:{\displaystyle A}
1294:{\displaystyle A}
1182:to the theory of
1005:For every degree
593:′ whenever
471:least upper bound
328:equivalence class
189:Turing equivalent
80:partially ordered
75:Turing equivalent
68:decision problems
16:(Redirected from
3615:
3503:Turing reduction
3460:
3453:
3446:
3437:
3430:
3424:
3413:
3407:
3401:
3395:
3389:
3383:
3368:
3332:
3312:
3262:
3245:
3217:
3186:
3169:
3146:
3113:
3088:
3087:
3060:
3023:
3013:
2992:
2943:
2941:
2939:
2934:
2924:
2899:(4): 1219–1227.
2874:
2856:
2847:(6): 1149–1181.
2828:
2806:
2794:
2772:
2734:
2704:
2702:
2700:
2669:
2655:
2625:
2605:
2591:
2572:
2563:
2558:
2556:
2551:
2526:
2504:
2385:is low, machine
1955:
1953:
1952:
1947:
1945:
1937:
1928:
1926:
1925:
1920:
1902:
1900:
1899:
1894:
1889:
1884:
1883:
1874:
1869:
1868:
1859:
1851:
1836:
1834:
1833:
1828:
1826:
1821:
1820:
1811:
1781:+1)-r.e. degree.
1760:
1758:
1757:
1752:
1738:
1737:
1710:
1709:
1590:
1588:
1587:
1582:
1580:
1579:
1578:
1562:
1561:
1531:
1529:
1528:
1523:
1512:
1511:
1472:
1470:
1469:
1464:
1462:
1454:
1453:
1407:L. A. Harrington
1324:
1322:
1321:
1316:
1300:
1298:
1297:
1292:
1243:
1239:
1237:
1236:
1231:
1229:
1228:
1209:
1207:
1206:
1201:
1199:
1198:
1177:
1173:
1170:in the language
1169:
1167:
1166:
1161:
1159:
1158:
1142:showed that the
1071:; such a degree
994:
992:
991:
986:
984:
983:
889:
887:
886:
881:
879:
878:
862:
860:
859:
854:
852:
851:
850:
849:
771:Order properties
756:
754:
753:
748:
746:
745:
744:
743:
707:For each degree
692:For each degree
688:
686:
685:
680:
678:
677:
676:
675:
651:
649:
648:
643:
641:
640:
548:
546:
545:
540:
538:
537:
507:join-semilattice
504:
502:
501:
496:
494:
493:
460:
445:
407:
405:
404:
399:
397:
396:
361:
359:
358:
353:
351:
350:
207:. The notation
157:. The notation
138:Turing reducible
123:Turing reduction
32:computer science
21:
3623:
3622:
3618:
3617:
3616:
3614:
3613:
3612:
3588:
3587:
3586:
3581:
3558:
3512:
3469:
3464:
3434:
3433:
3425:
3416:
3408:
3404:
3400:, p. 1224.
3396:
3392:
3384:
3380:
3375:
3350:10.2307/2269807
3335:
3315:
3285:10.2307/1971028
3265:
3220:
3207:10.2307/1970393
3189:
3149:
3091:
3063:
3041:10.2307/2270459
3026:
3011:10.1.1.106.7893
2995:
2966:10.2307/1969708
2946:
2937:
2935:
2932:
2927:
2884:
2881:
2879:Research papers
2831:
2825:
2809:
2797:
2791:
2775:
2769:
2737:
2723:
2707:
2698:
2696:
2686:
2660:Rogers, Hartley
2658:
2644:
2628:
2614:
2594:
2588:
2575:
2566:
2554:
2552:
2549:
2544:
2541:
2523:
2507:
2501:
2488:
2485:
2480:
2468:
2405:
2349:
2332:
2306:
2284:
2276:
2259:
2230:
2207:)=∞. At stage
2202:
2187:
2178:
2171:
2163:
2153:
2126:For example, a
2076:
2061:
2050:
2043:
2009:priority method
1978:
1971:
1931:
1930:
1911:
1910:
1875:
1860:
1839:
1838:
1812:
1802:
1801:
1769:-r.e. degrees:
1723:
1701:
1687:
1686:
1680:
1665:
1625:
1600:
1563:
1553:
1545:
1544:
1503:
1483:
1482:
1455:
1445:
1431:
1430:
1389:Boolean algebra
1380:: Every finite
1378:Thomason (1971)
1360:Lachlan (1966b)
1346:Lachlan (1966a)
1336:Lachlan (1966a)
1307:
1306:
1283:
1282:
1251:
1241:
1218:
1217:
1188:
1187:
1175:
1171:
1148:
1147:
1140:Simpson (1977b)
1136:
1114:
1105:
1094:
1047:For any degree
1036:if and only if
1032:is of the form
1002:
975:
970:
969:
960:
913:
906:
868:
867:
841:
836:
831:
830:
810:
778:minimal degrees
773:
764:
735:
730:
725:
724:
667:
662:
657:
656:
632:
627:
626:
618:
610:halting problem
600:
589:
586:′ ≡
527:
526:
483:
482:
447:
432:
386:
385:
376:
340:
339:
333:
314:
303:
292:
279:
268:
256:
229:
218:indicates that
214:
168:indicates that
164:
145:if there is an
125:
119:
111:priority method
60:
52:natural numbers
28:
23:
22:
15:
12:
11:
5:
3621:
3619:
3611:
3610:
3605:
3600:
3590:
3589:
3583:
3582:
3580:
3579:
3578:
3577:
3566:
3564:
3560:
3559:
3557:
3556:
3549:
3542:
3535:
3528:
3520:
3518:
3514:
3513:
3511:
3510:
3505:
3500:
3498:Turing's proof
3495:
3493:Turing pattern
3490:
3488:Turing machine
3485:
3480:
3474:
3471:
3470:
3465:
3463:
3462:
3455:
3448:
3440:
3432:
3431:
3414:
3410:Odifreddi 1989
3402:
3390:
3386:DeAntonio 2010
3377:
3376:
3374:
3371:
3370:
3369:
3344:(2): 159–168,
3333:
3313:
3279:(1): 121–139.
3263:
3236:(6): 711–722,
3218:
3201:(2): 300–312,
3187:
3160:(5): 284–316,
3147:
3111:10.1.1.29.9588
3104:(2): 241–291,
3089:
3061:
3035:(3): 434–454,
3024:
3004:(1): 537–569,
2993:
2960:(3): 379–407,
2944:
2925:
2880:
2877:
2876:
2875:
2829:
2823:
2807:
2795:
2789:
2773:
2767:
2735:
2721:
2705:
2684:
2656:
2642:
2626:
2612:
2592:
2586:
2573:
2564:
2540:
2537:
2536:
2535:
2521:
2505:
2499:
2484:
2481:
2479:
2476:
2475:
2474:
2472:Martin measure
2467:
2464:
2401:
2397:steps on some
2345:
2327:
2301:
2280:
2272:
2255:
2226:
2200:
2183:
2176:
2167:
2159:
2149:
2074:
2059:
2048:
2041:
1993:Post's problem
1970:
1967:
1966:
1965:
1943:
1940:
1918:
1908:
1907:-r.e. degrees.
1892:
1888:
1882:
1878:
1873:
1867:
1863:
1858:
1854:
1850:
1846:
1825:
1819:
1815:
1810:
1782:
1765:Properties of
1763:
1762:
1750:
1747:
1744:
1741:
1736:
1733:
1730:
1726:
1722:
1719:
1716:
1713:
1708:
1704:
1700:
1697:
1694:
1678:
1663:
1658:
1621:
1598:
1577:
1573:
1570:
1566:
1560:
1556:
1552:
1521:
1518:
1515:
1510:
1506:
1502:
1499:
1496:
1493:
1490:
1461:
1458:
1452:
1448:
1444:
1441:
1438:
1427:
1426:
1396:
1375:
1357:
1343:
1333:
1314:
1290:
1250:
1247:
1246:
1245:
1227:
1211:
1197:
1157:
1135:
1132:
1131:
1130:
1123:Post's theorem
1120:
1110:
1100:
1090:
1084:
1045:
1026:
1001:
998:
997:
996:
982:
978:
962:
956:
911:
904:
898:
895:
877:
864:
848:
844:
839:
827:
812:
808:
805:
772:
769:
763:
760:
759:
758:
742:
738:
733:
705:
704:′ holds.
690:
674:
670:
665:
653:
639:
635:
617:
614:
598:
587:
536:
492:
395:
374:
349:
331:
320:
319:
312:
301:
290:
283:
277:
266:
260:
254:
227:
212:
162:
135:is said to be
121:Main article:
118:
115:
59:
56:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3620:
3609:
3606:
3604:
3601:
3599:
3596:
3595:
3593:
3576:
3573:
3572:
3571:
3568:
3567:
3565:
3561:
3554:
3550:
3547:
3543:
3540:
3536:
3533:
3529:
3526:
3522:
3521:
3519:
3515:
3509:
3506:
3504:
3501:
3499:
3496:
3494:
3491:
3489:
3486:
3484:
3483:Turing degree
3481:
3479:
3476:
3475:
3472:
3468:
3461:
3456:
3454:
3449:
3447:
3442:
3441:
3438:
3428:
3423:
3421:
3419:
3415:
3411:
3406:
3403:
3399:
3394:
3391:
3387:
3382:
3379:
3372:
3367:
3363:
3359:
3355:
3351:
3347:
3343:
3339:
3334:
3331:
3327:
3323:
3319:
3314:
3310:
3306:
3302:
3298:
3294:
3290:
3286:
3282:
3278:
3274:
3273:
3268:
3264:
3261:
3257:
3253:
3249:
3244:
3239:
3235:
3231:
3227:
3223:
3219:
3216:
3212:
3208:
3204:
3200:
3196:
3192:
3188:
3185:
3181:
3177:
3173:
3168:
3163:
3159:
3155:
3154:
3148:
3145:
3141:
3137:
3133:
3129:
3125:
3121:
3117:
3112:
3107:
3103:
3099:
3095:
3090:
3086:
3081:
3077:
3073:
3072:
3067:
3062:
3058:
3054:
3050:
3046:
3042:
3038:
3034:
3030:
3029:J. Symb. Log.
3025:
3021:
3017:
3012:
3007:
3003:
2999:
2994:
2991:
2987:
2983:
2979:
2975:
2971:
2967:
2963:
2959:
2955:
2954:
2949:
2945:
2931:
2926:
2922:
2918:
2914:
2910:
2906:
2902:
2898:
2894:
2893:
2888:
2883:
2882:
2878:
2872:
2868:
2864:
2860:
2855:
2850:
2846:
2842:
2838:
2834:
2830:
2826:
2824:3-540-15299-7
2820:
2816:
2812:
2808:
2804:
2800:
2796:
2792:
2786:
2782:
2778:
2774:
2770:
2768:9780444863881
2764:
2760:
2756:
2752:
2748:
2744:
2740:
2736:
2732:
2728:
2724:
2718:
2714:
2710:
2706:
2695:
2691:
2687:
2685:9780262680523
2681:
2677:
2673:
2668:
2667:
2661:
2657:
2653:
2649:
2645:
2639:
2635:
2631:
2627:
2623:
2619:
2615:
2609:
2604:
2603:
2597:
2593:
2589:
2587:3-540-12155-2
2583:
2579:
2574:
2570:
2565:
2562:
2548:
2543:
2542:
2538:
2534:
2533:0-521-29465-7
2530:
2524:
2522:0-521-22384-9
2518:
2514:
2510:
2506:
2502:
2500:1-58488-237-9
2496:
2492:
2487:
2486:
2482:
2477:
2473:
2470:
2469:
2465:
2463:
2461:
2457:
2453:
2449:
2445:
2441:
2437:
2433:
2429:
2425:
2421:
2417:
2413:
2410:that halt on
2409:
2404:
2400:
2396:
2392:
2388:
2384:
2379:
2377:
2373:
2369:
2365:
2361:
2357:
2353:
2348:
2344:
2340:
2336:
2330:
2326:
2322:
2318:
2314:
2310:
2304:
2300:
2296:
2292:
2288:
2283:
2279:
2275:
2271:
2267:
2263:
2258:
2254:
2250:
2246:
2243:halts in <
2242:
2238:
2234:
2229:
2225:
2222:
2218:
2214:
2210:
2206:
2199:
2195:
2191:
2186:
2182:
2179:=∅); and let
2175:
2170:
2166:
2162:
2157:
2152:
2148:
2144:
2140:
2136:
2133:
2129:
2124:
2121:
2117:
2113:
2109:
2105:
2101:
2097:
2093:
2089:
2085:
2081:
2077:
2070:
2066:
2062:
2055:
2051:
2044:
2037:
2033:
2029:
2025:
2021:
2017:
2012:
2010:
2006:
2002:
1998:
1994:
1990:
1986:
1982:
1976:
1963:
1959:
1938:
1916:
1909:
1906:
1880:
1876:
1865:
1861:
1852:
1817:
1813:
1799:
1795:
1791:
1787:
1783:
1780:
1776:
1772:
1771:
1770:
1768:
1742:
1734:
1731:
1728:
1724:
1720:
1714:
1706:
1702:
1698:
1695:
1684:
1677:
1673:
1669:
1662:
1659:
1657:
1653:
1649:
1645:
1641:
1637:
1633:
1629:
1624:
1620:
1616:
1612:
1608:
1604:
1597:
1594:
1593:
1592:
1571:
1568:
1558:
1554:
1542:
1538:
1533:
1516:
1508:
1504:
1500:
1494:
1488:
1480:
1476:
1459:
1450:
1446:
1439:
1424:
1420:
1416:
1412:
1408:
1404:
1400:
1397:
1394:
1390:
1387:
1383:
1379:
1376:
1373:
1369:
1365:
1361:
1358:
1355:
1351:
1347:
1344:
1341:
1337:
1334:
1331:
1328:
1327:
1326:
1312:
1304:
1288:
1280:
1276:
1272:
1268:
1264:
1255:
1248:
1215:
1212:
1185:
1181:
1145:
1141:
1138:
1137:
1133:
1128:
1124:
1121:
1118:
1113:
1109:
1103:
1098:
1093:
1089:
1085:
1082:
1078:
1074:
1070:
1066:
1062:
1058:
1054:
1050:
1046:
1043:
1039:
1035:
1031:
1027:
1024:
1020:
1016:
1012:
1008:
1004:
1003:
999:
980:
976:
967:
964:Assuming the
963:
959:
955:
951:
948:
944:
940:
936:
932:
928:
924:
920:
917:
910:
903:
899:
896:
893:
865:
846:
837:
828:
825:
821:
817:
813:
806:
803:
799:
795:
791:
787:
783:
779:
775:
774:
770:
768:
761:
740:
731:
722:
718:
714:
710:
706:
703:
699:
695:
691:
672:
663:
654:
637:
624:
620:
619:
615:
613:
611:
607:
603:
596:
592:
585:
581:
577:
576:
571:
567:
563:
560:the notation
559:
554:
552:
524:
520:
516:
512:
508:
480:
476:
472:
468:
464:
459:
455:
451:
444:
440:
436:
430:
426:
422:
418:
414:
411:For any sets
409:
383:
379:
372:
368:
367:partial order
363:
337:
329:
325:
324:Turing degree
317:
310:
306:
299:
295:
288:
284:
282:
275:
271:
264:
261:
259:
252:
249:
248:
247:
245:
241:
237:
233:
225:
221:
217:
210:
206:
202:
198:
194:
190:
186:
182:
177:
175:
171:
167:
160:
156:
152:
148:
144:
140:
139:
134:
130:
124:
116:
114:
112:
108:
104:
99:
97:
93:
89:
85:
81:
76:
73:Two sets are
71:
69:
65:
57:
55:
53:
49:
45:
42:(named after
41:
40:Turing degree
37:
33:
19:
3517:Publications
3482:
3405:
3393:
3388:, p. 9.
3381:
3341:
3337:
3321:
3317:
3276:
3270:
3233:
3229:
3198:
3194:
3157:
3151:
3101:
3097:
3075:
3069:
3032:
3028:
3001:
2997:
2957:
2951:
2936:. Retrieved
2896:
2890:
2844:
2840:
2814:
2802:
2780:
2746:
2742:
2731:j.ctt1b9x0r8
2712:
2697:. Retrieved
2665:
2633:
2601:
2577:
2568:
2560:
2553:. Retrieved
2512:
2490:
2459:
2455:
2451:
2447:
2443:
2439:
2435:
2431:
2427:
2423:
2419:
2415:
2411:
2407:
2402:
2398:
2394:
2390:
2386:
2382:
2381:To see that
2380:
2375:
2371:
2367:
2363:
2362:to priority
2359:
2355:
2351:
2346:
2342:
2338:
2334:
2328:
2324:
2320:
2316:
2312:
2308:
2302:
2298:
2294:
2290:
2286:
2281:
2277:
2273:
2269:
2265:
2261:
2256:
2252:
2248:
2244:
2240:
2236:
2232:
2227:
2223:
2220:
2216:
2212:
2208:
2204:
2197:
2193:
2189:
2184:
2180:
2173:
2168:
2164:
2160:
2155:
2150:
2146:
2142:
2138:
2134:
2125:
2119:
2115:
2111:
2107:
2103:
2099:
2095:
2091:
2087:
2083:
2079:
2072:
2068:
2064:
2057:
2053:
2046:
2039:
2035:
2031:
2027:
2023:
2020:requirements
2019:
2015:
2013:
2008:
1992:
1988:
1984:
1979:
1961:
1957:
1904:
1903:contains no
1797:
1793:
1789:
1785:
1778:
1774:
1766:
1764:
1761:is ≤n.
1682:
1675:
1671:
1667:
1660:
1655:
1651:
1647:
1643:
1639:
1635:
1631:
1627:
1622:
1618:
1614:
1610:
1606:
1602:
1595:
1540:
1536:
1534:
1478:
1474:
1428:
1418:
1411:T. A. Slaman
1371:
1367:
1363:
1353:
1350:Yates (1966)
1340:Yates (1966)
1330:Sacks (1964)
1302:
1278:
1274:
1266:
1262:
1260:
1116:
1111:
1107:
1101:
1096:
1091:
1087:
1080:
1079:relative to
1076:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1041:
1037:
1033:
1029:
1022:
1018:
1014:
1010:
1006:
957:
953:
949:
946:
942:
938:
934:
930:
926:
922:
918:
915:
908:
901:
823:
819:
815:
797:
793:
789:
785:
781:
780:. A degree
777:
765:
720:
712:
708:
701:
697:
693:
605:
601:
594:
590:
583:
579:
573:
569:
565:
561:
557:
556:For any set
555:
522:
518:
514:
510:
478:
474:
466:
462:
457:
453:
449:
442:
438:
434:
428:
424:
420:
416:
412:
410:
381:
377:
370:
364:
335:
323:
321:
315:
308:
304:
297:
293:
286:
280:
273:
269:
262:
257:
250:
243:
239:
235:
223:
219:
215:
208:
204:
200:
196:
192:
188:
184:
180:
178:
173:
169:
165:
158:
154:
150:
142:
136:
132:
128:
126:
110:
100:
95:
91:
87:
83:
74:
72:
61:
50:of a set of
47:
39:
29:
3608:Alan Turing
3508:Turing test
3467:Alan Turing
3324:: 273–280,
3191:Sacks, G.E.
2753:: 631–652.
2709:Sacks, G.E.
2561:Unpublished
2219:such that ∀
2137:(low means
1605:: for some
1591:such that:
925:such that ∀
802:dense order
575:Turing jump
517:is denoted
423:Y, written
103:Post (1944)
44:Alan Turing
3592:Categories
2478:References
2414:do so <
1609:, for any
1539:is called
1265:(r.e.) or
1075:is called
1055:such that
916:exact pair
776:There are
655:There are
452:+1 :
3575:namesakes
3293:0003-486X
3252:1073-2780
3176:0002-9904
3128:0024-6115
3106:CiteSeerX
3078:: 78–82,
3006:CiteSeerX
2974:0003-486X
2938:20 August
2799:Shore, R.
2694:933975989
2676:MIT Press
2555:20 August
2389:halts on
1997:Friedberg
1981:Emil Post
1942:¯
1877:≤
1862:≤
1853:∣
1814:≤
1721:≠
1699:∣
1572:∈
1505:χ
1457:∅
1447:≤
1325:is r.e..
1115:for each
977:ω
890:is not a
843:ℵ
737:ℵ
723:has size
717:countable
669:ℵ
634:ℵ
549:is not a
179:Two sets
141:to a set
3555:" (1952)
3548:" (1950)
3541:" (1948)
3534:" (1939)
3527:" (1936)
3366:38778059
3144:16488410
3057:30992462
2921:38576214
2913:27588601
2871:29549997
2835:(1978).
2813:(1987).
2779:(1971).
2751:Elsevier
2711:(1966).
2662:(1967).
2632:(1999).
2598:(1989).
2511:(1980).
2466:See also
2337:) = min(
2056:, where
2036:0′
2030:between
1989:0′
1784:For all
1650:"weakly
1617:we have
1460:′
1403:lattices
1386:atomless
1368:0′
1303:0′
1279:0′
1275:0′
1106:≤
1069:a′
1065:b′
1040:≤
1038:0′
1034:b′
1023:a′
1015:a′
521:∪
465:⊕
456:∈
441:∈
437: :
427:⊕
272:implies
58:Overview
3563:Related
3358:2269807
3309:0432435
3301:1971028
3260:1739227
3215:1970393
3184:0010514
3136:1635141
3049:2270459
2990:0061078
2982:1969708
2863:0508451
2652:1718169
2622:0982269
2116:injured
2104:satisfy
2001:Muchnik
1666:is an "
1613:≥
1099:′
892:lattice
786:minimal
597:≡
551:lattice
481:. Thus
469:is the
446:} and
373:≤
311:≡
300:≡
289:≡
276:≡
265:≡
253:≡
211:≡
161:≤
3364:
3356:
3307:
3299:
3291:
3258:
3250:
3213:
3182:
3174:
3142:
3134:
3126:
3108:
3055:
3047:
3008:
2988:
2980:
2972:
2919:
2911:
2869:
2861:
2821:
2787:
2765:
2729:
2719:
2692:
2682:
2650:
2640:
2620:
2610:
2584:
2531:
2519:
2497:
2450:; and
2323:, set
2297:, set
2260:with ∀
2145:, let
2128:simple
1654:-r.e."
1535:A set
326:is an
242:, and
3373:Notes
3362:S2CID
3354:JSTOR
3297:JSTOR
3211:JSTOR
3140:S2CID
3053:S2CID
3045:JSTOR
2978:JSTOR
2933:(PDF)
2917:S2CID
2909:JSTOR
2867:S2CID
2727:JSTOR
2699:6 May
2550:(PDF)
2022:that
1964:-r.e.
1956:are (
1800:with
1648:being
1413:(see
1059:<
700:<
652:sets.
505:is a
307:then
46:) or
3289:ISSN
3248:ISSN
3172:ISSN
3124:ISSN
2970:ISSN
2940:2023
2819:ISBN
2785:ISBN
2763:ISBN
2717:ISBN
2701:2020
2690:OCLC
2680:ISBN
2638:ISBN
2608:ISBN
2582:ISBN
2557:2023
2529:ISBN
2517:ISBN
2495:ISBN
2430:iff
2215:<
2071:and
2045:and
2034:and
1999:and
1987:and
1929:and
1630:) =
1409:and
1348:and
1338:and
1305:iff
1063:and
1021:and
1013:and
941:<
933:<
796:and
513:and
477:and
421:join
419:, X
415:and
296:and
222:and
199:and
183:and
38:the
34:and
3346:doi
3326:doi
3281:doi
3277:105
3238:doi
3203:doi
3162:doi
3116:doi
3080:doi
3037:doi
3016:doi
2962:doi
2901:doi
2849:doi
2755:doi
2319:on
2132:low
1646:A
1178:is
1174:or
1146:of
1077:low
945:⇔ ∃
788:if
784:is
715:is
578:of
285:If
246::
191:if
129:set
30:In
3594::
3417:^
3360:,
3352:,
3342:31
3340:,
3322:17
3320:,
3305:MR
3303:.
3295:.
3287:.
3256:MR
3254:,
3246:,
3232:,
3224:;
3209:,
3199:80
3180:MR
3178:,
3170:,
3158:50
3156:,
3138:,
3132:MR
3130:,
3122:,
3114:,
3102:77
3100:,
3076:37
3074:,
3051:,
3043:,
3033:31
3031:,
3014:,
3000:,
2986:MR
2984:,
2976:,
2968:,
2958:59
2915:.
2907:.
2897:72
2895:.
2889:.
2865:.
2859:MR
2857:.
2845:84
2843:.
2839:.
2761:.
2749:.
2747:90
2725:.
2688:.
2678:.
2674::
2670:.
2648:MR
2646:.
2618:MR
2616:.
2559:.
2527:;
2341:,
2331:+1
2305:+1
2289:)≥
2235:)≠
2196:;
2172:;
2158:=∪
1796:,
1674:,
1532:.
1481:,
1104:+1
1067:=
921:,
907:,
612:.
448:{2
433:{2
362:.
322:A
238:,
176:.
113:.
3551:"
3544:"
3537:"
3530:"
3523:"
3459:e
3452:t
3445:v
3429:.
3348::
3328::
3311:.
3283::
3240::
3234:6
3205::
3164::
3118::
3082::
3059:.
3039::
3022:.
3018::
3002:3
2964::
2942:.
2923:.
2903::
2873:.
2851::
2827:.
2793:.
2771:.
2757::
2733:.
2703:.
2654:.
2624:.
2590:.
2525:.
2503:.
2460:i
2456:i
2452:X
2448:i
2444:i
2440:X
2436:X
2434:\
2432:Y
2428:Y
2424:X
2420:i
2418:-
2416:n
2412:X
2408:i
2403:n
2399:T
2395:n
2391:X
2387:i
2383:X
2376:i
2372:i
2368:i
2364:i
2360:S
2356:i
2352:m
2350:(
2347:n
2343:P
2339:i
2335:m
2333:(
2329:n
2325:P
2321:S
2317:i
2313:m
2309:S
2307:=
2303:n
2299:T
2295:S
2291:i
2287:m
2285:(
2282:n
2278:P
2274:n
2270:T
2268:\
2266:S
2264:∈
2262:m
2257:n
2253:T
2251:⊇
2249:S
2245:n
2241:i
2237:i
2233:m
2231:(
2228:n
2224:P
2221:m
2217:n
2213:i
2209:n
2205:m
2203:(
2201:0
2198:P
2194:m
2190:m
2188:(
2185:n
2181:P
2177:0
2174:T
2169:n
2165:T
2161:n
2156:X
2151:n
2147:T
2143:n
2139:X
2135:X
2120:X
2112:X
2108:X
2100:X
2096:X
2092:X
2084:X
2080:e
2075:e
2073:B
2069:X
2065:e
2060:e
2058:A
2054:e
2049:e
2047:B
2042:e
2040:A
2032:0
2028:X
2024:X
2016:X
1985:0
1977:.
1962:n
1958:n
1939:A
1917:A
1905:n
1891:}
1887:b
1881:T
1872:c
1866:T
1857:a
1849:c
1845:{
1824:b
1818:T
1809:a
1798:b
1794:a
1790:n
1786:n
1779:n
1775:n
1767:n
1749:}
1746:)
1743:x
1740:(
1735:1
1732:+
1729:s
1725:A
1718:)
1715:x
1712:(
1707:s
1703:A
1696:s
1693:{
1683:x
1681:(
1679:0
1676:A
1672:x
1668:n
1664:s
1661:A
1656:)
1652:n
1640:A
1636:x
1634:(
1632:A
1628:x
1626:(
1623:s
1619:A
1615:t
1611:s
1607:t
1603:A
1599:s
1596:A
1576:N
1569:s
1565:)
1559:s
1555:A
1551:(
1541:n
1537:A
1520:)
1517:s
1514:(
1509:A
1501:=
1498:)
1495:s
1492:(
1489:g
1479:s
1475:g
1451:T
1443:]
1440:A
1437:[
1425:.
1419:0
1395:.
1374:.
1364:0
1356:.
1354:0
1313:A
1289:A
1244:.
1226:D
1196:D
1156:D
1119:.
1117:i
1112:i
1108:a
1102:i
1097:a
1092:i
1088:a
1083:.
1081:a
1073:b
1061:b
1057:a
1053:b
1049:a
1044:.
1042:a
1030:a
1025:.
1019:a
1011:a
1007:a
995:.
981:1
958:i
954:a
952:≤
950:e
947:i
943:d
939:e
937:∧
935:c
931:e
929:(
927:e
923:d
919:c
912:2
909:a
905:1
902:a
894:.
876:D
847:0
838:2
826:.
824:a
820:b
816:a
811:.
809:T
804:.
798:a
794:0
790:a
782:a
757:.
741:0
732:2
721:a
713:a
709:a
702:a
698:a
694:a
673:0
664:2
638:0
606:0
602:Y
599:T
595:X
591:Y
588:T
584:X
580:X
570:X
566:X
562:X
558:X
535:D
523:b
519:a
515:b
511:a
491:D
479:Y
475:X
467:Y
463:X
458:Y
454:m
450:m
443:X
439:n
435:n
429:Y
425:X
417:Y
413:X
394:D
382:0
378:Y
375:T
371:X
348:D
336:X
332:T
318:.
316:Z
313:T
309:X
305:Z
302:T
298:Y
294:Y
291:T
287:X
281:X
278:T
274:Y
270:Y
267:T
263:X
258:X
255:T
251:X
244:Z
240:Y
236:X
228:T
224:Y
220:X
216:Y
213:T
209:X
205:X
201:Y
197:Y
193:X
185:Y
181:X
174:Y
170:X
166:Y
163:T
159:X
155:Y
151:X
143:Y
133:X
96:X
92:Y
88:Y
84:X
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.