2147:
518:
447:
3185:
2159:
3195:
3205:
2183:
2171:
913:
is a theoretically interesting idealization of a computer. There are several variants. In most of them, each register can hold a natural number (of unlimited size), and the instructions are simple (and few in number), e.g. only decrementation (combined with conditional jump) and incrementation exist
426:
Automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata. Automata comes from the Greek word (Αυτόματα) which means that
541:
numbers in the list, then if the list is not sorted or indexed in any way we may have to look at every number in order to find the number we're seeking. We thus say that in order to solve this problem, the computer needs to perform a number of steps that grow linearly in the size of the problem.
528:
considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved. Two major aspects are considered: time complexity and space complexity, which are respectively how many steps it takes to perform a computation, and how much memory is
431:
theory, as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set. Automata are used as theoretical models for computing machines, and are used for proofs about
480:
cannot be solved by a Turing machine is one of the most important results in computability theory, as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a Turing machine. Much of computability theory builds on the halting problem result.
918:
techniques: the fact that each register holds a natural number allows the possibility of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriately huge natural number — unambiguity of both representation and interpretation can be established by
536:
requires, computer scientists express the time or space required to solve the problem as a function of the size of the input problem. For example, finding a particular number in a long list of numbers becomes harder as the list of numbers grows larger. If we say there are
709:-calculus). Combinatory logic was developed with great ambitions: understanding the nature of paradoxes, making foundations of mathematics more economic (conceptually), eliminating the notion of variables (thus clarifying their role in mathematics).
458:. It is closely linked with automata theory, as automata are used to generate and recognize formal languages. There are several classes of formal languages, each allowing more complex language specification than the one before it, i.e.
100:. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see
503:, which removes the restriction of studying only models of computation which are reducible to the Turing model. Many mathematicians and computational theorists who study recursion theory will refer to it as computability theory.
108:
problem solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a finite amount of memory.
462:, and each corresponding to a class of automata which recognizes it. Because automata are used as models for computation, formal languages are the preferred mode of specification for any problem that must be computed.
652:
A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of
303:
1425:
A textbook covering the topics of formal languages, automata and grammars. The emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the
885:, then for 'f(5)=3' to appear, terms like 'g(5)=6' and 'h(5,6)=3' must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
721:
its defining sequence, any input value(s) and a sequence of recursive functions appearing in the defining sequence with inputs and outputs. Thus, if in the defining sequence of a recursive function
1301:
1099:
814:
appear, then terms of the form 'g(5)=7' or 'h(3,2)=10' might appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries above by using
248:
346:
419:
883:
388:
707:
683:
812:
549:, which allows functions to be compared in a way that ensures that particular aspects of a machine's construction do not need to be considered, but rather only the
777:
748:
580:
1607:
122:
2221:
954:
Different models of computation have the ability to do different tasks. One way to measure the power of a computational model is to study the class of
914:(and halting). The lack of the infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its role with
815:
2938:
2910:
2963:
1565:
1413:
1398:
1352:
1311:
1109:
1026:
991:
1366:
121:
are used. In the last century, it separated from mathematics and became an independent academic discipline with its own conferences such as
2814:
1970:
476:
Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer. The statement that the
2968:
2240:
1421:
2473:
2115:
1600:
1265:
927:
In addition to the general computational models, some simpler computational models are useful for special, restricted applications.
3120:
2948:
2478:
2187:
1544:
1514:
1492:
1474:
1441:
1376:
1330:
1075:
270:
92:
In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a
3208:
2302:
1651:
126:
2596:
2065:
525:
512:
215:
83:
2849:
3229:
2887:
2506:
2214:
2163:
117:
The theory of computation can be considered the creation of models of all kinds in the field of computer science. Therefore,
3029:
3006:
2736:
2726:
1593:
3110:
2698:
2606:
2511:
2287:
2272:
1537:
Computability: Computable
Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.)
1429:
1253:
948:
47:
31:
3198:
2933:
2431:
2090:
1646:
455:
3170:
2819:
1661:
1018:
606:
1258:
The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed)
3188:
3115:
3090:
2953:
2601:
2207:
2075:
2047:
1684:
902:
602:
258:
640:
101:
3039:
2872:
2458:
2327:
2120:
263:
227:
67:
454:
Language theory is a branch of mathematics concerned with describing languages as a set of operations over an
3100:
3034:
2925:
2741:
2401:
2005:
1995:
1965:
1899:
1634:
894:
823:
712:
2175:
3165:
2996:
2877:
2644:
2634:
2629:
2103:
2000:
1980:
1975:
1904:
1629:
1416:
An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
360:
325:
63:
1532:
3135:
3105:
3095:
2991:
2905:
2781:
2721:
2688:
2678:
2526:
2516:
2453:
2322:
2297:
2292:
2257:
2130:
1937:
1861:
1800:
1785:
1780:
1757:
1639:
1528:
1449:
1401:
A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
936:
2146:
2895:
2867:
2839:
2834:
2663:
2639:
2591:
2574:
2569:
2551:
2541:
2536:
2498:
2448:
2443:
2360:
2306:
2110:
1990:
1985:
1909:
1810:
940:
932:
630:
489:
471:
395:
312:
105:
104:). It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any
93:
79:
829:
367:
3160:
3085:
3001:
2986:
2751:
2531:
2488:
2483:
2380:
2370:
2342:
2125:
2035:
1957:
1856:
1790:
1747:
1737:
1717:
928:
819:
598:
550:
38:
1362:
3125:
3024:
2900:
2857:
2766:
2708:
2693:
2683:
2468:
2267:
2151:
2070:
2010:
1942:
1932:
1871:
1846:
1722:
1679:
1674:
1502:
1462:
1382:
1235:
1187:
1145:
1046:
944:
496:
318:
118:
915:
610:
931:, for example, specify string patterns in many contexts, from office productivity software to
3145:
3075:
3054:
3016:
2824:
2791:
2771:
2463:
2375:
2249:
1866:
1851:
1795:
1742:
1540:
1510:
1488:
1470:
1445:
1437:
1409:
1394:
1372:
1348:
1326:
1307:
1296:
1261:
1125:
1105:
1095:
1071:
1022:
987:
959:
692:
668:
660:
553:
as problems become large. So in our previous example, we might say that the problem requires
485:
459:
165:
58:
is the branch that deals with what problems can be solved on a model of computation, using an
998:
central areas of the theory of computation: automata, computability, and complexity. (Page 1)
2978:
2862:
2829:
2624:
2546:
2435:
2421:
2416:
2365:
2352:
2277:
2230:
2080:
2055:
1927:
1775:
1712:
1318:
1225:
1179:
1137:
1042:
908:
888:
782:
586:
500:
169:
130:
517:
3049:
2943:
2915:
2809:
2761:
2746:
2731:
2586:
2581:
2521:
2411:
2385:
2337:
2282:
2020:
1947:
1876:
1669:
1480:
955:
753:
724:
647:
594:
590:
556:
477:
441:
428:
355:
190:
75:
71:
3155:
3059:
2958:
2804:
2776:
2098:
2025:
1732:
1340:
979:
654:
636:
546:
220:
173:
161:
134:
97:
1434:
Computability, complexity, and languages: fundamentals of theoretical computer science
3223:
3044:
2332:
1886:
1818:
1770:
1292:
1091:
1064:
1010:
920:
153:
149:
1149:
17:
3140:
2799:
1828:
1823:
1727:
1048:
Turing, Church, Gödel, Computability, Complexity and
Randomization: A Personal View
618:
614:
427:
something is doing something by itself. Automata theory is also closely related to
1191:
3130:
2756:
2668:
2030:
1694:
1617:
1163:
446:
157:
145:
138:
51:
1444:. Covers a wider range of topics than most other introductory books, including
1288:(There are many textbooks in this area; this list is by necessity incomplete.)
1183:
1167:
488:, which states that for all non-trivial properties of partial functions, it is
3150:
3080:
2673:
2406:
2262:
2015:
1894:
1689:
1141:
685:-calculus, but also important differences exist (e.g. fixed point combinator
2655:
2616:
533:
59:
1582:- A theory of interactive computation. The main web source on this subject.
1579:
1585:
2716:
1919:
1838:
1765:
492:
whether a Turing machine computes a partial function with that property.
96:. There are several models in use, but the most commonly examined is the
1517:. A shorter textbook suitable for graduate students in Computer Science.
1168:"On computable numbers, with an application to the Entscheidungsproblem"
1704:
1574:
1457:
Books on computability theory from the (wider) mathematical perspective
1239:
898:
70:
versus precise ones). The field is divided into three major branches:
935:. Another formalism mathematically equivalent to regular expressions,
88:"What are the fundamental capabilities and limitations of computers?".
589:
is the question of whether a certain broad class of problems denoted
1230:
1214:"Classes of Recursively Enumerable Sets and Their Decision Problems"
1213:
2199:
1101:
Introduction to
Automata Theory, Languages, and Computation. 3rd ed
516:
445:
939:
are used in circuit design and in some kinds of problem-solving.
2203:
1589:
1570:
298:{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
1561:
1302:
Introduction to
Automata Theory, Languages, and Computation
947:
are another formalism equivalent to context-free grammars.
545:
To simplify this problem, computer scientists have adopted
1467:
Theory of
Recursive Functions and Effective Computability
521:
A representation of the relation among complexity classes
495:
Computability theory is closely related to the branch of
1128:(1956). "Three models for the description of language".
943:
specify programming language syntax. Non-deterministic
593:
can be solved efficiently. This is discussed further at
133:(established in 1981 as the Rolf Nevanlinna Prize), the
1507:
A recursive introduction to the theory of computation
832:
785:
756:
727:
695:
671:
559:
398:
370:
328:
273:
230:
532:
In order to analyze how much time and space a given
3068:
3015:
2977:
2924:
2886:
2848:
2790:
2707:
2653:
2615:
2560:
2497:
2430:
2394:
2351:
2315:
2248:
2089:
2046:
1956:
1918:
1885:
1837:
1809:
1756:
1703:
1660:
951:are a defined subclass of the recursive functions.
717:a computation consists of a mu-recursive function,
484:Another important step in computability theory was
1063:
958:that the model can generate; in such a way to the
877:
806:
771:
742:
701:
677:
585:Perhaps the most important open problem in all of
574:
413:
382:
340:
297:
242:
1218:Transactions of the American Mathematical Society
450:Set inclusions described by the Chomsky hierarchy
689:has normal form in combinatory logic but not in
144:Some pioneers of the theory of computation were
1323:An introduction to formal language and automata
264:Linear-bounded non-deterministic Turing machine
1172:Proceedings of the London Mathematical Society
2239:Note: This template roughly follows the 2012
2215:
1601:
1224:(2). American Mathematical Society: 358–366.
984:Introduction to the Theory of Computation 3rd
8:
1368:An Introduction to the Theory of Computation
1314:One of the standard references in the field.
665:is a concept which has many similarities to
66:they can be solved or to what degree (e.g.,
1406:Models of Computation and Formal Languages.
2222:
2208:
2200:
1608:
1594:
1586:
1422:Essentials of theoretical computer science
1345:Introduction to the Theory of Computation
1229:
831:
784:
755:
726:
694:
670:
558:
397:
369:
327:
272:
243:{\displaystyle \alpha \rightarrow \beta }
229:
194:
129:in 1969, and its own awards such as the
1130:Information Theory, IRE Transactions on
971:
2939:Knowledge representation and reasoning
1284:Textbooks aimed at computer scientists
529:required to perform that computation.
2964:Philosophy of artificial intelligence
27:Academic subfield of computer science
7:
2283:Energy consumption (Green computing)
2170:
1408:New York: Oxford University Press.
1393:Sudbury, MA: Jones & Bartlett.
643:) models of computation are in use.
341:{\displaystyle A\rightarrow \gamma }
86:, which are linked by the question:
2969:Distributed artificial intelligence
2241:ACM Computing Classification System
2182:
2474:Integrated development environment
1347:(3rd ed.). Cengage Learning.
25:
2949:Automated planning and scheduling
2479:Software configuration management
1436:, 2nd ed., Academic Press, 1994,
3203:
3193:
3184:
3183:
2181:
2169:
2158:
2157:
2145:
1432:, Ron Sigal, Elaine J. Weyuker,
923:foundations of these techniques.
3194:
2597:Computational complexity theory
2066:Computational complexity theory
1104:. Reading, MA: Addison-Wesley.
513:Computational complexity theory
507:Computational complexity theory
414:{\displaystyle A\rightarrow aB}
207:Production rules (constraints)
137:, established in 1993, and the
84:computational complexity theory
2381:Network performance evaluation
1539:. Wadsworth/Thomson Learning.
878:{\displaystyle f(x)=h(x,g(x))}
872:
869:
863:
851:
842:
836:
801:
789:
766:
760:
737:
731:
569:
563:
402:
383:{\displaystyle A\rightarrow a}
374:
332:
283:
234:
1:
2752:Multimedia information system
2737:Geographic information system
2727:Enterprise information system
2316:Computer systems organization
1452:. Aimed at graduate students.
1306:Reading, MA: Addison-Wesley.
949:Primitive recursive functions
3111:Computational social science
2699:Theoretical computer science
2512:Software development process
2288:Electronic design automation
2273:Very Large Scale Integration
611:Official Problem Description
48:theoretical computer science
32:Computational theory of mind
2934:Natural language processing
2722:Information storage systems
1404:Taylor, R. Gregory (1998).
595:Complexity classes P and NP
3246:
2850:Human–computer interaction
2820:Intrusion detection system
2732:Social information systems
2717:Database management system
2116:Films about mathematicians
1371:. Computer Science Press.
1212:Henry Gordon Rice (1953).
1019:Princeton University Press
1017:(The Centenary ed.).
962:of languages is obtained.
901:-like rules to operate on
628:
607:Clay Mathematics Institute
510:
469:
439:
188:
36:
29:
3179:
3116:Computational engineering
3091:Computational mathematics
2237:
2139:
1685:Philosophy of mathematics
1625:
639:, other equivalent (See:
603:Millennium Prize Problems
3126:Computational healthcare
3121:Differentiable computing
3040:Graphics processing unit
2459:Domain-specific language
2328:Computational complexity
2121:Recreational mathematics
1487:. Chapman and Hall/CRC.
1184:10.1112/plms/s2-42.1.230
1142:10.1109/TIT.1956.1056813
702:{\displaystyle \lambda }
678:{\displaystyle \lambda }
30:Not to be confused with
3101:Computational chemistry
3035:Photograph manipulation
2926:Artificial intelligence
2742:Decision support system
2006:Mathematical statistics
1996:Mathematical psychology
1966:Engineering mathematics
1900:Algebraic number theory
1015:Alan Turing: The Enigma
895:string rewriting system
141:, established in 1996.
3166:Educational technology
2997:Reinforcement learning
2747:Process control system
2645:Computational geometry
2635:Algorithmic efficiency
2630:Analysis of algorithms
2278:Systems on Chip (SoCs)
2152:Mathematics portal
2001:Mathematical sociology
1981:Mathematical economics
1976:Mathematical chemistry
1905:Analytic number theory
1786:Differential equations
1522:Historical perspective
1391:Theory of Computation.
1389:Hein, James L. (1996)
1260:. Dover Publications.
879:
808:
807:{\displaystyle h(x,y)}
773:
744:
703:
679:
576:
522:
451:
436:Formal Language theory
415:
384:
361:Finite state automaton
342:
299:
244:
216:Recursively enumerable
3230:Theory of computation
3136:Electronic publishing
3106:Computational biology
3096:Computational physics
2992:Unsupervised learning
2906:Distributed computing
2782:Information retrieval
2689:Mathematical analysis
2679:Mathematical software
2562:Theory of computation
2527:Software construction
2517:Requirements analysis
2395:Software organization
2323:Computer architecture
2293:Hardware acceleration
2258:Printed circuit board
2131:Mathematics education
2061:Theory of computation
1781:Hypercomplex analysis
1571:Theory of Computation
1562:Theory of Computation
1450:quantification theory
1419:Lewis, F. D. (2007).
1325:. Narosa Publishing.
1178:(42). IEEE: 230–265.
941:Context-free grammars
933:programming languages
880:
809:
774:
745:
713:ÎĽ-recursive functions
704:
680:
625:Models of computation
577:
520:
449:
416:
385:
343:
300:
245:
119:mathematics and logic
68:approximate solutions
56:theory of computation
37:For the journal, see
2896:Concurrent computing
2868:Ubiquitous computing
2840:Application security
2835:Information security
2664:Discrete mathematics
2640:Randomized algorithm
2592:Computability theory
2570:Model of computation
2542:Software maintenance
2537:Software engineering
2499:Software development
2449:Programming language
2444:Programming paradigm
2361:Network architecture
2111:Informal mathematics
1991:Mathematical physics
1986:Mathematical finance
1971:Mathematical biology
1910:Diophantine geometry
1485:Computability Theory
1136:(3). IEEE: 113–124.
1062:Donald Monk (1976).
986:. Cengage Learning.
830:
783:
772:{\displaystyle g(x)}
754:
743:{\displaystyle f(x)}
725:
693:
669:
641:Church–Turing thesis
631:Model of computation
601:is one of the seven
575:{\displaystyle O(n)}
557:
472:Computability theory
466:Computability theory
396:
368:
326:
271:
228:
102:Church–Turing thesis
94:model of computation
80:computability theory
18:Theory of algorithms
3171:Document management
3161:Operations research
3086:Enterprise software
3002:Multi-task learning
2987:Supervised learning
2709:Information systems
2532:Software deployment
2489:Software repository
2343:Real-time computing
2126:Mathematics and art
2036:Operations research
1791:Functional analysis
1580:Computability Logic
1533:Walter A. Carnielli
1070:. Springer-Verlag.
929:Regular expressions
826:. For instance if
820:primitive recursion
599:P versus NP problem
551:asymptotic behavior
40:Theory of Computing
2954:Search methodology
2901:Parallel computing
2858:Interaction design
2767:Computing platform
2694:Numerical analysis
2684:Information theory
2469:Software framework
2432:Software notations
2371:Network components
2268:Integrated circuit
2071:Numerical analysis
1680:Mathematical logic
1675:Information theory
1529:Richard L. Epstein
1509:, Springer, 1994,
1463:Hartley Rogers, Jr
1066:Mathematical Logic
921:number theoretical
875:
804:
769:
740:
699:
675:
572:
523:
497:mathematical logic
452:
411:
380:
338:
319:pushdown automaton
317:Non-deterministic
295:
250:(no restrictions)
240:
3217:
3216:
3146:Electronic voting
3076:Quantum Computing
3069:Applied computing
3055:Image compression
2825:Hardware security
2815:Security services
2772:Digital marketing
2552:Open-source model
2464:Modeling language
2376:Network scheduler
2197:
2196:
1796:Harmonic analysis
1446:program semantics
1414:978-0-19-510983-2
1399:978-0-86720-497-1
1354:978-1-133-18779-0
1312:978-0-321-45536-9
1297:Jeffrey D. Ullman
1293:Hopcroft, John E.
1126:Chomsky hierarchy
1111:978-0-321-45536-9
1096:Jeffrey D. Ullman
1092:Hopcroft, John E.
1043:Rabin, Michael O.
1028:978-0-691-15564-7
993:978-1-133-18779-0
960:Chomsky hierarchy
945:pushdown automata
661:Combinatory logic
526:Complexity theory
460:Chomsky hierarchy
424:
423:
259:Context-sensitive
16:(Redirected from
3237:
3207:
3206:
3197:
3196:
3187:
3186:
3007:Cross-validation
2979:Machine learning
2863:Social computing
2830:Network security
2625:Algorithm design
2547:Programming team
2507:Control variable
2484:Software library
2422:Software quality
2417:Operating system
2366:Network protocol
2231:Computer science
2224:
2217:
2210:
2201:
2185:
2184:
2173:
2172:
2161:
2160:
2150:
2149:
2081:Computer algebra
2056:Computer science
1776:Complex analysis
1610:
1603:
1596:
1587:
1550:
1498:
1386:
1381:. Archived from
1358:
1336:
1272:
1271:
1250:
1244:
1243:
1233:
1209:
1203:
1202:
1200:
1198:
1160:
1154:
1153:
1122:
1116:
1115:
1088:
1082:
1081:
1069:
1059:
1053:
1052:
1039:
1033:
1032:
1007:
1001:
1000:
976:
956:formal languages
909:Register machine
889:Markov algorithm
884:
882:
881:
876:
813:
811:
810:
805:
778:
776:
775:
770:
749:
747:
746:
741:
708:
706:
705:
700:
684:
682:
681:
676:
587:computer science
582:steps to solve.
581:
579:
578:
573:
501:recursion theory
420:
418:
417:
412:
389:
387:
386:
381:
347:
345:
344:
339:
304:
302:
301:
296:
249:
247:
246:
241:
195:
170:John von Neumann
131:IMU Abacus Medal
76:formal languages
21:
3245:
3244:
3240:
3239:
3238:
3236:
3235:
3234:
3220:
3219:
3218:
3213:
3204:
3175:
3156:Word processing
3064:
3050:Virtual reality
3011:
2973:
2944:Computer vision
2920:
2916:Multiprocessing
2882:
2844:
2810:Security hacker
2786:
2762:Digital library
2703:
2654:Mathematics of
2649:
2611:
2587:Automata theory
2582:Formal language
2556:
2522:Software design
2493:
2426:
2412:Virtual machine
2390:
2386:Network service
2347:
2338:Embedded system
2311:
2244:
2233:
2228:
2198:
2193:
2144:
2135:
2085:
2042:
2021:Systems science
1952:
1948:Homotopy theory
1914:
1881:
1833:
1805:
1752:
1699:
1670:Category theory
1656:
1621:
1614:
1558:
1547:
1527:
1495:
1481:S. Barry Cooper
1479:
1379:
1361:
1355:
1339:
1333:
1317:
1281:
1279:Further reading
1276:
1275:
1268:
1252:
1251:
1247:
1231:10.2307/1990888
1211:
1210:
1206:
1196:
1194:
1162:
1161:
1157:
1124:
1123:
1119:
1112:
1090:
1089:
1085:
1078:
1061:
1060:
1056:
1041:
1040:
1036:
1029:
1009:
1008:
1004:
994:
978:
977:
973:
968:
937:Finite automata
916:Gödel numbering
828:
827:
781:
780:
752:
751:
723:
722:
691:
690:
667:
666:
648:Lambda calculus
633:
627:
555:
554:
515:
509:
478:halting problem
474:
468:
444:
442:Formal language
438:
432:computability.
429:formal language
394:
393:
392:
390:
366:
365:
324:
323:
269:
268:
226:
225:
193:
191:Automata theory
187:
185:Automata theory
182:
115:
72:automata theory
44:
35:
28:
23:
22:
15:
12:
11:
5:
3243:
3241:
3233:
3232:
3222:
3221:
3215:
3214:
3212:
3211:
3201:
3191:
3180:
3177:
3176:
3174:
3173:
3168:
3163:
3158:
3153:
3148:
3143:
3138:
3133:
3128:
3123:
3118:
3113:
3108:
3103:
3098:
3093:
3088:
3083:
3078:
3072:
3070:
3066:
3065:
3063:
3062:
3060:Solid modeling
3057:
3052:
3047:
3042:
3037:
3032:
3027:
3021:
3019:
3013:
3012:
3010:
3009:
3004:
2999:
2994:
2989:
2983:
2981:
2975:
2974:
2972:
2971:
2966:
2961:
2959:Control method
2956:
2951:
2946:
2941:
2936:
2930:
2928:
2922:
2921:
2919:
2918:
2913:
2911:Multithreading
2908:
2903:
2898:
2892:
2890:
2884:
2883:
2881:
2880:
2875:
2870:
2865:
2860:
2854:
2852:
2846:
2845:
2843:
2842:
2837:
2832:
2827:
2822:
2817:
2812:
2807:
2805:Formal methods
2802:
2796:
2794:
2788:
2787:
2785:
2784:
2779:
2777:World Wide Web
2774:
2769:
2764:
2759:
2754:
2749:
2744:
2739:
2734:
2729:
2724:
2719:
2713:
2711:
2705:
2704:
2702:
2701:
2696:
2691:
2686:
2681:
2676:
2671:
2666:
2660:
2658:
2651:
2650:
2648:
2647:
2642:
2637:
2632:
2627:
2621:
2619:
2613:
2612:
2610:
2609:
2604:
2599:
2594:
2589:
2584:
2579:
2578:
2577:
2566:
2564:
2558:
2557:
2555:
2554:
2549:
2544:
2539:
2534:
2529:
2524:
2519:
2514:
2509:
2503:
2501:
2495:
2494:
2492:
2491:
2486:
2481:
2476:
2471:
2466:
2461:
2456:
2451:
2446:
2440:
2438:
2428:
2427:
2425:
2424:
2419:
2414:
2409:
2404:
2398:
2396:
2392:
2391:
2389:
2388:
2383:
2378:
2373:
2368:
2363:
2357:
2355:
2349:
2348:
2346:
2345:
2340:
2335:
2330:
2325:
2319:
2317:
2313:
2312:
2310:
2309:
2300:
2295:
2290:
2285:
2280:
2275:
2270:
2265:
2260:
2254:
2252:
2246:
2245:
2238:
2235:
2234:
2229:
2227:
2226:
2219:
2212:
2204:
2195:
2194:
2192:
2191:
2179:
2167:
2155:
2140:
2137:
2136:
2134:
2133:
2128:
2123:
2118:
2113:
2108:
2107:
2106:
2099:Mathematicians
2095:
2093:
2091:Related topics
2087:
2086:
2084:
2083:
2078:
2073:
2068:
2063:
2058:
2052:
2050:
2044:
2043:
2041:
2040:
2039:
2038:
2033:
2028:
2026:Control theory
2018:
2013:
2008:
2003:
1998:
1993:
1988:
1983:
1978:
1973:
1968:
1962:
1960:
1954:
1953:
1951:
1950:
1945:
1940:
1935:
1930:
1924:
1922:
1916:
1915:
1913:
1912:
1907:
1902:
1897:
1891:
1889:
1883:
1882:
1880:
1879:
1874:
1869:
1864:
1859:
1854:
1849:
1843:
1841:
1835:
1834:
1832:
1831:
1826:
1821:
1815:
1813:
1807:
1806:
1804:
1803:
1801:Measure theory
1798:
1793:
1788:
1783:
1778:
1773:
1768:
1762:
1760:
1754:
1753:
1751:
1750:
1745:
1740:
1735:
1730:
1725:
1720:
1715:
1709:
1707:
1701:
1700:
1698:
1697:
1692:
1687:
1682:
1677:
1672:
1666:
1664:
1658:
1657:
1655:
1654:
1649:
1644:
1643:
1642:
1637:
1626:
1623:
1622:
1615:
1613:
1612:
1605:
1598:
1590:
1584:
1583:
1577:
1568:
1557:
1556:External links
1554:
1553:
1552:
1545:
1524:
1523:
1519:
1518:
1500:
1493:
1477:
1459:
1458:
1454:
1453:
1427:
1417:
1402:
1387:
1385:on 2007-01-07.
1377:
1359:
1353:
1341:Michael Sipser
1337:
1331:
1315:
1286:
1285:
1280:
1277:
1274:
1273:
1267:978-0486432281
1266:
1245:
1204:
1155:
1117:
1110:
1083:
1076:
1054:
1034:
1027:
1011:Hodges, Andrew
1002:
992:
980:Michael Sipser
970:
969:
967:
964:
925:
924:
911:
906:
891:
886:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
803:
800:
797:
794:
791:
788:
768:
765:
762:
759:
750:the functions
739:
736:
733:
730:
715:
710:
698:
674:
663:
658:
655:Beta reduction
650:
637:Turing machine
629:Main article:
626:
623:
605:stated by the
571:
568:
565:
562:
547:Big O notation
511:Main article:
508:
505:
486:Rice's theorem
470:Main article:
467:
464:
440:Main article:
437:
434:
422:
421:
410:
407:
404:
401:
379:
376:
373:
363:
358:
353:
349:
348:
337:
334:
331:
321:
315:
310:
306:
305:
294:
291:
288:
285:
282:
279:
276:
266:
261:
256:
252:
251:
239:
236:
233:
223:
221:Turing machine
218:
213:
209:
208:
205:
202:
199:
189:Main article:
186:
183:
181:
178:
174:Claude Shannon
162:Stephen Kleene
114:
111:
98:Turing machine
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3242:
3231:
3228:
3227:
3225:
3210:
3202:
3200:
3192:
3190:
3182:
3181:
3178:
3172:
3169:
3167:
3164:
3162:
3159:
3157:
3154:
3152:
3149:
3147:
3144:
3142:
3139:
3137:
3134:
3132:
3129:
3127:
3124:
3122:
3119:
3117:
3114:
3112:
3109:
3107:
3104:
3102:
3099:
3097:
3094:
3092:
3089:
3087:
3084:
3082:
3079:
3077:
3074:
3073:
3071:
3067:
3061:
3058:
3056:
3053:
3051:
3048:
3046:
3045:Mixed reality
3043:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3022:
3020:
3018:
3014:
3008:
3005:
3003:
3000:
2998:
2995:
2993:
2990:
2988:
2985:
2984:
2982:
2980:
2976:
2970:
2967:
2965:
2962:
2960:
2957:
2955:
2952:
2950:
2947:
2945:
2942:
2940:
2937:
2935:
2932:
2931:
2929:
2927:
2923:
2917:
2914:
2912:
2909:
2907:
2904:
2902:
2899:
2897:
2894:
2893:
2891:
2889:
2885:
2879:
2878:Accessibility
2876:
2874:
2873:Visualization
2871:
2869:
2866:
2864:
2861:
2859:
2856:
2855:
2853:
2851:
2847:
2841:
2838:
2836:
2833:
2831:
2828:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2806:
2803:
2801:
2798:
2797:
2795:
2793:
2789:
2783:
2780:
2778:
2775:
2773:
2770:
2768:
2765:
2763:
2760:
2758:
2755:
2753:
2750:
2748:
2745:
2743:
2740:
2738:
2735:
2733:
2730:
2728:
2725:
2723:
2720:
2718:
2715:
2714:
2712:
2710:
2706:
2700:
2697:
2695:
2692:
2690:
2687:
2685:
2682:
2680:
2677:
2675:
2672:
2670:
2667:
2665:
2662:
2661:
2659:
2657:
2652:
2646:
2643:
2641:
2638:
2636:
2633:
2631:
2628:
2626:
2623:
2622:
2620:
2618:
2614:
2608:
2605:
2603:
2600:
2598:
2595:
2593:
2590:
2588:
2585:
2583:
2580:
2576:
2573:
2572:
2571:
2568:
2567:
2565:
2563:
2559:
2553:
2550:
2548:
2545:
2543:
2540:
2538:
2535:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2504:
2502:
2500:
2496:
2490:
2487:
2485:
2482:
2480:
2477:
2475:
2472:
2470:
2467:
2465:
2462:
2460:
2457:
2455:
2452:
2450:
2447:
2445:
2442:
2441:
2439:
2437:
2433:
2429:
2423:
2420:
2418:
2415:
2413:
2410:
2408:
2405:
2403:
2400:
2399:
2397:
2393:
2387:
2384:
2382:
2379:
2377:
2374:
2372:
2369:
2367:
2364:
2362:
2359:
2358:
2356:
2354:
2350:
2344:
2341:
2339:
2336:
2334:
2333:Dependability
2331:
2329:
2326:
2324:
2321:
2320:
2318:
2314:
2308:
2304:
2301:
2299:
2296:
2294:
2291:
2289:
2286:
2284:
2281:
2279:
2276:
2274:
2271:
2269:
2266:
2264:
2261:
2259:
2256:
2255:
2253:
2251:
2247:
2242:
2236:
2232:
2225:
2220:
2218:
2213:
2211:
2206:
2205:
2202:
2190:
2189:
2180:
2178:
2177:
2168:
2166:
2165:
2156:
2154:
2153:
2148:
2142:
2141:
2138:
2132:
2129:
2127:
2124:
2122:
2119:
2117:
2114:
2112:
2109:
2105:
2102:
2101:
2100:
2097:
2096:
2094:
2092:
2088:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2062:
2059:
2057:
2054:
2053:
2051:
2049:
2048:Computational
2045:
2037:
2034:
2032:
2029:
2027:
2024:
2023:
2022:
2019:
2017:
2014:
2012:
2009:
2007:
2004:
2002:
1999:
1997:
1994:
1992:
1989:
1987:
1984:
1982:
1979:
1977:
1974:
1972:
1969:
1967:
1964:
1963:
1961:
1959:
1955:
1949:
1946:
1944:
1941:
1939:
1936:
1934:
1931:
1929:
1926:
1925:
1923:
1921:
1917:
1911:
1908:
1906:
1903:
1901:
1898:
1896:
1893:
1892:
1890:
1888:
1887:Number theory
1884:
1878:
1875:
1873:
1870:
1868:
1865:
1863:
1860:
1858:
1855:
1853:
1850:
1848:
1845:
1844:
1842:
1840:
1836:
1830:
1827:
1825:
1822:
1820:
1819:Combinatorics
1817:
1816:
1814:
1812:
1808:
1802:
1799:
1797:
1794:
1792:
1789:
1787:
1784:
1782:
1779:
1777:
1774:
1772:
1771:Real analysis
1769:
1767:
1764:
1763:
1761:
1759:
1755:
1749:
1746:
1744:
1741:
1739:
1736:
1734:
1731:
1729:
1726:
1724:
1721:
1719:
1716:
1714:
1711:
1710:
1708:
1706:
1702:
1696:
1693:
1691:
1688:
1686:
1683:
1681:
1678:
1676:
1673:
1671:
1668:
1667:
1665:
1663:
1659:
1653:
1650:
1648:
1645:
1641:
1638:
1636:
1633:
1632:
1631:
1628:
1627:
1624:
1619:
1611:
1606:
1604:
1599:
1597:
1592:
1591:
1588:
1581:
1578:
1576:
1572:
1569:
1567:
1563:
1560:
1559:
1555:
1548:
1546:0-534-54644-7
1542:
1538:
1534:
1530:
1526:
1525:
1521:
1520:
1516:
1515:0-387-94332-3
1512:
1508:
1504:
1503:Carl H. Smith
1501:
1496:
1494:1-58488-237-9
1490:
1486:
1482:
1478:
1476:
1475:0-262-68052-1
1472:
1469:, MIT Press.
1468:
1464:
1461:
1460:
1456:
1455:
1451:
1447:
1443:
1442:0-12-206382-1
1439:
1435:
1431:
1428:
1424:
1423:
1418:
1415:
1411:
1407:
1403:
1400:
1396:
1392:
1388:
1384:
1380:
1378:0-7167-8182-4
1374:
1370:
1369:
1364:
1360:
1356:
1350:
1346:
1342:
1338:
1334:
1332:9788173197819
1328:
1324:
1320:
1316:
1313:
1309:
1305:
1303:
1298:
1294:
1291:
1290:
1289:
1283:
1282:
1278:
1269:
1263:
1259:
1255:
1249:
1246:
1241:
1237:
1232:
1227:
1223:
1219:
1215:
1208:
1205:
1193:
1189:
1185:
1181:
1177:
1173:
1169:
1165:
1159:
1156:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1121:
1118:
1113:
1107:
1103:
1102:
1097:
1093:
1087:
1084:
1079:
1077:9780387901701
1073:
1068:
1067:
1058:
1055:
1050:
1049:
1045:(June 2012).
1044:
1038:
1035:
1030:
1024:
1020:
1016:
1012:
1006:
1003:
999:
995:
989:
985:
981:
975:
972:
965:
963:
961:
957:
952:
950:
946:
942:
938:
934:
930:
922:
917:
912:
910:
907:
904:
900:
896:
892:
890:
887:
866:
860:
857:
854:
848:
845:
839:
833:
825:
821:
817:
798:
795:
792:
786:
763:
757:
734:
728:
720:
716:
714:
711:
696:
688:
672:
664:
662:
659:
656:
651:
649:
646:
645:
644:
642:
638:
635:Aside from a
632:
624:
622:
620:
616:
613:was given by
612:
609:in 2000. The
608:
604:
600:
596:
592:
588:
583:
566:
560:
552:
548:
543:
540:
535:
530:
527:
519:
514:
506:
504:
502:
498:
493:
491:
487:
482:
479:
473:
465:
463:
461:
457:
448:
443:
435:
433:
430:
408:
405:
399:
377:
371:
364:
362:
359:
357:
354:
351:
350:
335:
329:
322:
320:
316:
314:
311:
308:
307:
292:
289:
286:
280:
277:
274:
267:
265:
262:
260:
257:
254:
253:
237:
231:
224:
222:
219:
217:
214:
211:
210:
206:
203:
200:
197:
196:
192:
184:
179:
177:
175:
171:
167:
163:
159:
155:
151:
150:Alonzo Church
147:
142:
140:
136:
132:
128:
124:
120:
112:
110:
107:
103:
99:
95:
90:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
49:
42:
41:
33:
19:
3141:Cyberwarfare
2800:Cryptography
2561:
2186:
2174:
2162:
2143:
2076:Optimization
2060:
1938:Differential
1862:Differential
1829:Order theory
1824:Graph theory
1728:Group theory
1536:
1506:
1484:
1466:
1433:
1430:Martin Davis
1420:
1405:
1390:
1383:the original
1367:
1363:Eitan Gurari
1344:
1322:
1300:
1287:
1257:
1254:Martin Davis
1248:
1221:
1217:
1207:
1195:. Retrieved
1175:
1171:
1158:
1133:
1129:
1120:
1100:
1086:
1065:
1057:
1047:
1037:
1014:
1005:
997:
983:
974:
953:
926:
718:
686:
634:
619:Stephen Cook
615:Turing Award
584:
544:
538:
531:
524:
494:
483:
475:
453:
425:
313:Context-free
143:
125:in 1960 and
116:
91:
87:
55:
45:
39:
3151:Video games
3131:Digital art
2888:Concurrency
2757:Data mining
2669:Probability
2402:Interpreter
2188:WikiProject
2031:Game theory
2011:Probability
1748:Homological
1738:Multilinear
1718:Commutative
1695:Type theory
1662:Foundations
1618:mathematics
1164:Alan Turing
905:of symbols.
824:ÎĽ recursion
816:composition
490:undecidable
166:RĂłzsa PĂ©ter
158:Alan Turing
146:Ramon Llull
139:Knuth Prize
135:Gödel Prize
64:efficiently
52:mathematics
3209:Glossaries
3081:E-commerce
2674:Statistics
2617:Algorithms
2575:Stochastic
2407:Middleware
2263:Peripheral
2016:Statistics
1895:Arithmetic
1857:Arithmetic
1723:Elementary
1690:Set theory
966:References
897:that uses
204:Automaton
201:Languages
154:Kurt Gödel
3030:Rendering
3025:Animation
2656:computing
2607:Semantics
2298:Processor
1943:Geometric
1933:Algebraic
1872:Euclidean
1847:Algebraic
1743:Universal
1197:6 January
697:λ
673:λ
534:algorithm
403:→
375:→
336:γ
333:→
293:β
290:γ
287:α
284:→
281:β
275:α
238:β
235:→
232:α
106:decidable
60:algorithm
3224:Category
3189:Category
3017:Graphics
2792:Security
2454:Compiler
2353:Networks
2250:Hardware
2164:Category
1920:Topology
1867:Discrete
1852:Analytic
1839:Geometry
1811:Discrete
1766:Calculus
1758:Analysis
1713:Abstract
1652:Glossary
1635:Timeline
1535:(2000).
1483:(2004).
1465:(1987).
1426:results.
1365:(1989).
1343:(2013).
1321:(2007).
1304:. 3rd ed
1299:(2006).
1256:(2004).
1166:(1937).
1150:19519474
1098:(2006).
1013:(2012).
982:(2013).
456:alphabet
198:Grammar
180:Branches
3199:Outline
2176:Commons
1958:Applied
1928:General
1705:Algebra
1630:History
1575:Harvard
1240:1990888
903:strings
899:grammar
617:winner
499:called
356:Regular
352:Type-3
309:Type-2
255:Type-1
212:Type-0
113:History
1877:Finite
1733:Linear
1640:Future
1616:Major
1543:
1513:
1491:
1473:
1440:
1412:
1397:
1375:
1351:
1329:
1319:Linz P
1310:
1295:, and
1264:
1238:
1190:
1148:
1108:
1074:
1025:
990:
597:, and
82:, and
62:, how
54:, the
2602:Logic
2436:tools
2104:lists
1647:Lists
1620:areas
1236:JSTOR
1192:73712
1188:S2CID
1146:S2CID
2434:and
2307:Form
2303:Size
1541:ISBN
1531:and
1511:ISBN
1489:ISBN
1471:ISBN
1448:and
1438:ISBN
1410:ISBN
1395:ISBN
1373:ISBN
1349:ISBN
1327:ISBN
1308:ISBN
1262:ISBN
1199:2015
1106:ISBN
1094:and
1072:ISBN
1023:ISBN
988:ISBN
779:and
719:i.e.
172:and
127:STOC
123:FOCS
74:and
50:and
1573:at
1566:MIT
1564:at
1226:doi
1180:doi
1138:doi
822:or
391:and
46:In
3226::
2305:/
1505:,
1234:.
1222:74
1220:.
1216:.
1186:.
1174:.
1170:.
1144:.
1132:.
1021:.
996:.
893:a
818:,
621:.
591:NP
176:.
168:,
164:,
160:,
156:,
152:,
148:,
78:,
2243:.
2223:e
2216:t
2209:v
1609:e
1602:t
1595:v
1551:.
1549:.
1499:.
1497:.
1357:.
1335:.
1270:.
1242:.
1228::
1201:.
1182::
1176:2
1152:.
1140::
1134:2
1114:.
1080:.
1051:.
1031:.
873:)
870:)
867:x
864:(
861:g
858:,
855:x
852:(
849:h
846:=
843:)
840:x
837:(
834:f
802:)
799:y
796:,
793:x
790:(
787:h
767:)
764:x
761:(
758:g
738:)
735:x
732:(
729:f
687:Y
657:.
570:)
567:n
564:(
561:O
539:n
409:B
406:a
400:A
378:a
372:A
330:A
278:A
43:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.