1208:
structure by the basic result that a set is computable if and only if the set and its complement are both computably enumerable. Infinite c.e. sets have always infinite computable subsets; but on the other hand, simple sets exist but do not always have a coinfinite computable superset. Post introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are c.e. sets such that every c.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the computable sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; in 1991, Harrington and Soare found eventually such a property.
1237:(as defined in the previous paragraph) have the property that they cannot be automorphic to non-maximal sets, that is, if there is an automorphism of the computably enumerable sets under the structure just mentioned, then every maximal set is mapped to another maximal set. In 1974, Soare showed that also the converse holds, that is, every two maximal sets are automorphic. So the maximal sets form an orbit, that is, every automorphism preserves maximality and any two maximal sets are transformed into each other by some automorphism. Harrington gave a further example of an automorphic property: that of the creative sets, the sets which are many-one equivalent to the halting problem.
1195:, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.
739:. After ten years, Kleene and Post showed in 1954 that there are intermediate Turing degrees between those of the computable sets and the halting problem, but they failed to show that any of these degrees contains a computably enumerable set. Very soon after this, Friedberg and Muchnik independently solved Post's problem by establishing the existence of computably enumerable sets of intermediate degree. This groundbreaking result opened a wide study of the Turing degrees of the computably enumerable sets which turned out to possess a very complicated and non-trivial structure.
6576:
1291:. This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of a subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs. There are still many open problems in this area.
4798:
1752:, a prominent researcher in the field, has proposed that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than the terminology using the word "recursive" introduced by Kleene. Many contemporary researchers have begun to use this alternate terminology. These researchers also use terminology such as
1169:(named after its discoverer) is a one-one numbering of all partial-computable functions; it is necessarily not an admissible numbering. Later research dealt also with numberings of other classes like classes of computably enumerable sets. Goncharov discovered for example a class of computably enumerable sets for which the numberings fall into exactly two classes with respect to computable isomorphisms.
4808:
4818:
979:, this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
1840:
1445:)-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that a set
1537:. Basic results are that all computably enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of computably enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards.
1804:
computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers, the sets of interest in computability theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.
502:
Beginning with the theory of computable sets and functions described above, the field of computability theory has grown to include the study of many closely related topics. These are not independent areas of research: each of these areas draws ideas and results from the others, and most computability
1240:
Besides the lattice of computably enumerable sets, automorphisms are also studied for the structure of the Turing degrees of all sets as well as for the structure of the Turing degrees of c.e. sets. In both cases, Cooper claims to have constructed nontrivial automorphisms which map some degrees to
990:
The major research on strong reducibilities has been to compare their theories, both for the class of all computably enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that
732:
and hyperhypersimple sets. Post showed that these sets are strictly between the computable sets and the halting problem with respect to many-one reducibility. Post also showed that some of them are strictly intermediate under other reducibility notions stronger than Turing reducibility. But Post
2161:
has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an
277:
has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an
1565:
by permitting quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are linked to the theories of well-orderings and trees; for example the set of all indices of computable (nonbinary) trees without infinite branches is complete for level
1198:
Priority arguments have been employed to solve many problems in computability theory, and have been classified into a hierarchy based on their complexity. Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results
1207:
When Post defined the notion of a simple set as a c.e. set with an infinite complement not containing any infinite c.e. set, he started to study the structure of the computably enumerable sets under inclusion. This lattice became a well-studied structure. Computable sets can be defined in this
1803:
in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the
Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a
1263:
was developed during the 1960s and 1970s by
Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of the research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider a
713:. It can be shown that every computably enumerable set is many-one reducible to the halting problem, and thus the halting problem is the most complicated computably enumerable set with respect to many-one reducibility and with respect to Turing reducibility. In 1944, Post asked whether
742:
There are uncountably many sets that are not computably enumerable, and the investigation of the Turing degrees of all sets is as central in computability theory as the investigation of the computably enumerable Turing degrees. Many degrees with special properties were constructed:
1241:
other degrees; this construction has, however, not been verified and some colleagues believe that the construction contains errors and that the question of whether there is a nontrivial automorphism of the Turing degrees is still one of the main unsolved questions in this area.
102:
Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of
823:
Much recent research on Turing degrees has focused on the overall structure of the set of Turing degrees and the set of Turing degrees containing computably enumerable sets. A deep theorem of Shore and Slaman states that the function mapping a degree
1557:, as described by Sacks in 1990. These generalized notions include reducibilities that cannot be executed by Turing machines but are nevertheless natural generalizations of Turing reducibility. These studies include approaches to investigate the
537:
in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot.
1701:, a formal theory of natural numbers and sets of natural numbers. The fact that certain sets are computable or relatively computable often implies that these sets can be defined in weak subsystems of second-order arithmetic. The program of
1199:
without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published a paper on a proof for the existence of
Friedberg numberings without using the priority method.
256:
as the correct formalization of the informal idea of effective calculation. In 1952, these results led Kleene to coin the two names "Church's thesis" and "Turing's thesis". Nowadays these are often considered as a single hypothesis, the
1216:
Another important question is the existence of automorphisms in computability-theoretic structures. One of these structures is that one of computably enumerable sets under inclusion modulo finite difference; in this structure,
1191:. This method is primarily used to construct computably enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as
1716:, as well as formal theories of the natural numbers weaker than Peano arithmetic. One method of classifying the strength of these weak systems is by characterizing which computable functions the system can prove to be
812:. The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the Halting problem can be obtained as the Turing jump of another set.
1437: + 1. There are uncountably many of these sets and also some computably enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of computably enumerable sets that are (1,
465:, which is the set of (descriptions of) Turing machines that halt on input 0, is a well-known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only
480:
Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a
494:). Equivalently, a set is c.e. if and only if it is the range of some computable function. The c.e. sets, although not decidable in general, have been studied in detail in computability theory.
1705:
uses these subsystems to measure the non-computability inherent in well known mathematical theorems. In 1999, Simpson discussed many aspects of second-order arithmetic and reverse mathematics.
828:
to the degree of its Turing jump is definable in the partial order of the Turing degrees. A survey by Ambos-Spies and Fejer gives an overview of this research and its historical progression.
1097:
contains the computably enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
846:, so named because they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of which oracle it is presented with.
529:, introduced by Turing in 1939. An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an
458:
it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. In 1996, Soare gave additional comments about the terminology.
1736:, which are not primitive recursive, are total. Not every total computable function is provably total in Peano arithmetic, however; an example of such a function is provided by
693:, but the converse does not always hold. Although the natural examples of noncomputable sets are all many-one equivalent, it is possible to construct computably enumerable sets
294:
is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false.
4955:
2823:
1596:
3629:
430:
The terminology for computable functions and sets is not completely standardized. The definition in terms of μ-recursive functions as well as a different definition of
5630:
2224:(with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in
2201:
To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function
2563:
2383:
2344:
3134:
994:
Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known are
286:. In 1936, Church and Turing were inspired by techniques used by Gödel to prove his incompleteness theorems - in 1931, Gödel independently demonstrated that the
2619:
1481:'s model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class
5713:
4854:
1129:
and others; in 1999, Simpson gave a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that the
3834:
450:
which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to
1060:
for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the
1795:
In 1967, Rogers has suggested that a key property of computability theory is that its results and structures should be invariant under computable
6027:
2400:
4551:
4523:
3520:
3052:
6185:
4576:
3400:
3110:
3031:
2744:
2194:
2147:
4973:
1748:
The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days.
1393:)-recursive sets. The first major result in this branch of computability theory is Trakhtenbrot's result that a set is computable if it is (
6040:
5363:
4427:
842:
An ongoing area of research in computability theory studies reducibility relations other than Turing reducibility. Post introduced several
3615:
2721:
2067:
1683:
4581:
3853:
5625:
6045:
6035:
5772:
4978:
4086:
3200:
3167:
1691:
733:
left open the main problem of the existence of computably enumerable sets of intermediate Turing degree; this problem became known as
5523:
4969:
1784:. Not all researchers have been convinced, however, as explained by Fortnow and Simpson. Some commentators argue that both the names
1679:
983:
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article
6181:
4733:
4561:
4091:
3501:
3456:
3430:
3377:
3346:
3304:
3278:
3237:
2988:
2794:
2484:
2449:
2110:
1996:
721:
to the halting problem, that is, whether there is no computably enumerable set with a Turing degree intermediate between those two.
1651:
6278:
6022:
4847:
4821:
3915:
3326:
1599:
794:
The study of arbitrary (not necessarily computably enumerable) Turing degrees involves the study of the Turing jump. Given a set
77:
5583:
5276:
5017:
4209:
3288:
2931:
2243:
357:
The main form of computability studied in the field was introduced by Turing in 1936. A set of natural numbers is said to be a
104:
4462:
1133:
of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics is
6539:
6241:
6004:
5999:
5824:
5245:
4929:
4500:
4119:
3827:
1814:
1721:
1550:
999:
975:
via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of
3544:(1958). "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition".
6600:
6534:
6317:
6234:
5947:
5878:
5755:
4997:
4642:
4619:
4349:
4339:
3703:
3546:
3155:
2778:
2021:
1126:
314:
5605:
6459:
6285:
5971:
5204:
4723:
4311:
4219:
4124:
3900:
3885:
2129:
1915:
1903:
1853:
1725:
1662:
There are close relationships between the Turing degree of a set of natural numbers and the difficulty (in terms of the
984:
837:
5610:
1598:
of the analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field of
282:
With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be
6605:
5942:
5681:
4939:
4840:
4811:
4546:
4044:
3130:
1485:
of computable functions, is there a learner (that is, computable functional) which outputs for any input of the form (
808:
is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle
306:
6337:
6332:
6266:
5856:
5250:
5218:
4909:
4783:
4432:
2515:
2441:
1863:
1687:
780:
342:
4983:
2375:
6556:
6505:
6402:
5900:
5861:
5338:
4801:
4728:
4703:
4566:
4214:
3820:
3737:
2288:
1635:
995:
820:, which is a classification of certain subsets of the natural numbers based on their definability in arithmetic.
482:
338:
6397:
5012:
1618:
Computability theory for digital computation is well developed. Computability theory is less well developed for
1603:
1421:
sets (which were already known informally before
Jockusch introduced them 1968) are examples of a set which is (
614:
The natural examples of sets that are not computable, including many different sets that encode variants of the
258:
6327:
5866:
5718:
5701:
5424:
4904:
4652:
4485:
4071:
3940:
3793:
2139:
1627:
1265:
747:
where every function computable relative to that degree is majorized by a (unrelativized) computable function;
6229:
6206:
6167:
6053:
5994:
5640:
5560:
5404:
5348:
4961:
4713:
4647:
4538:
4354:
4014:
3620:
3595:
3392:
2186:
1968:
1820:
1698:
1546:
1118:
424:
318:
1947:" and "c.e." show that many papers have been published with this terminology as well as with the other one.
1117:
asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems of
991:
every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees.
850:
are those where a reduction process may not terminate for all oracles; Turing reducibility is one example.
486:, which is a set that can be enumerated by a Turing machine (other terms for computably enumerable include
6519:
6246:
6224:
6191:
6084:
5930:
5915:
5888:
5839:
5723:
5658:
5483:
5449:
5444:
5318:
5149:
5126:
4778:
4609:
4490:
4257:
4247:
4242:
3473:
3322:
3061:
3009:
2810:
1737:
1663:
1562:
1554:
1260:
1061:
817:
623:
533:, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is
345:
has no effective solution; this problem asked whether there is an effective procedure to decide whether a
88:
6449:
6302:
6094:
5812:
5548:
5454:
5313:
5298:
5179:
5154:
4748:
4718:
4708:
4604:
4518:
4394:
4334:
4301:
4291:
4174:
4139:
4129:
4066:
3935:
3910:
3905:
3870:
3669:
3440:
3410:
2918:
2883:
2665:
2063:
1944:
1643:
1256:
1250:
956:
526:
321:
is not effectively solvable: there is no effective procedure that, given a word in a finitely presented
98:
How can noncomputable functions be classified into a hierarchy based on their level of noncomputability?
53:
6575:
2135:
The
Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions
2731:. Handbook of the History of Logic. Vol. 9. Amsterdam: Elsevier/North-Holland. pp. 443–494.
6422:
6261:
6065:
5905:
5829:
5807:
5635:
5593:
5492:
5459:
5323:
5111:
5022:
4508:
4480:
4452:
4447:
4276:
4252:
4187:
4182:
4164:
4154:
4149:
4111:
4061:
4056:
3973:
3919:
3541:
3126:
2832:
2661:
2558:
2371:
2339:
1792:
fail to convey the fact that most of the objects studied in computability theory are not computable.
1558:
1162:
420:
346:
289:
3587:
1161:. Numberings can be partial-computable although some of its members are total computable functions.
1002:. These reducibilities are closely connected to definability over the standard model of arithmetic.
6551:
6442:
6427:
6407:
6364:
6251:
6201:
6127:
6072:
6009:
5802:
5797:
5745:
5513:
5502:
5174:
5074:
5002:
4993:
4989:
4924:
4919:
4773:
4698:
4614:
4599:
4364:
4144:
4101:
4096:
3993:
3983:
3955:
3660:
3014:
2922:
2878:
2814:
2503:
2468:
2094:
2048:
1858:
1702:
1686:. Gödel's proofs show that the set of logical consequences of an effective first-order theory is a
1166:
1113:
1106:
470:
398:
322:
266:
253:
57:
3803:
Webpage on
Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes
3066:
1818:, which holds several research conferences each year. The interdisciplinary research Association
1569:
454:, it is a partial recursive function (which can be undefined for some inputs), while according to
6580:
6349:
6312:
6297:
6290:
6273:
6059:
5925:
5851:
5834:
5787:
5600:
5509:
5343:
5328:
5288:
5240:
5225:
5213:
5169:
5144:
4914:
4863:
4738:
4637:
4513:
4470:
4379:
4321:
4306:
4296:
4081:
3880:
3762:
3754:
3720:
3698:
3686:
3648:
3571:
3563:
3221:
2968:
2900:
2540:
2532:
2361:
2313:
2305:
2260:
1733:
1631:
1619:
1049:
906:
877:
857:
788:
630:
115:. The study of which mathematical constructions can be effectively performed is sometimes called
45:
6077:
5533:
3518:
Burgin, Mark; Klinger, Allen (2004). "Experience, Generations, and Limits in
Machine Learning".
3493:
3477:
2758:
2507:
2052:
6515:
6322:
6132:
6122:
6014:
5895:
5730:
5706:
5487:
5471:
5376:
5353:
5230:
5199:
5164:
5059:
4894:
4758:
4688:
4667:
4629:
4437:
4404:
4384:
4076:
3988:
3862:
3497:
3452:
3426:
3396:
3373:
3352:
3342:
3300:
3274:
3270:
3233:
3192:
3159:
3106:
3090:
3027:
2984:
2860:
2790:
2740:
2691:
2480:
2445:
2190:
2143:
2106:
1992:
1980:
1845:
1671:
1667:
1057:
1010:
813:
735:
330:
302:
234:
2881:(1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets".
6529:
6524:
6417:
6374:
6196:
6157:
6152:
6137:
5963:
5920:
5817:
5615:
5565:
5139:
5101:
4591:
4475:
4442:
4237:
4159:
4048:
4034:
4029:
3978:
3965:
3890:
3843:
3802:
3746:
3712:
3678:
3638:
3604:
3555:
3529:
3071:
3019:
2940:
2892:
2850:
2840:
2732:
2681:
2628:
2580:
2572:
2524:
2429:
2392:
2353:
2297:
2252:
2178:
2030:
1800:
1729:
1713:
1647:
547:
512:
451:
326:
49:
2954:
2754:
2703:
2642:
724:
As intermediate results, Post defined natural types of computably enumerable sets like the
6510:
6500:
6454:
6437:
6392:
6354:
6256:
6176:
5983:
5910:
5883:
5871:
5777:
5691:
5665:
5620:
5588:
5389:
5191:
5134:
5084:
5049:
5007:
4662:
4556:
4528:
4422:
4374:
4359:
4344:
4199:
4194:
4134:
4024:
3998:
3950:
3895:
3797:
3369:
3262:
3188:
2980:
2950:
2786:
2750:
2699:
2638:
2476:
1749:
1623:
1122:
1041:
729:
615:
474:
462:
455:
301:
have been shown to be undecidable after these initial examples were established. In 1947,
112:
1517:
with respect to a previously agreed on acceptable numbering of all computable functions;
2836:
1469:; these choices must contain the true cardinality but leave out at least one false one.
6495:
6474:
6432:
6412:
6307:
6162:
5760:
5750:
5740:
5735:
5669:
5543:
5419:
5308:
5303:
5281:
4882:
4768:
4672:
4571:
4417:
4389:
3732:
3664:
3415:
3094:
2973:
2736:
2610:
2434:
2034:
1717:
1639:
376:
359:
334:
242:
92:
17:
3643:
3624:
3609:
2376:"On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction"
1137:, which states that the powerset of the naturals is closed under Turing reducibility.
611:). The Turing degree of a set gives a precise measure of how uncomputable the set is.
6594:
6469:
6147:
5654:
5439:
5429:
5399:
5384:
5054:
4657:
3945:
3724:
3489:
3422:
3334:
3075:
2855:
2818:
2585:
2283:
2238:
2221:
2174:
2158:
2154:
2102:
2012:
1988:
1675:
1545:
Computability theory includes the study of generalized notions of this field such as
1418:
1178:
718:
603:
516:
466:
310:
283:
278:
interesting epistemological notion, i.e., one not depending on the formalism chosen."
274:
230:
226:
108:
69:
65:
61:
31:
3766:
3575:
2633:
2614:
2317:
2162:
interesting epistemological notion, i.e., one not depending on the formalism chosen.
1690:, and that if the theory is strong enough this set will be uncomputable. Similarly,
469:
Turing machines, and thus only countably many computable sets, but according to the
6369:
6216:
6117:
6109:
5989:
5937:
5846:
5782:
5765:
5696:
5555:
5414:
5116:
4899:
4753:
4412:
3807:
3583:
2544:
2342:(1937) . "On computable numbers, with an application to the Entscheidungsproblem".
1709:
1478:
976:
73:
1064:. For example, the index set FIN of the class of all finite sets is on the level Σ
3023:
2365:
2133:
6479:
6359:
5538:
5528:
5475:
5159:
5079:
5064:
4944:
4889:
4743:
4369:
4281:
3481:
1976:
1694:
can be interpreted both in terms of definability and in terms of computability.
1234:
800:
298:
238:
210:
2686:
2669:
2576:
2396:
2357:
1299:
This branch of computability theory analyzed the following question: For fixed
5409:
5264:
5235:
5041:
4763:
4693:
4286:
4019:
3875:
3716:
3533:
3047:
2615:"Recursively enumerable sets of positive integers and their decision problems"
1940:
1835:
1607:
1477:
This is the computability-theoretic branch of learning theory. It is based on
725:
269:. Although initially skeptical, by 1946 Gödel argued in favor of this thesis:
2945:
2926:
2845:
2695:
6561:
6464:
5517:
5434:
5394:
5358:
5294:
5106:
5096:
5069:
4268:
4229:
3338:
3296:
3229:
1796:
262:
246:
2864:
2053:"Computability Theory and Applications: The Art of Classical Computability"
2016:
1927:
A list of open problems is maintained by Joseph Miller and André Nies, the
816:
establishes a close relationship between the Turing jump operation and the
1972:
555:
if there is an oracle machine that correctly tells whether numbers are in
419:). The use of Turing machines here is not necessary; there are many other
6546:
6344:
5792:
5497:
5091:
4329:
3448:
3102:
3050:(1996). "Recursion theory on the reals and continuous-time computation".
3004:
Orponen, Pekka (1997). "A Survey of
Continuous-Time Computation Theory".
1130:
3667:(1954). "The upper semi-lattice of degrees of recursive unsolvability".
1068:, the index set REC of the class of all recursive sets is on the level Σ
787:
degrees of 1-generic sets; and the degrees below the halting problem of
521:
Computability theory in mathematical logic has traditionally focused on
6142:
4934:
3758:
3690:
3652:
3567:
2904:
2309:
2264:
1928:
909:: This is essentially one-one reducibility without the constraint that
423:
that have the same computing power as Turing machines; for example the
2536:
4832:
3790:
3750:
3682:
3559:
2896:
2301:
2256:
1087:
contains just all sets which are computably enumerable relative to Σ
677:
Many-one reductions are "stronger" than Turing reductions: if a set
3812:
2528:
1812:
The main professional organization for computability theory is the
1145:
A numbering is an enumeration of functions; it has two parameters,
64:. The field has since expanded to include the study of generalized
5686:
5032:
4877:
1799:
on the natural numbers (this suggestion draws on the ideas of the
1076:
and the index set COMP of the class of all Turing-complete sets Σ
1072:, the index set COFIN of all cofinite sets is also on the level Σ
325:, will decide whether the element represented by the word is the
3356:
440:
for sets and functions computable by a Turing machine. The word
4836:
3816:
225:
Computability theory originated in the 1930s, with the work of
2241:(1936a). "An unsolvable problem of elementary number theory".
3226:
The Theory of
Recursive Functions and Effective Computability
252:
The fundamental results the researchers obtained established
3785:
2819:"Post's Program and incomplete recursively enumerable sets"
2436:
Computability, An introduction to recursive function theory
1724:
any computable function that is provably total is actually
1658:
Relationships between definability, proof and computability
1179:
Turing degree § Post's problem and the priority method
83:
Basic questions addressed by computability theory include:
1017:(which contains some but not all c.e. sets) the index set
261:, which states that any function that is computable by an
219:
Hence, it is not computable; only a few values are known.
2715:
2713:
525:, a generalization of Turing computability defined using
3735:(1947). "Recursive unsolvability of a problem of Thue".
1461:
many possible choices of the cardinality of this set of
305:
and Post published independent papers showing that the
3701:(1956). "The lattice of recursively enumerable sets".
3331:
Systems that learn: an introduction to learning theory
1453:
such that some algorithm enumerates for each tuple of
1271:
and to measure the complexity of a number (or string)
1005:
427:
obtained from primitive recursion and the μ operator.
309:
cannot be effectively decided. Extending this result,
1572:
1165:
are those into which all others can be translated. A
72:. In these areas, computability theory overlaps with
3808:
German language lecture notes on inductive inference
461:
Not every set of natural numbers is computable. The
6488:
6383:
6215:
6108:
5960:
5653:
5576:
5470:
5374:
5263:
5190:
5125:
5040:
5031:
4953:
4870:
4681:
4628:
4590:
4537:
4499:
4461:
4403:
4320:
4266:
4228:
4173:
4110:
4043:
4007:
3964:
3928:
3861:
2824:
Proceedings of the
National Academy of Sciences USA
1895:Many of these foundational papers are collected in
1183:Post's problem was solved with a method called the
1080:. These hierarchy levels are defined inductively, Σ
3414:
2972:
2433:
1712:includes the study of second-order arithmetic and
1590:
717:computably enumerable set is either computable or
503:theorists are familiar with the majority of them.
349:over the integers has a solution in the integers.
3630:Transactions of the American Mathematical Society
3006:Advances in Algorithms, Languages, and Complexity
2220:(NB. This volume also includes the 1946 paper by
1828:) also organizes a series of annual conferences.
1650:. For example, models of computation such as the
1654:model have formalized computation on the reals.
27:Study of computable functions and Turing degrees
2773:
2771:
2286:(1936b). "A note on the Entscheidungsproblem".
1886:covers many of the known results in this field.
436:functions by Gödel led to the traditional name
271:
56:that originated in the 1930s with the study of
3625:"Semirecursive sets and positive reducibility"
2564:Proceedings of the London Mathematical Society
2561:(1939). "Systems of logic based on ordinals".
2384:Proceedings of the London Mathematical Society
2345:Proceedings of the London Mathematical Society
2334:
2332:
4848:
3852:Note: This template roughly follows the 2012
3828:
3091:"Hierarchies of Provably Recursive Functions"
3089:Fairtlough, Matt; Wainer, Stanley S. (1998).
2620:Bulletin of the American Mathematical Society
2498:
2496:
2463:
2461:
2089:
2087:
1006:Rice's theorem and the arithmetical hierarchy
751:relative to which one can compute a function
507:Relative computability and the Turing degrees
395:from natural numbers to natural numbers is a
8:
2720:Ambos-Spies, Klaus; Fejer, Peter A. (2014).
2605:
2603:
2601:
2124:
2122:
1674:. A weaker relationship was demonstrated by
1509:if almost all hypotheses are the same index
1319:is it possible to compute for any different
629:Each can be translated into any other via a
445:
431:
407:if there is a Turing machine that, on input
287:
217:) grows faster than any computable function.
3131:"Is it Recursive, Computable or Decidable?"
2183:Kurt Gödel Publications 1938–1974 Volume II
1670:. One such relationship is made precise by
1441: + 1)-recursive but not (1,
1157:-th function in the numbering on the input
1044:or its complement is many-one reducible to
317:showed independently in the 1950s that the
5674:
5269:
5037:
4855:
4841:
4833:
3835:
3821:
3813:
755:which dominates every computable function
128:
3642:
3608:
3065:
3013:
2944:
2854:
2844:
2685:
2632:
2584:
1582:
1577:
1571:
1449:is computable if and only if there is an
1203:The lattice of computably enumerable sets
563:as the oracle set (in this case, the set
387:is in the set and halts with output 0 if
1187:; a proof using this method is called a
929:if there is a total computable function
601:then the sets are said to have the same
3786:Association for Symbolic Logic homepage
2473:Recursively Enumerable Sets and Degrees
1960:
1875:
1697:Computability theory is also linked to
1541:Generalizations of Turing computability
1013:showed that for every nontrivial class
641:, there is a total computable function
4552:Knowledge representation and reasoning
3588:"Language Identification in the Limit"
3368:. Perspectives in Mathematical Logic.
2475:. Perspectives in Mathematical Logic.
759:in the sense that there is a constant
30:For the concept of computability, see
4577:Philosophy of artificial intelligence
3772:
2783:Subsystems of Second Order Arithmetic
2648:
2592:
2416:
2323:
2270:
2225:
1896:
541:Informally, a set of natural numbers
7:
3896:Energy consumption (Green computing)
2927:"Definability in the Turing degrees"
1275:as the length of the shortest input
4582:Distributed artificial intelligence
3854:ACM Computing Classification System
1040:} has the property that either the
853:The strong reducibilities include:
4087:Integrated development environment
2737:10.1016/B978-0-444-51624-4.50010-1
2035:10.1002/j.1538-7305.1962.tb00480.x
1602:. The even more general notion of
1574:
1385:are true. Such sets are known as (
1225:if and only if the set difference
25:
4562:Automated planning and scheduling
4092:Software configuration management
3644:10.1090/S0002-9947-1968-0220595-7
1985:Handbook of Recursive Mathematics
1884:Handbook of Recursive Mathematics
1048:, that is, can be mapped using a
618:, have two properties in common:
6574:
4816:
4806:
4797:
4796:
3791:Computability in Europe homepage
3289:Matiyasevich, Yuri Vladimirovich
1973:Goncharov, Sergei Savostyanovich
1838:
1600:effective descriptive set theory
1417:. On the other hand, Jockusch's
985:Reduction (computability theory)
483:computably enumerable (c.e.) set
78:effective descriptive set theory
4807:
4210:Computational complexity theory
3512:Research papers and collections
3203:from the original on 2022-03-01
3170:from the original on 2021-12-18
3160:"What is computability theory?"
3137:from the original on 2022-08-07
2932:Illinois Journal of Mathematics
2634:10.1090/S0002-9904-1944-08111-1
2406:from the original on 2022-07-18
2244:American Journal of Mathematics
2213:a computable term representing
2185:. Vol. II. New York, USA:
2099:Introduction to Metamathematics
2073:from the original on 2022-06-30
1732:proves that functions like the
1692:Tarski's indefinability theorem
1666:) of defining that set using a
1614:Continuous computability theory
876:if there is a total computable
681:is many-one reducible to a set
3994:Network performance evaluation
3486:Handbook of Mathematical Logic
3478:"Elements of Recursion Theory"
2727:. In Siekmann, Jörg H. (ed.).
1943:searches for the titles like "
1815:Association for Symbolic Logic
1722:primitive recursive arithmetic
1551:hyperarithmetical reducibility
1121:. This study was initiated by
1000:hyperarithmetical reducibility
709:but not many-one reducible to
391:is not in the set. A function
1:
6535:History of mathematical logic
4365:Multimedia information system
4350:Geographic information system
4340:Enterprise information system
3929:Computer systems organization
3704:The Journal of Symbolic Logic
3610:10.1016/s0019-9958(67)91165-5
3547:The Journal of Symbolic Logic
3467:Survey papers and collections
2674:Mathematical Research Letters
2508:"Computability and recursion"
2022:Bell System Technical Journal
2017:"On non-computable functions"
1153:and outputs the value of the
1125:and was studied in detail by
665:}. These sets are said to be
589:is Turing reducible to a set
6460:Primitive recursive function
4724:Computational social science
4312:Theoretical computer science
4125:Software development process
3901:Electronic design automation
3886:Very Large Scale Integration
3521:Theoretical Computer Science
3389:Computability and Randomness
3076:10.1016/0304-3975(95)00248-0
3053:Theoretical Computer Science
3024:10.1007/978-1-4613-3394-4_11
1916:list of undecidable problems
1854:Recursion (computer science)
1591:{\displaystyle \Pi _{1}^{1}}
1429:)-recursive if and only if 2
963:is truth-table reducible to
838:Reduction (recursion theory)
198:
192:
180:
175:
172:
169:
166:
4547:Natural language processing
4335:Information storage systems
3193:"Renaming recursion theory"
1754:partial computable function
1604:degrees of constructibility
1501:)) a hypothesis. A learner
781:algorithmically random sets
633:. That is, given such sets
444:stems from the German word
411:, halts and returns output
307:word problem for semigroups
151:
148:
6622:
5524:Schröder–Bernstein theorem
5251:Monadic predicate calculus
4910:Foundations of mathematics
4463:Human–computer interaction
4433:Intrusion detection system
4345:Social information systems
4330:Database management system
3445:Classical Recursion Theory
3417:Classical Recursion Theory
2722:"Degrees of unsolvability"
2687:10.4310/mrl.1999.v6.n6.a10
2670:"Defining the Turing Jump"
2516:Bulletin of Symbolic Logic
2442:Cambridge University Press
1918:gives additional examples.
1864:Transcomputational problem
1808:Professional organizations
1770:partial recursive function
1636:artificial neural networks
1248:
1176:
1104:
835:
510:
154:
145:
142:
139:
136:
29:
6570:
6557:Philosophy of mathematics
6506:Automated theorem proving
5677:
5631:Von Neumann–Bernays–Gödel
5272:
4792:
4729:Computational engineering
4704:Computational mathematics
3850:
3738:Journal of Symbolic Logic
3717:10.1017/S002248120008525X
3534:10.1016/j.tcs.2003.12.005
3256:Undergraduate level texts
2586:21.11116/0000-0001-91CE-3
2289:Journal of Symbolic Logic
2060:Department of Mathematics
1688:computably enumerable set
1465:numbers intersected with
996:arithmetical reducibility
477:sets of natural numbers.
383:, halts with output 1 if
333:proved (using results of
205:
4739:Computational healthcare
4734:Differentiable computing
4653:Graphics processing unit
4072:Domain-specific language
3941:Computational complexity
3621:Jockusch, Carl Groos Jr.
3366:Degrees of unsolvability
3099:Handbook of Proof Theory
2846:10.1073/pnas.88.22.10242
2577:10.1112/plms/s2-45.1.161
2397:10.1112/plms/s2-43.6.544
2358:10.1112/plms/s2-42.1.230
2205:is called computable in
2140:Dover Publications, Inc.
1969:Ershov, Yury Leonidovich
1628:analog signal processing
1457:different numbers up to
1266:universal Turing machine
957:Truth-table reducibility
745:hyperimmune-free degrees
105:subrecursive hierarchies
87:What does it mean for a
6207:Self-verifying theories
6028:Tarski's axiomatization
4979:Tarski's undefinability
4974:incompleteness theorems
4714:Computational chemistry
4648:Photograph manipulation
4539:Artificial intelligence
4355:Decision support system
3596:Information and Control
3474:Enderton, Herbert Bruce
3393:Oxford University Press
3364:Lerman, Manuel (1983).
3323:Osherson, Daniel Nathan
3293:Hilbert's Tenth Problem
3156:Simpson, Stephen George
2975:Higher Recursion Theory
2811:Harrington, Leo Anthony
2226:Davis' 1965 compilation
2187:Oxford University Press
1821:Computability in Europe
1774:recursively enumerable
1699:second-order arithmetic
1684:incompleteness theorems
1652:Blum–Shub–Smale machine
1561:which differs from the
1547:arithmetic reducibility
1135:recursive comprehension
1119:second-order arithmetic
971:is Turing reducible to
705:is Turing reducible to
689:is Turing reducible to
609:degree of unsolvability
597:is Turing reducible to
343:Hilbert's tenth problem
329:of the group. In 1970,
319:word problem for groups
18:Theory of computability
6581:Mathematics portal
6192:Proof of impossibility
5840:propositional variable
5150:Propositional calculus
4779:Educational technology
4610:Reinforcement learning
4360:Process control system
4258:Computational geometry
4248:Algorithmic efficiency
4243:Analysis of algorithms
3891:Systems on Chip (SoCs)
3441:Odifreddi, Piergiorgio
3411:Odifreddi, Piergiorgio
2946:10.1215/ijm/1256044641
2919:Slaman, Theodore Allen
2779:Simpson, Steven George
2666:Slaman, Theodore Allen
2181:; et al. (eds.).
1758:computably enumerable
1664:arithmetical hierarchy
1644:differential equations
1592:
1563:arithmetical hierarchy
1315:, for which functions
1307:with 0 <
1261:algorithmic randomness
1062:arithmetical hierarchy
818:arithmetical hierarchy
527:oracle Turing machines
523:relative computability
488:recursively enumerable
446:
432:
339:Matiyasevich's theorem
288:
280:
6450:Kolmogorov complexity
6403:Computably enumerable
6303:Model complete theory
6095:Principia Mathematica
5155:Propositional formula
4984:Banach–Tarski paradox
4749:Electronic publishing
4719:Computational biology
4709:Computational physics
4605:Unsupervised learning
4519:Distributed computing
4395:Information retrieval
4302:Mathematical analysis
4292:Mathematical software
4175:Theory of computation
4140:Software construction
4130:Requirements analysis
4008:Software organization
3936:Computer architecture
3906:Hardware acceleration
3871:Printed circuit board
3670:Annals of Mathematics
3542:Friedberg, Richard M.
3127:Fortnow, Lance Jeremy
2884:Annals of Mathematics
2662:Shore, Richard Arnold
2559:Turing, Alan Mathison
2372:Turing, Alan Mathison
2340:Turing, Alan Mathison
2105:. pp. 300, 376.
2064:University of Chicago
1945:computably enumerable
1929:André Nies's homepage
1678:in the proofs of his
1593:
1401:)-recursive for some
1295:Frequency computation
1257:Kolmogorov complexity
1251:Kolmogorov complexity
1245:Kolmogorov complexity
1212:Automorphism problems
1177:Further information:
1163:Admissible numberings
907:Many-one reducibility
844:strong reducibilities
624:computably enumerable
425:μ-recursive functions
421:models of computation
379:that, given a number
341:, which implies that
117:recursive mathematics
54:theory of computation
6601:Computability theory
6398:Church–Turing thesis
6385:Computability theory
5594:continuum hypothesis
5112:Square of opposition
4970:Gödel's completeness
4509:Concurrent computing
4481:Ubiquitous computing
4453:Application security
4448:Information security
4277:Discrete mathematics
4253:Randomized algorithm
4205:Computability theory
4183:Model of computation
4155:Software maintenance
4150:Software engineering
4112:Software development
4062:Programming language
4057:Programming paradigm
3974:Network architecture
3661:Kleene, Stephen Cole
3387:Nies, André (2009).
3267:Computability Theory
3105:. pp. 149–208.
3008:. pp. 209–224.
2923:Woodin, William Hugh
2879:Soare, Robert Irving
2815:Soare, Robert Irving
2504:Soare, Robert Irving
2469:Soare, Robert Irving
2095:Kleene, Stephen Cole
2049:Soare, Robert Irving
1790:computability theory
1680:completeness theorem
1638:and continuous-time
1570:
1559:analytical hierarchy
1493:(1), ...,
858:One-one reducibility
832:Other reducibilities
567:is also said to be (
447:Entscheidungsproblem
353:Turing computability
347:Diophantine equation
290:Entscheidungsproblem
259:Church–Turing thesis
254:Turing computability
58:computable functions
38:Computability theory
6552:Mathematical object
6443:P versus NP problem
6408:Computable function
6202:Reverse mathematics
6128:Logical consequence
6005:primitive recursive
6000:elementary function
5773:Free/bound variable
5626:Tarski–Grothendieck
5145:Logical connectives
5075:Logical equivalence
4925:Logical consequence
4784:Document management
4774:Operations research
4699:Enterprise software
4615:Multi-task learning
4600:Supervised learning
4322:Information systems
4145:Software deployment
4102:Software repository
3956:Real-time computing
3699:Myhill, John R. Sr.
3325:; Royer, James S.;
3222:Rogers, Hartley Jr.
2969:Sacks, Gerald Enoch
2837:1991PNAS...8810242H
2831:(22): 10242–10246.
2729:Computational Logic
1859:Computability logic
1738:Goodstein's theorem
1726:primitive recursive
1703:reverse mathematics
1668:first-order formula
1587:
1473:Inductive inference
1363:such that at least
1229: −
1173:The priority method
1167:Friedberg numbering
1114:reverse mathematics
1107:Reverse mathematics
1101:Reverse mathematics
848:Weak reducibilities
667:many-one equivalent
375:set) if there is a
284:effectively decided
267:computable function
6606:Mathematical logic
6350:Transfer principle
6313:Semantics of logic
6298:Categorical theory
6274:Non-standard model
5788:Logical connective
4915:Information theory
4864:Mathematical logic
4567:Search methodology
4514:Parallel computing
4471:Interaction design
4380:Computing platform
4307:Numerical analysis
4297:Information theory
4082:Software framework
4045:Software notations
3984:Network components
3881:Integrated circuit
3796:2011-02-17 at the
3271:Chapman & Hall
2189:. pp. 144ff.
1981:Remmel, Jeffrey B.
1734:Ackermann function
1720:. For example, in
1632:analog electronics
1620:analog computation
1588:
1573:
1555:α-recursion theory
1505:learns a function
1358:, ..., y
1050:many-one reduction
919:many-one reducible
878:injective function
631:many-one reduction
405:recursive function
46:mathematical logic
6588:
6587:
6520:Abstract category
6323:Theories of truth
6133:Rule of inference
6123:Natural deduction
6104:
6103:
5649:
5648:
5354:Cartesian product
5259:
5258:
5165:Many-valued logic
5140:Boolean functions
5023:Russell's paradox
4998:diagonal argument
4895:First-order logic
4830:
4829:
4759:Electronic voting
4689:Quantum Computing
4682:Applied computing
4668:Image compression
4438:Hardware security
4428:Security services
4385:Digital marketing
4165:Open-source model
4077:Modeling language
3989:Network scheduler
3402:978-0-19-923076-1
3112:978-0-08-053318-6
3033:978-1-4613-3396-8
2746:978-0-444-51624-4
2430:Cutland, Nigel J.
2196:978-0-19-514721-6
2179:Feferman, Solomon
2149:978-0-486-43228-1
1931:has it published.
1846:Philosophy portal
1648:dynamical systems
1367:of the equations
1337:, ...,
1189:priority argument
866:one-one reducible
719:Turing equivalent
498:Areas of research
373:Turing computable
331:Yuri Matiyasevich
297:Many problems in
223:
222:
95:to be computable?
44:, is a branch of
16:(Redirected from
6613:
6579:
6578:
6530:History of logic
6525:Category of sets
6418:Decision problem
6197:Ordinal analysis
6138:Sequent calculus
6036:Boolean algebras
5976:
5975:
5950:
5921:logical/constant
5675:
5661:
5584:Zermelo–Fraenkel
5335:Set operations:
5270:
5207:
5038:
5018:Löwenheim–Skolem
4905:Formal semantics
4857:
4850:
4843:
4834:
4820:
4819:
4810:
4809:
4800:
4799:
4620:Cross-validation
4592:Machine learning
4476:Social computing
4443:Network security
4238:Algorithm design
4160:Programming team
4120:Control variable
4097:Software library
4035:Software quality
4030:Operating system
3979:Network protocol
3844:Computer science
3837:
3830:
3823:
3814:
3770:
3728:
3694:
3656:
3646:
3614:
3612:
3592:
3579:
3537:
3507:
3462:
3447:. Vol. II.
3436:
3420:
3406:
3383:
3360:
3333:(2nd ed.).
3310:
3284:
3263:Cooper, S. Barry
3244:
3243:
3228:(2nd ed.).
3218:
3212:
3211:
3209:
3208:
3189:Friedman, Harvey
3185:
3179:
3178:
3176:
3175:
3152:
3146:
3145:
3143:
3142:
3123:
3117:
3116:
3086:
3080:
3079:
3069:
3044:
3038:
3037:
3017:
3001:
2995:
2994:
2978:
2965:
2959:
2958:
2948:
2915:
2909:
2908:
2875:
2869:
2868:
2858:
2848:
2807:
2801:
2800:
2775:
2766:
2765:
2763:
2757:. Archived from
2726:
2717:
2708:
2707:
2689:
2658:
2652:
2646:
2636:
2607:
2596:
2590:
2588:
2555:
2549:
2548:
2512:
2500:
2491:
2490:
2465:
2456:
2455:
2439:
2426:
2420:
2414:
2412:
2411:
2405:
2380:
2369:
2336:
2327:
2321:
2280:
2274:
2268:
2235:
2229:
2219:
2171:
2165:
2164:
2126:
2117:
2116:
2091:
2082:
2081:
2079:
2078:
2072:
2057:
2045:
2039:
2038:
2009:
2003:
2002:
1965:
1948:
1938:
1932:
1925:
1919:
1912:
1906:
1893:
1887:
1880:
1848:
1843:
1842:
1841:
1801:Erlangen program
1786:recursion theory
1730:Peano arithmetic
1714:Peano arithmetic
1624:analog computers
1597:
1595:
1594:
1589:
1586:
1581:
1433: <
1413: >
1311: <
789:limit-computable
548:Turing reducible
513:Turing reduction
475:uncountably many
471:Cantor's theorem
452:Nigel J. Cutland
449:
435:
327:identity element
293:
208:
201:
195:
190:
188:
183:
178:
129:
113:formal languages
50:computer science
42:recursion theory
40:, also known as
21:
6621:
6620:
6616:
6615:
6614:
6612:
6611:
6610:
6591:
6590:
6589:
6584:
6573:
6566:
6511:Category theory
6501:Algebraic logic
6484:
6455:Lambda calculus
6393:Church encoding
6379:
6355:Truth predicate
6211:
6177:Complete theory
6100:
5969:
5965:
5961:
5956:
5948:
5668: and
5664:
5659:
5645:
5621:New Foundations
5589:axiom of choice
5572:
5534:Gödel numbering
5474: and
5466:
5370:
5255:
5205:
5186:
5135:Boolean algebra
5121:
5085:Equiconsistency
5050:Classical logic
5027:
5008:Halting problem
4996: and
4972: and
4960: and
4959:
4954:Theorems (
4949:
4866:
4861:
4831:
4826:
4817:
4788:
4769:Word processing
4677:
4663:Virtual reality
4624:
4586:
4557:Computer vision
4533:
4529:Multiprocessing
4495:
4457:
4423:Security hacker
4399:
4375:Digital library
4316:
4267:Mathematics of
4262:
4224:
4200:Automata theory
4195:Formal language
4169:
4135:Software design
4106:
4039:
4025:Virtual machine
4003:
3999:Network service
3960:
3951:Embedded system
3924:
3857:
3846:
3841:
3798:Wayback Machine
3782:
3751:10.2307/2267170
3733:Post, Emil Leon
3731:
3697:
3683:10.2307/1969708
3665:Post, Emil Leon
3659:
3619:
3590:
3582:
3560:10.2307/2964290
3540:
3517:
3504:
3472:
3459:
3439:
3433:
3409:
3403:
3386:
3380:
3370:Springer-Verlag
3363:
3349:
3320:
3307:
3287:
3281:
3261:
3253:
3251:Further reading
3248:
3247:
3240:
3220:
3219:
3215:
3206:
3204:
3187:
3186:
3182:
3173:
3171:
3154:
3153:
3149:
3140:
3138:
3125:
3124:
3120:
3113:
3095:Buss, Samuel R.
3088:
3087:
3083:
3046:
3045:
3041:
3034:
3003:
3002:
2998:
2991:
2981:Springer-Verlag
2967:
2966:
2962:
2917:
2916:
2912:
2897:10.2307/1970842
2877:
2876:
2872:
2809:
2808:
2804:
2797:
2787:Springer-Verlag
2777:
2776:
2769:
2761:
2747:
2724:
2719:
2718:
2711:
2660:
2659:
2655:
2611:Post, Emil Leon
2609:
2608:
2599:
2557:
2556:
2552:
2510:
2502:
2501:
2494:
2487:
2477:Springer-Verlag
2467:
2466:
2459:
2452:
2428:
2427:
2423:
2409:
2407:
2403:
2378:
2370:
2338:
2337:
2330:
2302:10.2307/2269326
2282:
2281:
2277:
2257:10.2307/2371045
2237:
2236:
2232:
2209:if there is in
2199:. p. 150:
2197:
2177:(1990). "". In
2173:
2172:
2168:
2150:
2132:, ed. (2004) .
2128:
2127:
2120:
2113:
2093:
2092:
2085:
2076:
2074:
2070:
2055:
2047:
2046:
2042:
2011:
2010:
2006:
1999:
1967:
1966:
1962:
1957:
1952:
1951:
1939:
1935:
1926:
1922:
1913:
1909:
1898:The Undecidable
1894:
1890:
1881:
1877:
1872:
1844:
1839:
1837:
1834:
1810:
1750:Robert I. Soare
1746:
1660:
1646:and continuous
1622:that occurs in
1616:
1568:
1567:
1543:
1475:
1383:
1376:
1361:
1357:
1353:
1342:
1336:
1329:
1297:
1253:
1247:
1214:
1205:
1185:priority method
1181:
1175:
1143:
1127:Stephen Simpson
1123:Harvey Friedman
1111:The program of
1109:
1103:
1096:
1092:
1086:
1079:
1075:
1071:
1067:
1042:halting problem
1034:
1008:
941:if and only if
933:such that each
891:if and only if
883:such that each
840:
834:
616:halting problem
573:computable from
519:
511:Main articles:
509:
500:
463:halting problem
456:Robert I. Soare
363:(also called a
355:
218:
207:Does not appear
206:
199:
193:
186:
184:
181:
176:
125:
93:natural numbers
35:
28:
23:
22:
15:
12:
11:
5:
6619:
6617:
6609:
6608:
6603:
6593:
6592:
6586:
6585:
6571:
6568:
6567:
6565:
6564:
6559:
6554:
6549:
6544:
6543:
6542:
6532:
6527:
6522:
6513:
6508:
6503:
6498:
6496:Abstract logic
6492:
6490:
6486:
6485:
6483:
6482:
6477:
6475:Turing machine
6472:
6467:
6462:
6457:
6452:
6447:
6446:
6445:
6440:
6435:
6430:
6425:
6415:
6413:Computable set
6410:
6405:
6400:
6395:
6389:
6387:
6381:
6380:
6378:
6377:
6372:
6367:
6362:
6357:
6352:
6347:
6342:
6341:
6340:
6335:
6330:
6320:
6315:
6310:
6308:Satisfiability
6305:
6300:
6295:
6294:
6293:
6283:
6282:
6281:
6271:
6270:
6269:
6264:
6259:
6254:
6249:
6239:
6238:
6237:
6232:
6225:Interpretation
6221:
6219:
6213:
6212:
6210:
6209:
6204:
6199:
6194:
6189:
6179:
6174:
6173:
6172:
6171:
6170:
6160:
6155:
6145:
6140:
6135:
6130:
6125:
6120:
6114:
6112:
6106:
6105:
6102:
6101:
6099:
6098:
6090:
6089:
6088:
6087:
6082:
6081:
6080:
6075:
6070:
6050:
6049:
6048:
6046:minimal axioms
6043:
6032:
6031:
6030:
6019:
6018:
6017:
6012:
6007:
6002:
5997:
5992:
5979:
5977:
5958:
5957:
5955:
5954:
5953:
5952:
5940:
5935:
5934:
5933:
5928:
5923:
5918:
5908:
5903:
5898:
5893:
5892:
5891:
5886:
5876:
5875:
5874:
5869:
5864:
5859:
5849:
5844:
5843:
5842:
5837:
5832:
5822:
5821:
5820:
5815:
5810:
5805:
5800:
5795:
5785:
5780:
5775:
5770:
5769:
5768:
5763:
5758:
5753:
5743:
5738:
5736:Formation rule
5733:
5728:
5727:
5726:
5721:
5711:
5710:
5709:
5699:
5694:
5689:
5684:
5678:
5672:
5655:Formal systems
5651:
5650:
5647:
5646:
5644:
5643:
5638:
5633:
5628:
5623:
5618:
5613:
5608:
5603:
5598:
5597:
5596:
5591:
5580:
5578:
5574:
5573:
5571:
5570:
5569:
5568:
5558:
5553:
5552:
5551:
5544:Large cardinal
5541:
5536:
5531:
5526:
5521:
5507:
5506:
5505:
5500:
5495:
5480:
5478:
5468:
5467:
5465:
5464:
5463:
5462:
5457:
5452:
5442:
5437:
5432:
5427:
5422:
5417:
5412:
5407:
5402:
5397:
5392:
5387:
5381:
5379:
5372:
5371:
5369:
5368:
5367:
5366:
5361:
5356:
5351:
5346:
5341:
5333:
5332:
5331:
5326:
5316:
5311:
5309:Extensionality
5306:
5304:Ordinal number
5301:
5291:
5286:
5285:
5284:
5273:
5267:
5261:
5260:
5257:
5256:
5254:
5253:
5248:
5243:
5238:
5233:
5228:
5223:
5222:
5221:
5211:
5210:
5209:
5196:
5194:
5188:
5187:
5185:
5184:
5183:
5182:
5177:
5172:
5162:
5157:
5152:
5147:
5142:
5137:
5131:
5129:
5123:
5122:
5120:
5119:
5114:
5109:
5104:
5099:
5094:
5089:
5088:
5087:
5077:
5072:
5067:
5062:
5057:
5052:
5046:
5044:
5035:
5029:
5028:
5026:
5025:
5020:
5015:
5010:
5005:
5000:
4988:Cantor's
4986:
4981:
4976:
4966:
4964:
4951:
4950:
4948:
4947:
4942:
4937:
4932:
4927:
4922:
4917:
4912:
4907:
4902:
4897:
4892:
4887:
4886:
4885:
4874:
4872:
4868:
4867:
4862:
4860:
4859:
4852:
4845:
4837:
4828:
4827:
4825:
4824:
4814:
4804:
4793:
4790:
4789:
4787:
4786:
4781:
4776:
4771:
4766:
4761:
4756:
4751:
4746:
4741:
4736:
4731:
4726:
4721:
4716:
4711:
4706:
4701:
4696:
4691:
4685:
4683:
4679:
4678:
4676:
4675:
4673:Solid modeling
4670:
4665:
4660:
4655:
4650:
4645:
4640:
4634:
4632:
4626:
4625:
4623:
4622:
4617:
4612:
4607:
4602:
4596:
4594:
4588:
4587:
4585:
4584:
4579:
4574:
4572:Control method
4569:
4564:
4559:
4554:
4549:
4543:
4541:
4535:
4534:
4532:
4531:
4526:
4524:Multithreading
4521:
4516:
4511:
4505:
4503:
4497:
4496:
4494:
4493:
4488:
4483:
4478:
4473:
4467:
4465:
4459:
4458:
4456:
4455:
4450:
4445:
4440:
4435:
4430:
4425:
4420:
4418:Formal methods
4415:
4409:
4407:
4401:
4400:
4398:
4397:
4392:
4390:World Wide Web
4387:
4382:
4377:
4372:
4367:
4362:
4357:
4352:
4347:
4342:
4337:
4332:
4326:
4324:
4318:
4317:
4315:
4314:
4309:
4304:
4299:
4294:
4289:
4284:
4279:
4273:
4271:
4264:
4263:
4261:
4260:
4255:
4250:
4245:
4240:
4234:
4232:
4226:
4225:
4223:
4222:
4217:
4212:
4207:
4202:
4197:
4192:
4191:
4190:
4179:
4177:
4171:
4170:
4168:
4167:
4162:
4157:
4152:
4147:
4142:
4137:
4132:
4127:
4122:
4116:
4114:
4108:
4107:
4105:
4104:
4099:
4094:
4089:
4084:
4079:
4074:
4069:
4064:
4059:
4053:
4051:
4041:
4040:
4038:
4037:
4032:
4027:
4022:
4017:
4011:
4009:
4005:
4004:
4002:
4001:
3996:
3991:
3986:
3981:
3976:
3970:
3968:
3962:
3961:
3959:
3958:
3953:
3948:
3943:
3938:
3932:
3930:
3926:
3925:
3923:
3922:
3913:
3908:
3903:
3898:
3893:
3888:
3883:
3878:
3873:
3867:
3865:
3859:
3858:
3851:
3848:
3847:
3842:
3840:
3839:
3832:
3825:
3817:
3811:
3810:
3805:
3800:
3788:
3781:
3780:External links
3778:
3777:
3776:
3729:
3695:
3677:(3): 379–407.
3657:
3637:(2): 420–436.
3617:
3603:(5): 447–474.
3580:
3554:(3): 309–316.
3538:
3528:(1–3): 71–91.
3514:
3513:
3509:
3508:
3502:
3469:
3468:
3464:
3463:
3457:
3437:
3431:
3407:
3401:
3384:
3378:
3361:
3347:
3321:Jain, Sanjay;
3317:
3316:
3315:Advanced texts
3312:
3311:
3305:
3285:
3279:
3258:
3257:
3252:
3249:
3246:
3245:
3238:
3213:
3197:FOM email list
3191:(1998-08-28).
3180:
3164:FOM email list
3158:(1998-08-24).
3147:
3129:(2004-02-15).
3118:
3111:
3081:
3039:
3032:
3015:10.1.1.53.1991
2996:
2989:
2960:
2939:(2): 320–334.
2910:
2870:
2802:
2795:
2767:
2764:on 2013-04-20.
2745:
2709:
2680:(6): 711–722.
2653:
2627:(5): 284–316.
2597:
2571:(1): 161–228.
2550:
2529:10.2307/420992
2523:(3): 284–321.
2492:
2485:
2457:
2450:
2421:
2391:(1): 544–546.
2352:(1): 230–265.
2328:
2284:Church, Alonzo
2275:
2251:(2): 345–363.
2239:Church, Alonzo
2230:
2195:
2166:
2152:. p. 84:
2148:
2118:
2111:
2083:
2051:(2011-12-22).
2040:
2029:(3): 877–884.
2004:
1997:
1959:
1958:
1956:
1953:
1950:
1949:
1933:
1920:
1907:
1888:
1874:
1873:
1871:
1868:
1867:
1866:
1861:
1856:
1850:
1849:
1833:
1830:
1809:
1806:
1745:
1742:
1672:Post's theorem
1659:
1656:
1642:, modelled by
1640:control theory
1615:
1612:
1606:is studied in
1585:
1580:
1576:
1542:
1539:
1474:
1471:
1381:
1374:
1359:
1355:
1351:
1340:
1334:
1327:
1296:
1293:
1249:Main article:
1246:
1243:
1213:
1210:
1204:
1201:
1174:
1171:
1142:
1139:
1105:Main article:
1102:
1099:
1094:
1088:
1081:
1077:
1073:
1069:
1065:
1058:Rice's theorem
1032:
1007:
1004:
981:
980:
954:
913:be injective.
904:
836:Main article:
833:
830:
814:Post's theorem
777:random degrees
769:g(x) < f(x)
736:Post's problem
675:
674:
627:
559:when run with
508:
505:
499:
496:
467:countably many
377:Turing machine
360:computable set
354:
351:
335:Julia Robinson
243:Stephen Kleene
221:
220:
203:
202:
197:
191:
179:
174:
171:
168:
165:
157:
156:
153:
150:
147:
144:
141:
138:
135:
124:
121:
109:formal methods
100:
99:
96:
62:Turing degrees
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6618:
6607:
6604:
6602:
6599:
6598:
6596:
6583:
6582:
6577:
6569:
6563:
6560:
6558:
6555:
6553:
6550:
6548:
6545:
6541:
6538:
6537:
6536:
6533:
6531:
6528:
6526:
6523:
6521:
6517:
6514:
6512:
6509:
6507:
6504:
6502:
6499:
6497:
6494:
6493:
6491:
6487:
6481:
6478:
6476:
6473:
6471:
6470:Recursive set
6468:
6466:
6463:
6461:
6458:
6456:
6453:
6451:
6448:
6444:
6441:
6439:
6436:
6434:
6431:
6429:
6426:
6424:
6421:
6420:
6419:
6416:
6414:
6411:
6409:
6406:
6404:
6401:
6399:
6396:
6394:
6391:
6390:
6388:
6386:
6382:
6376:
6373:
6371:
6368:
6366:
6363:
6361:
6358:
6356:
6353:
6351:
6348:
6346:
6343:
6339:
6336:
6334:
6331:
6329:
6326:
6325:
6324:
6321:
6319:
6316:
6314:
6311:
6309:
6306:
6304:
6301:
6299:
6296:
6292:
6289:
6288:
6287:
6284:
6280:
6279:of arithmetic
6277:
6276:
6275:
6272:
6268:
6265:
6263:
6260:
6258:
6255:
6253:
6250:
6248:
6245:
6244:
6243:
6240:
6236:
6233:
6231:
6228:
6227:
6226:
6223:
6222:
6220:
6218:
6214:
6208:
6205:
6203:
6200:
6198:
6195:
6193:
6190:
6187:
6186:from ZFC
6183:
6180:
6178:
6175:
6169:
6166:
6165:
6164:
6161:
6159:
6156:
6154:
6151:
6150:
6149:
6146:
6144:
6141:
6139:
6136:
6134:
6131:
6129:
6126:
6124:
6121:
6119:
6116:
6115:
6113:
6111:
6107:
6097:
6096:
6092:
6091:
6086:
6085:non-Euclidean
6083:
6079:
6076:
6074:
6071:
6069:
6068:
6064:
6063:
6061:
6058:
6057:
6055:
6051:
6047:
6044:
6042:
6039:
6038:
6037:
6033:
6029:
6026:
6025:
6024:
6020:
6016:
6013:
6011:
6008:
6006:
6003:
6001:
5998:
5996:
5993:
5991:
5988:
5987:
5985:
5981:
5980:
5978:
5973:
5967:
5962:Example
5959:
5951:
5946:
5945:
5944:
5941:
5939:
5936:
5932:
5929:
5927:
5924:
5922:
5919:
5917:
5914:
5913:
5912:
5909:
5907:
5904:
5902:
5899:
5897:
5894:
5890:
5887:
5885:
5882:
5881:
5880:
5877:
5873:
5870:
5868:
5865:
5863:
5860:
5858:
5855:
5854:
5853:
5850:
5848:
5845:
5841:
5838:
5836:
5833:
5831:
5828:
5827:
5826:
5823:
5819:
5816:
5814:
5811:
5809:
5806:
5804:
5801:
5799:
5796:
5794:
5791:
5790:
5789:
5786:
5784:
5781:
5779:
5776:
5774:
5771:
5767:
5764:
5762:
5759:
5757:
5754:
5752:
5749:
5748:
5747:
5744:
5742:
5739:
5737:
5734:
5732:
5729:
5725:
5722:
5720:
5719:by definition
5717:
5716:
5715:
5712:
5708:
5705:
5704:
5703:
5700:
5698:
5695:
5693:
5690:
5688:
5685:
5683:
5680:
5679:
5676:
5673:
5671:
5667:
5662:
5656:
5652:
5642:
5639:
5637:
5634:
5632:
5629:
5627:
5624:
5622:
5619:
5617:
5614:
5612:
5609:
5607:
5606:Kripke–Platek
5604:
5602:
5599:
5595:
5592:
5590:
5587:
5586:
5585:
5582:
5581:
5579:
5575:
5567:
5564:
5563:
5562:
5559:
5557:
5554:
5550:
5547:
5546:
5545:
5542:
5540:
5537:
5535:
5532:
5530:
5527:
5525:
5522:
5519:
5515:
5511:
5508:
5504:
5501:
5499:
5496:
5494:
5491:
5490:
5489:
5485:
5482:
5481:
5479:
5477:
5473:
5469:
5461:
5458:
5456:
5453:
5451:
5450:constructible
5448:
5447:
5446:
5443:
5441:
5438:
5436:
5433:
5431:
5428:
5426:
5423:
5421:
5418:
5416:
5413:
5411:
5408:
5406:
5403:
5401:
5398:
5396:
5393:
5391:
5388:
5386:
5383:
5382:
5380:
5378:
5373:
5365:
5362:
5360:
5357:
5355:
5352:
5350:
5347:
5345:
5342:
5340:
5337:
5336:
5334:
5330:
5327:
5325:
5322:
5321:
5320:
5317:
5315:
5312:
5310:
5307:
5305:
5302:
5300:
5296:
5292:
5290:
5287:
5283:
5280:
5279:
5278:
5275:
5274:
5271:
5268:
5266:
5262:
5252:
5249:
5247:
5244:
5242:
5239:
5237:
5234:
5232:
5229:
5227:
5224:
5220:
5217:
5216:
5215:
5212:
5208:
5203:
5202:
5201:
5198:
5197:
5195:
5193:
5189:
5181:
5178:
5176:
5173:
5171:
5168:
5167:
5166:
5163:
5161:
5158:
5156:
5153:
5151:
5148:
5146:
5143:
5141:
5138:
5136:
5133:
5132:
5130:
5128:
5127:Propositional
5124:
5118:
5115:
5113:
5110:
5108:
5105:
5103:
5100:
5098:
5095:
5093:
5090:
5086:
5083:
5082:
5081:
5078:
5076:
5073:
5071:
5068:
5066:
5063:
5061:
5058:
5056:
5055:Logical truth
5053:
5051:
5048:
5047:
5045:
5043:
5039:
5036:
5034:
5030:
5024:
5021:
5019:
5016:
5014:
5011:
5009:
5006:
5004:
5001:
4999:
4995:
4991:
4987:
4985:
4982:
4980:
4977:
4975:
4971:
4968:
4967:
4965:
4963:
4957:
4952:
4946:
4943:
4941:
4938:
4936:
4933:
4931:
4928:
4926:
4923:
4921:
4918:
4916:
4913:
4911:
4908:
4906:
4903:
4901:
4898:
4896:
4893:
4891:
4888:
4884:
4881:
4880:
4879:
4876:
4875:
4873:
4869:
4865:
4858:
4853:
4851:
4846:
4844:
4839:
4838:
4835:
4823:
4815:
4813:
4805:
4803:
4795:
4794:
4791:
4785:
4782:
4780:
4777:
4775:
4772:
4770:
4767:
4765:
4762:
4760:
4757:
4755:
4752:
4750:
4747:
4745:
4742:
4740:
4737:
4735:
4732:
4730:
4727:
4725:
4722:
4720:
4717:
4715:
4712:
4710:
4707:
4705:
4702:
4700:
4697:
4695:
4692:
4690:
4687:
4686:
4684:
4680:
4674:
4671:
4669:
4666:
4664:
4661:
4659:
4658:Mixed reality
4656:
4654:
4651:
4649:
4646:
4644:
4641:
4639:
4636:
4635:
4633:
4631:
4627:
4621:
4618:
4616:
4613:
4611:
4608:
4606:
4603:
4601:
4598:
4597:
4595:
4593:
4589:
4583:
4580:
4578:
4575:
4573:
4570:
4568:
4565:
4563:
4560:
4558:
4555:
4553:
4550:
4548:
4545:
4544:
4542:
4540:
4536:
4530:
4527:
4525:
4522:
4520:
4517:
4515:
4512:
4510:
4507:
4506:
4504:
4502:
4498:
4492:
4491:Accessibility
4489:
4487:
4486:Visualization
4484:
4482:
4479:
4477:
4474:
4472:
4469:
4468:
4466:
4464:
4460:
4454:
4451:
4449:
4446:
4444:
4441:
4439:
4436:
4434:
4431:
4429:
4426:
4424:
4421:
4419:
4416:
4414:
4411:
4410:
4408:
4406:
4402:
4396:
4393:
4391:
4388:
4386:
4383:
4381:
4378:
4376:
4373:
4371:
4368:
4366:
4363:
4361:
4358:
4356:
4353:
4351:
4348:
4346:
4343:
4341:
4338:
4336:
4333:
4331:
4328:
4327:
4325:
4323:
4319:
4313:
4310:
4308:
4305:
4303:
4300:
4298:
4295:
4293:
4290:
4288:
4285:
4283:
4280:
4278:
4275:
4274:
4272:
4270:
4265:
4259:
4256:
4254:
4251:
4249:
4246:
4244:
4241:
4239:
4236:
4235:
4233:
4231:
4227:
4221:
4218:
4216:
4213:
4211:
4208:
4206:
4203:
4201:
4198:
4196:
4193:
4189:
4186:
4185:
4184:
4181:
4180:
4178:
4176:
4172:
4166:
4163:
4161:
4158:
4156:
4153:
4151:
4148:
4146:
4143:
4141:
4138:
4136:
4133:
4131:
4128:
4126:
4123:
4121:
4118:
4117:
4115:
4113:
4109:
4103:
4100:
4098:
4095:
4093:
4090:
4088:
4085:
4083:
4080:
4078:
4075:
4073:
4070:
4068:
4065:
4063:
4060:
4058:
4055:
4054:
4052:
4050:
4046:
4042:
4036:
4033:
4031:
4028:
4026:
4023:
4021:
4018:
4016:
4013:
4012:
4010:
4006:
4000:
3997:
3995:
3992:
3990:
3987:
3985:
3982:
3980:
3977:
3975:
3972:
3971:
3969:
3967:
3963:
3957:
3954:
3952:
3949:
3947:
3946:Dependability
3944:
3942:
3939:
3937:
3934:
3933:
3931:
3927:
3921:
3917:
3914:
3912:
3909:
3907:
3904:
3902:
3899:
3897:
3894:
3892:
3889:
3887:
3884:
3882:
3879:
3877:
3874:
3872:
3869:
3868:
3866:
3864:
3860:
3855:
3849:
3845:
3838:
3833:
3831:
3826:
3824:
3819:
3818:
3815:
3809:
3806:
3804:
3801:
3799:
3795:
3792:
3789:
3787:
3784:
3783:
3779:
3774:
3771:Reprinted in
3768:
3764:
3760:
3756:
3752:
3748:
3744:
3740:
3739:
3734:
3730:
3726:
3722:
3718:
3714:
3710:
3706:
3705:
3700:
3696:
3692:
3688:
3684:
3680:
3676:
3672:
3671:
3666:
3662:
3658:
3654:
3650:
3645:
3640:
3636:
3632:
3631:
3626:
3622:
3618:
3616:
3611:
3606:
3602:
3598:
3597:
3589:
3585:
3584:Gold, E. Mark
3581:
3577:
3573:
3569:
3565:
3561:
3557:
3553:
3549:
3548:
3543:
3539:
3535:
3531:
3527:
3523:
3522:
3516:
3515:
3511:
3510:
3505:
3503:0-7204-2285-X
3499:
3495:
3491:
3490:North-Holland
3487:
3483:
3479:
3475:
3471:
3470:
3466:
3465:
3460:
3458:0-444-50205-X
3454:
3450:
3446:
3442:
3438:
3434:
3432:0-444-87295-7
3428:
3424:
3423:North-Holland
3419:
3418:
3412:
3408:
3404:
3398:
3394:
3390:
3385:
3381:
3379:3-540-12155-2
3375:
3371:
3367:
3362:
3358:
3354:
3350:
3348:0-262-10077-0
3344:
3340:
3336:
3335:Bradford Book
3332:
3328:
3324:
3319:
3318:
3314:
3313:
3308:
3306:0-262-13295-8
3302:
3298:
3294:
3290:
3286:
3282:
3280:1-58488-237-9
3276:
3272:
3268:
3264:
3260:
3259:
3255:
3254:
3250:
3241:
3239:0-262-68052-1
3235:
3231:
3227:
3223:
3217:
3214:
3202:
3198:
3194:
3190:
3184:
3181:
3169:
3165:
3161:
3157:
3151:
3148:
3136:
3132:
3128:
3122:
3119:
3114:
3108:
3104:
3100:
3096:
3092:
3085:
3082:
3077:
3073:
3068:
3067:10.1.1.6.5519
3063:
3059:
3055:
3054:
3049:
3043:
3040:
3035:
3029:
3025:
3021:
3016:
3011:
3007:
3000:
2997:
2992:
2990:3-540-19305-7
2986:
2982:
2977:
2976:
2970:
2964:
2961:
2956:
2952:
2947:
2942:
2938:
2934:
2933:
2928:
2924:
2920:
2914:
2911:
2906:
2902:
2898:
2894:
2891:(1): 80–120.
2890:
2886:
2885:
2880:
2874:
2871:
2866:
2862:
2857:
2852:
2847:
2842:
2838:
2834:
2830:
2826:
2825:
2820:
2816:
2812:
2806:
2803:
2798:
2796:3-540-64882-8
2792:
2788:
2784:
2780:
2774:
2772:
2768:
2760:
2756:
2752:
2748:
2742:
2738:
2734:
2730:
2723:
2716:
2714:
2710:
2705:
2701:
2697:
2693:
2688:
2683:
2679:
2675:
2671:
2667:
2663:
2657:
2654:
2650:
2647:Reprinted in
2644:
2640:
2635:
2630:
2626:
2622:
2621:
2616:
2612:
2606:
2604:
2602:
2598:
2594:
2591:Reprinted in
2587:
2582:
2578:
2574:
2570:
2566:
2565:
2560:
2554:
2551:
2546:
2542:
2538:
2534:
2530:
2526:
2522:
2518:
2517:
2509:
2505:
2499:
2497:
2493:
2488:
2486:0-387-15299-7
2482:
2478:
2474:
2470:
2464:
2462:
2458:
2453:
2451:0-521-29465-7
2447:
2443:
2438:
2437:
2431:
2425:
2422:
2418:
2415:Reprinted in
2402:
2398:
2394:
2390:
2386:
2385:
2377:
2373:
2367:
2363:
2359:
2355:
2351:
2347:
2346:
2341:
2335:
2333:
2329:
2325:
2322:Reprinted in
2319:
2315:
2311:
2307:
2303:
2299:
2295:
2291:
2290:
2285:
2279:
2276:
2272:
2269:Reprinted in
2266:
2262:
2258:
2254:
2250:
2246:
2245:
2240:
2234:
2231:
2227:
2223:
2218:
2216:
2212:
2208:
2204:
2198:
2192:
2188:
2184:
2180:
2176:
2170:
2167:
2163:
2160:
2156:
2151:
2145:
2141:
2137:
2136:
2131:
2130:Davis, Martin
2125:
2123:
2119:
2114:
2112:0-7204-2103-9
2108:
2104:
2103:North-Holland
2100:
2096:
2090:
2088:
2084:
2069:
2065:
2061:
2054:
2050:
2044:
2041:
2036:
2032:
2028:
2024:
2023:
2018:
2014:
2008:
2005:
2000:
1998:0-7204-2285-X
1994:
1990:
1989:North-Holland
1986:
1982:
1978:
1974:
1970:
1964:
1961:
1954:
1946:
1942:
1937:
1934:
1930:
1924:
1921:
1917:
1911:
1908:
1905:
1901:
1899:
1892:
1889:
1885:
1879:
1876:
1869:
1865:
1862:
1860:
1857:
1855:
1852:
1851:
1847:
1836:
1831:
1829:
1827:
1823:
1822:
1817:
1816:
1807:
1805:
1802:
1798:
1793:
1791:
1787:
1783:
1779:
1775:
1771:
1767:
1763:
1759:
1755:
1751:
1743:
1741:
1739:
1735:
1731:
1727:
1723:
1719:
1715:
1711:
1708:The field of
1706:
1704:
1700:
1695:
1693:
1689:
1685:
1681:
1677:
1673:
1669:
1665:
1657:
1655:
1653:
1649:
1645:
1641:
1637:
1633:
1629:
1625:
1621:
1613:
1611:
1609:
1605:
1601:
1583:
1578:
1564:
1560:
1556:
1552:
1548:
1540:
1538:
1536:
1532:
1529:learns every
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1500:
1496:
1492:
1488:
1484:
1480:
1472:
1470:
1468:
1464:
1460:
1456:
1452:
1448:
1444:
1440:
1436:
1432:
1428:
1424:
1420:
1419:semirecursive
1416:
1412:
1408:
1404:
1400:
1396:
1392:
1388:
1384:
1377:
1370:
1366:
1362:
1347:
1343:
1333:
1326:
1322:
1318:
1314:
1310:
1306:
1302:
1294:
1292:
1290:
1286:
1282:
1278:
1274:
1270:
1267:
1262:
1258:
1255:The field of
1252:
1244:
1242:
1238:
1236:
1232:
1228:
1224:
1220:
1211:
1209:
1202:
1200:
1196:
1194:
1190:
1186:
1180:
1172:
1170:
1168:
1164:
1160:
1156:
1152:
1148:
1140:
1138:
1136:
1132:
1128:
1124:
1120:
1116:
1115:
1108:
1100:
1098:
1091:
1084:
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1028:
1024:
1020:
1016:
1012:
1003:
1001:
997:
992:
988:
986:
978:
974:
970:
966:
962:
958:
955:
952:
948:
944:
940:
936:
932:
928:
924:
920:
916:
912:
908:
905:
902:
898:
894:
890:
886:
882:
879:
875:
871:
867:
863:
859:
856:
855:
854:
851:
849:
845:
839:
831:
829:
827:
821:
819:
815:
811:
807:
803:
802:
797:
792:
790:
786:
782:
778:
774:
770:
766:
763:depending on
762:
758:
754:
750:
746:
740:
738:
737:
731:
727:
722:
720:
716:
712:
708:
704:
700:
696:
692:
688:
684:
680:
672:
668:
664:
660:
656:
652:
648:
644:
640:
636:
632:
628:
625:
621:
620:
619:
617:
612:
610:
607:(also called
606:
605:
604:Turing degree
600:
596:
592:
588:
584:
581:
577:
574:
570:
566:
562:
558:
554:
550:
549:
544:
539:
536:
532:
528:
524:
518:
517:Turing degree
514:
506:
504:
497:
495:
493:
492:semidecidable
489:
485:
484:
478:
476:
472:
468:
464:
459:
457:
453:
448:
443:
439:
434:
428:
426:
422:
418:
414:
410:
406:
402:
400:
394:
390:
386:
382:
378:
374:
370:
366:
362:
361:
352:
350:
348:
344:
340:
336:
332:
328:
324:
320:
316:
315:William Boone
312:
311:Pyotr Novikov
308:
304:
300:
295:
292:
291:
285:
279:
276:
270:
268:
264:
260:
255:
250:
248:
244:
240:
236:
232:
231:Alonzo Church
228:
216:
212:
204:
163:
159:
158:
134:
131:
130:
127:
122:
120:
118:
114:
110:
106:
97:
94:
90:
86:
85:
84:
81:
79:
75:
71:
67:
66:computability
63:
59:
55:
51:
47:
43:
39:
33:
32:Computability
19:
6572:
6384:
6370:Ultraproduct
6217:Model theory
6182:Independence
6118:Formal proof
6110:Proof theory
6093:
6066:
6023:real numbers
5995:second-order
5906:Substitution
5783:Metalanguage
5724:conservative
5697:Axiom schema
5641:Constructive
5611:Morse–Kelley
5577:Set theories
5556:Aleph number
5549:inaccessible
5455:Grothendieck
5339:intersection
5226:Higher-order
5214:Second-order
5160:Truth tables
5117:Venn diagram
4900:Formal proof
4754:Cyberwarfare
4413:Cryptography
4204:
3742:
3736:
3708:
3702:
3674:
3673:. Series 2.
3668:
3634:
3628:
3600:
3594:
3551:
3545:
3525:
3519:
3485:
3482:Barwise, Jon
3444:
3416:
3388:
3365:
3330:
3327:Sharma, Arun
3292:
3266:
3225:
3216:
3205:. Retrieved
3196:
3183:
3172:. Retrieved
3163:
3150:
3139:. Retrieved
3121:
3098:
3084:
3060:(1): 23–44.
3057:
3051:
3042:
3005:
2999:
2974:
2963:
2936:
2930:
2913:
2888:
2882:
2873:
2828:
2822:
2805:
2782:
2759:the original
2728:
2677:
2673:
2656:
2624:
2618:
2568:
2562:
2553:
2520:
2514:
2472:
2435:
2424:
2408:. Retrieved
2388:
2382:
2349:
2343:
2296:(1): 40–41.
2293:
2287:
2278:
2248:
2242:
2233:
2214:
2210:
2206:
2202:
2200:
2182:
2169:
2153:
2142:p. 84.
2134:
2098:
2075:. Retrieved
2059:
2043:
2026:
2020:
2015:(May 1962).
2007:
1984:
1977:Nerode, Anil
1963:
1936:
1923:
1910:
1904:Martin Davis
1897:
1891:
1883:
1878:
1825:
1819:
1813:
1811:
1794:
1789:
1785:
1781:
1777:
1773:
1769:
1765:
1761:
1757:
1753:
1747:
1710:proof theory
1707:
1696:
1661:
1617:
1544:
1534:
1530:
1526:
1522:
1518:
1514:
1510:
1506:
1502:
1498:
1494:
1490:
1486:
1482:
1479:E. Mark Gold
1476:
1466:
1462:
1458:
1454:
1450:
1446:
1442:
1438:
1434:
1430:
1426:
1422:
1414:
1410:
1406:
1402:
1398:
1394:
1390:
1386:
1379:
1372:
1368:
1364:
1349:
1345:
1338:
1331:
1324:
1320:
1316:
1312:
1308:
1304:
1300:
1298:
1288:
1284:
1280:
1276:
1272:
1268:
1254:
1239:
1235:Maximal sets
1230:
1226:
1222:
1218:
1215:
1206:
1197:
1193:requirements
1192:
1188:
1184:
1182:
1158:
1154:
1150:
1146:
1144:
1134:
1112:
1110:
1089:
1082:
1053:
1045:
1037:
1030:
1029:th c.e. set
1026:
1022:
1018:
1014:
1009:
993:
989:
982:
977:Cantor space
972:
968:
964:
960:
950:
946:
942:
938:
934:
930:
926:
922:
918:
914:
910:
900:
896:
892:
888:
884:
880:
873:
869:
865:
861:
852:
847:
843:
841:
825:
822:
809:
805:
799:
795:
793:
784:
776:
772:
768:
764:
760:
756:
752:
749:high degrees
748:
744:
741:
734:
723:
714:
710:
706:
702:
698:
694:
690:
686:
682:
678:
676:
671:m-equivalent
670:
666:
662:
658:
654:
650:
646:
642:
638:
634:
613:
608:
602:
598:
594:
590:
586:
585:). If a set
582:
580:recursive in
579:
575:
572:
568:
564:
560:
556:
552:
546:
542:
540:
534:
530:
522:
520:
501:
491:
487:
481:
479:
473:, there are
460:
441:
437:
429:
416:
412:
408:
404:
396:
392:
388:
384:
380:
372:
368:
364:
358:
356:
296:
281:
272:
251:
224:
214:
161:
132:
126:
123:Introduction
116:
101:
82:
74:proof theory
70:definability
41:
37:
36:
6480:Type theory
6428:undecidable
6360:Truth value
6247:equivalence
5926:non-logical
5539:Enumeration
5529:Isomorphism
5476:cardinality
5460:Von Neumann
5425:Ultrafilter
5390:Uncountable
5324:equivalence
5241:Quantifiers
5231:Fixed-point
5200:First-order
5080:Consistency
5065:Proposition
5042:Traditional
5013:Lindström's
5003:Compactness
4945:Type theory
4890:Cardinality
4764:Video games
4744:Digital art
4501:Concurrency
4370:Data mining
4282:Probability
4015:Interpreter
3745:(1): 1–11.
3711:: 215–220.
3492:. pp.
3048:Moore, Cris
2175:Gödel, Kurt
2013:Radó, Tibor
1768:instead of
1344:a tuple of
1233:is finite.
923:m-reducible
870:1-reducible
801:Turing jump
779:containing
730:hypersimple
299:mathematics
239:Alan Turing
235:Rózsa Péter
213:function Σ(
211:Busy Beaver
6595:Categories
6291:elementary
5984:arithmetic
5852:Quantifier
5830:functional
5702:Expression
5420:Transitive
5364:identities
5349:complement
5282:hereditary
5265:Set theory
4822:Glossaries
4694:E-commerce
4287:Statistics
4230:Algorithms
4188:Stochastic
4020:Middleware
3876:Peripheral
3773:Davis 1965
3207:2006-01-09
3174:2006-01-09
3141:2018-03-22
2649:Davis 1965
2593:Davis 1965
2417:Davis 1965
2410:2022-08-08
2324:Davis 1965
2271:Davis 1965
2222:Kurt Gödel
2155:Kurt Gödel
2077:2017-08-23
1955:References
1941:MathSciNet
1902:edited by
1797:bijections
1676:Kurt Gödel
1608:set theory
1489:(0),
1287:) outputs
1279:such that
1141:Numberings
767:such that
701:such that
645:such that
569:relatively
399:computable
227:Kurt Gödel
52:, and the
6562:Supertask
6465:Recursion
6423:decidable
6257:saturated
6235:of models
6158:deductive
6153:axiomatic
6073:Hilbert's
6060:Euclidean
6041:canonical
5964:axiomatic
5896:Signature
5825:Predicate
5714:Extension
5636:Ackermann
5561:Operation
5440:Universal
5430:Recursive
5405:Singleton
5400:Inhabited
5385:Countable
5375:Types of
5359:power set
5329:partition
5246:Predicate
5192:Predicate
5107:Syllogism
5097:Soundness
5070:Inference
5060:Tautology
4962:paradoxes
4643:Rendering
4638:Animation
4269:computing
4220:Semantics
3911:Processor
3725:123260425
3339:MIT Press
3297:MIT Press
3230:MIT Press
3062:CiteSeerX
3010:CiteSeerX
2696:1073-2780
1575:Π
1378:) =
1221:is below
785:1-generic
622:They are
551:to a set
442:decidable
438:recursive
397:(Turing)
369:recursive
365:decidable
263:algorithm
247:Emil Post
6547:Logicism
6540:timeline
6516:Concrete
6375:Validity
6345:T-schema
6338:Kripke's
6333:Tarski's
6328:semantic
6318:Strength
6267:submodel
6262:spectrum
6230:function
6078:Tarski's
6067:Elements
6054:geometry
6010:Robinson
5931:variable
5916:function
5889:spectrum
5879:Sentence
5835:variable
5778:Language
5731:Relation
5692:Automata
5682:Alphabet
5666:language
5520:-jection
5498:codomain
5484:Function
5445:Universe
5415:Infinite
5319:Relation
5102:Validity
5092:Argument
4990:theorem,
4802:Category
4630:Graphics
4405:Security
4067:Compiler
3966:Networks
3863:Hardware
3794:Archived
3767:30320278
3623:(1968).
3586:(1967).
3576:25834814
3476:(1977).
3449:Elsevier
3443:(1999).
3413:(1989).
3357:98-34861
3329:(1999).
3291:(1993).
3265:(2004).
3224:(1987).
3201:Archived
3168:Archived
3135:Archived
3103:Elsevier
2971:(1990).
2925:(1986).
2865:11607241
2817:(1991).
2781:(1999).
2668:(1999).
2613:(1944).
2506:(1996).
2471:(1987).
2432:(1980).
2401:Archived
2374:(1938).
2318:42323521
2157:(1946):
2097:(1952).
2068:Archived
1983:(1998).
1832:See also
1728:, while
1354:, y
1348:numbers
1131:powerset
949:) is in
899:) is in
773:x > c
771:for all
653: :
433:rekursiv
89:function
6489:Related
6286:Diagram
6184: (
6163:Hilbert
6148:Systems
6143:Theorem
6021:of the
5966:systems
5746:Formula
5741:Grammar
5657: (
5601:General
5314:Forcing
5299:Element
5219:Monadic
4994:paradox
4935:Theorem
4871:General
4812:Outline
3759:2267170
3691:1969708
3653:1994957
3568:2964290
3494:527–566
3484:(ed.).
3097:(ed.).
2955:0840131
2905:1970842
2833:Bibcode
2755:3362163
2704:1739227
2643:0010514
2545:5894394
2310:2269326
2265:2371045
1521:learns
1425:,
1405:,
1397:,
1389:,
1330:,
1323:inputs
685:, then
91:on the
6252:finite
6015:Skolem
5968:
5943:Theory
5911:Symbol
5901:String
5884:atomic
5761:ground
5756:closed
5751:atomic
5707:ground
5670:syntax
5566:binary
5493:domain
5410:Finite
5175:finite
5033:Logics
4992:
4940:Theory
3765:
3757:
3723:
3689:
3651:
3574:
3566:
3500:
3455:
3429:
3399:
3376:
3355:
3345:
3303:
3277:
3273:/CRC.
3236:
3109:
3064:
3030:
3012:
2987:
2953:
2903:
2863:
2853:
2793:
2753:
2743:
2702:
2694:
2641:
2543:
2537:420992
2535:
2483:
2448:
2364:
2316:
2308:
2263:
2193:
2159:Tarski
2146:
2109:
1995:
1900:(1965)
1409:with 2
1036:is in
1025:: the
937:is in
887:is in
798:, the
791:sets.
726:simple
531:oracle
303:Markov
275:Tarski
245:, and
111:, and
6242:Model
5990:Peano
5847:Proof
5687:Arity
5616:Naive
5503:image
5435:Fuzzy
5395:Empty
5344:union
5289:Class
4930:Model
4920:Lemma
4878:Axiom
4215:Logic
4049:tools
3763:S2CID
3755:JSTOR
3721:S2CID
3687:JSTOR
3649:JSTOR
3591:(PDF)
3572:S2CID
3564:JSTOR
3480:. In
3093:. In
2901:JSTOR
2856:52904
2762:(PDF)
2725:(PDF)
2567:. 2.
2541:S2CID
2533:JSTOR
2511:(PDF)
2404:(PDF)
2387:. 2.
2379:(PDF)
2366:73712
2362:S2CID
2348:. 2.
2314:S2CID
2306:JSTOR
2261:JSTOR
2071:(PDF)
2056:(PDF)
1870:Notes
1718:total
1056:(see
925:) to
872:) to
715:every
626:, and
371:, or
323:group
265:is a
6365:Type
6168:list
5972:list
5949:list
5938:Term
5872:rank
5766:open
5660:list
5472:Maps
5377:sets
5236:Free
5206:list
4956:list
4883:list
4047:and
3920:Form
3916:Size
3498:ISBN
3453:ISBN
3427:ISBN
3397:ISBN
3374:ISBN
3353:LCCN
3343:ISBN
3301:ISBN
3275:ISBN
3234:ISBN
3107:ISBN
3028:ISBN
2985:ISBN
2861:PMID
2791:ISBN
2741:ISBN
2692:ISSN
2481:ISBN
2446:ISBN
2191:ISBN
2144:ISBN
2107:ISBN
1993:ISBN
1914:The
1882:The
1788:and
1778:r.e.
1772:and
1762:c.e.
1756:and
1744:Name
1682:and
1553:and
1303:and
1259:and
1149:and
1011:Rice
998:and
921:(or
868:(or
697:and
669:(or
661:) ∈
637:and
593:and
578:and
515:and
490:and
313:and
209:The
194:>
182:>
177:4098
155:...
76:and
68:and
60:and
6052:of
6034:of
5982:of
5514:Sur
5488:Map
5295:Ur-
5277:Set
3747:doi
3713:doi
3679:doi
3639:doi
3635:137
3605:doi
3556:doi
3530:doi
3526:317
3072:doi
3058:162
3020:doi
2941:doi
2893:doi
2889:100
2851:PMC
2841:doi
2733:doi
2682:doi
2629:doi
2581:hdl
2573:doi
2525:doi
2393:doi
2354:doi
2298:doi
2253:doi
2228:).)
2031:doi
1826:CiE
1782:set
1766:set
1533:in
1525:if
1513:of
1093:; Σ
1052:to
1021:= {
967:if
917:is
864:is
804:of
649:= {
545:is
403:or
196:10
185:3.5
173:13
6597::
6438:NP
6062::
6056::
5986::
5663:),
5518:Bi
5510:In
3918:/
3761:.
3753:.
3743:12
3741:.
3719:.
3709:21
3707:.
3685:.
3675:59
3663:;
3647:.
3633:.
3627:.
3601:10
3599:.
3593:.
3570:.
3562:.
3552:23
3550:.
3524:.
3496:.
3488:.
3451:.
3425:.
3421:.
3395:.
3391:.
3372:.
3351:.
3341:.
3337:/
3299:.
3295:.
3269:.
3232:.
3199:.
3195:.
3166:.
3162:.
3133:.
3101:.
3070:.
3056:.
3026:.
3018:.
2983:.
2979:.
2951:MR
2949:.
2937:30
2935:.
2929:.
2921:;
2899:.
2887:.
2859:.
2849:.
2839:.
2829:88
2827:.
2821:.
2813:;
2789:.
2785:.
2770:^
2751:MR
2749:.
2739:.
2712:^
2700:MR
2698:.
2690:.
2676:.
2672:.
2664:;
2639:MR
2637:.
2625:50
2623:.
2617:.
2600:^
2579:.
2569:45
2539:.
2531:.
2519:.
2513:.
2495:^
2479:.
2460:^
2444:.
2440:.
2399:.
2389:43
2381:.
2360:.
2350:42
2331:^
2312:.
2304:.
2292:.
2259:.
2249:58
2247:.
2138:.
2121:^
2101:.
2086:^
2066:.
2062:.
2058:.
2027:41
2025:.
2019:.
1991:.
1987:.
1979:;
1975:;
1971:;
1740:.
1634:,
1630:,
1626:,
1610:.
1549:,
1085:+1
987:.
959::
860::
783:;
775:;
728:,
673:).
571:)
367:,
337:)
249:.
241:,
237:,
233:,
229:,
189:10
170:6
167:4
164:)
160:Σ(
152:7
149:6
146:5
143:4
140:3
137:2
119:.
107:,
80:.
48:,
6518:/
6433:P
6188:)
5974:)
5970:(
5867:∀
5862:!
5857:∃
5818:=
5813:↔
5808:→
5803:∧
5798:∨
5793:¬
5516:/
5512:/
5486:/
5297:)
5293:(
5180:∞
5170:3
4958:)
4856:e
4849:t
4842:v
3856:.
3836:e
3829:t
3822:v
3775:.
3769:.
3749::
3727:.
3715::
3693:.
3681::
3655:.
3641::
3613:.
3607::
3578:.
3558::
3536:.
3532::
3506:.
3461:.
3435:.
3405:.
3382:.
3359:.
3309:.
3283:.
3242:.
3210:.
3177:.
3144:.
3115:.
3078:.
3074::
3036:.
3022::
2993:.
2957:.
2943::
2907:.
2895::
2867:.
2843::
2835::
2799:.
2735::
2706:.
2684::
2678:6
2651:.
2645:.
2631::
2595:.
2589:.
2583::
2575::
2547:.
2527::
2521:2
2489:.
2454:.
2419:.
2413:.
2395::
2368:.
2356::
2326:.
2320:.
2300::
2294:1
2273:.
2267:.
2255::
2217:.
2215:f
2211:S
2207:S
2203:f
2115:.
2080:.
2037:.
2033::
2001:.
1824:(
1780:)
1776:(
1764:)
1760:(
1584:1
1579:1
1535:S
1531:f
1527:M
1523:S
1519:M
1515:f
1511:e
1507:f
1503:M
1499:n
1497:(
1495:f
1491:f
1487:f
1483:S
1467:A
1463:n
1459:n
1455:n
1451:n
1447:A
1443:n
1439:n
1435:n
1431:m
1427:n
1423:m
1415:n
1411:m
1407:n
1403:m
1399:n
1395:m
1391:n
1387:m
1382:k
1380:y
1375:k
1373:x
1371:(
1369:A
1365:m
1360:n
1356:2
1352:1
1350:y
1346:n
1341:n
1339:x
1335:2
1332:x
1328:1
1325:x
1321:n
1317:A
1313:n
1309:m
1305:n
1301:m
1289:x
1285:p
1283:(
1281:U
1277:p
1273:x
1269:U
1231:A
1227:B
1223:B
1219:A
1159:x
1155:e
1151:x
1147:e
1095:1
1090:n
1083:n
1078:4
1074:3
1070:3
1066:2
1054:E
1046:E
1038:C
1033:e
1031:W
1027:e
1023:e
1019:E
1015:C
973:B
969:A
965:B
961:A
953:.
951:B
947:n
945:(
943:f
939:A
935:n
931:f
927:B
915:A
911:f
903:.
901:B
897:n
895:(
893:f
889:A
885:n
881:f
874:B
862:A
826:x
810:A
806:A
796:A
765:g
761:c
757:g
753:f
711:B
707:B
703:A
699:B
695:A
691:B
687:A
683:B
679:A
663:B
659:x
657:(
655:f
651:x
647:A
643:f
639:B
635:A
599:A
595:B
591:B
587:A
583:B
576:B
565:A
561:B
557:A
553:B
543:A
535:n
417:n
415:(
413:f
409:n
401:,
393:f
389:n
385:n
381:n
273:"
215:n
200:?
187:×
162:n
133:n
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.