1069:. We can further describe Turing machines that will eventually halt and give an answer for any input in a language, but which may run forever for input strings which are not in the language. Such Turing machines could tell us that a given string is in the language, but we may never be sure based on its behavior that a given string is not in a language, since it may run forever in such a case. A language which is accepted by such a Turing machine is called a
1040:. The language consisting of strings with equal numbers of 'a's and 'b's, which we showed was not a regular language, can be decided by a push-down automaton. Also, in general, a push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular. This model of computation is thus strictly more powerful than finite state machines.
566:
defined to be accepting states. An input stream is fed into the machine one character at a time, and the state transitions for the current state are compared to the input stream, and if there is a matching transition the machine may enter a new state. If at the end of the input stream the machine is in an accepting state, then the whole input stream is accepted.
1289:
Imagine a machine where each step of the computation requires half the time of the previous step (and hopefully half the energy of the previous step...). If we normalize to 1/2 time unit the amount of time required for the first step (and to 1/2 energy unit the amount of energy required for the first
1178:
that simulates the operation of this machine, along with simulating directly the execution of the machine given in the input as well, by interleaving the execution of the two programs. Since the direct simulation will eventually halt if the program it is simulating halts, and since by assumption the
1078:
The Turing machine, it turns out, is an exceedingly powerful model of automata. Attempts to amend the definition of a Turing machine to produce a more powerful machine have surprisingly met with failure. For example, adding an extra tape to the Turing machine, giving it a two-dimensional (or three-
1451:
Even these machines, which seemingly represent the limit of automata that we could imagine, run into their own limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. For example, an Oracle machine cannot answer
565:
Also called a finite-state machine. All real computing devices in existence today can be modeled as a finite-state machine, as all real computers operate on finite resources. Such a machine has a set of states, and a set of state transitions which are affected by the input stream. Certain states are
489:
Also similar to the finite state machine, except that the input is provided on an execution "tape", which the Turing machine can read from, write to, or move back and forth past its read/write "head". The tape is allowed to grow to arbitrary size. The Turing machine is capable of performing complex
1438:
So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable problems. For example, the Turing machine may have a "halting oracle" which answers immediately whether a given Turing machine will ever halt on a given input. These machines are a central
1415:
time unit (and 1 energy unit...) to run. This infinite series converges to 1, which means that this Zeno machine can execute a countably infinite number of steps in 1 time unit (using 1 energy unit...). This machine is capable of deciding the halting problem by directly simulating the execution of
1119:
That is, the only general way to know for sure if a given program will halt on a particular input in all cases is simply to run it and see if it halts. If it does halt, then you know it halts. If it doesn't halt, however, you may never know if it will eventually halt. The language consisting of
507:
Like Turing machines, P′′ uses an infinite tape of symbols (without random access), and a rather minimalistic set of instructions. But these instructions are very different, thus, unlike Turing machines, P′′ does not need to maintain a distinct state, because all “memory-like” functionality can be
471:
A theoretical 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 (and halting).
1062:
Because Turing machines have the ability to "back up" in their input tape, it is possible for a Turing machine to run for a long time in a way that is not possible with the other computation models previously described. It is possible to construct a Turing machine that will never finish running
1141:
The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever when given input which is a representation of a Turing machine that does not itself halt. The halting language is therefore recursively enumerable. It is possible to construct
584:
Similar to the finite state machine, except that it has available an execution stack, which is allowed to grow to arbitrary size. The state transitions additionally specify whether to add a symbol to the stack, or to remove a symbol from the stack. It is more powerful than a DFA due to its
498:
Here, there may be more than one tape; moreover there may be multiple heads per tape. Surprisingly, any computation that can be performed by this sort of machine can also be performed by an ordinary Turing machine, although the latter may be slower or require a larger total region of its
575:
Another simple model of computation, although its processing sequence is not uniquely determined. It can be interpreted as taking multiple paths of computation simultaneously through a finite number of states. However, it is possible to prove that any NFA is reducible to an equivalent
476:
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 appropriate huge natural number — unambiguity of both representation and interpretation can be established by
1410:
615:
An example of such a language is the set of all strings consisting of the letters 'a' and 'b' which contain an equal number of the letter 'a' and 'b'. To see why this language cannot be correctly recognized by a finite state machine, assume first that such a machine
327:
A computation consists of a ÎĽ-recursive function, i.e. 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
512:
incrementation on it. P′′ has also a pair of instructions for a cycle, inspecting the blank symbol. Despite its minimalistic nature, it has become the parental formal language of an implemented and (for entertainment) used programming language called
319:-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).
612:. Because of the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language that is not regular, we must construct a language that would require an infinite number of states.
1111:
Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the tables and asking a Turing machine to answer a question about another Turing machine. It can be shown (See main article:
1100:
The halting problem is one of the most famous problems in computer science, because it has profound implications on the theory of computability and on how we use computers in everyday practice. The problem can be phrased:
1058:
can decide any context-free language, in addition to languages not decidable by a push-down automaton, such as the language consisting of prime numbers. It is therefore a strictly more powerful model of computation.
262:
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
490:
calculations which can have arbitrary duration. This model is perhaps the most important model of computation in computer science, as it simulates computation in the absence of predefined resource limits.
1106:
Given a description of a Turing machine and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.
1120:
all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore called non-computable or
1079:
or any-dimensional) infinite surface to work with can all be simulated by a Turing machine with the basic one-dimensional tape. These models are thus not more powerful. In fact, a consequence of the
1296:
1043:
However, it turns out there are languages that cannot be decided by push-down automaton either. The result is similar to that for regular expressions, and won't be detailed here. There exists a
1233:
is thus a decider for the halting problem. We have previously shown, however, that the halting problem is undecidable. We have a contradiction, and we have thus shown that our assumption that
1153:
which is able to give a definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually halt. We can then construct another Turing machine
1145:
A simple example of such a language is the complement of the halting language; that is the language consisting of all Turing machines paired with input strings where the Turing machines do
1086:
The question to ask then is: do there exist languages which are recursively enumerable, but not recursive? And, furthermore, are there languages which are not even recursively enumerable?
1063:(halt) on some inputs. We say that a Turing machine can decide a language if it eventually will halt on all inputs and give an answer. A language that can be so decided is called a
1012:
We know, therefore, that this language cannot be accepted correctly by any finite-state machine, and is thus not a regular language. A more general form of this result is called the
1269:
conjectures that there is no effective model of computing that can compute more mathematical functions than a Turing machine. Computer scientists have imagined many varieties of
80:, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in
317:
293:
1231:
1206:
1176:
981:
907:
833:
791:
939:
865:
737:
694:
662:
1007:
544:
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
1257:. These models of concurrent computation still do not implement any mathematical functions that cannot be implemented by Turing machines.
1416:
the machine in question. By extension, any convergent infinite series would work. Assuming that the infinite series converges to a value
472:
The lack of the infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its role with
521:
In addition to the general computational models, some simpler computational models are useful for special, restricted applications.
223:
One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation.
439:
must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
379:
might appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries above by using
1044:
380:
1405:{\displaystyle 1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots }
1556:
1083:
is that there is no reasonable model of computation which can decide languages that cannot be decided by a Turing machine.
1149:
halt on their input. To see that this language is not recursively enumerable, imagine that we construct a Turing machine
1013:
1133:, which states that it is undecidable (in general) whether a given language possesses any specific nontrivial property.
1533:
1510:
569:
707:, there must be some state in the machine that is repeated as it reads in the first series of 'a's, since there are
241:
is a formal description of a particular type of computational process. The description often takes the form of an
1476:
1071:
1580:
1250:
1246:
559:
1575:
1016:, which can be used to show that broad classes of languages cannot be recognized by a finite state machine.
1471:
941:'b's, which is not in the language of strings containing an equal number of 'a's and 'b's. In other words,
594:
With these computational models in hand, we can determine what their limits are. That is, what classes of
208:
may take a string and return the string obtained by reversing the digits of the input (so f(0101) = 1010).
759:
to some subsequent occurrence during the 'a' sequence. We know, then, that at that second occurrence of
69:
1237:
exists is incorrect. The complement of the halting language is therefore not recursively enumerable.
456:
1116:) that it is not possible to construct a Turing machine that can answer this question in all cases.
1266:
1080:
493:
250:
945:
cannot correctly distinguish between a string of equal number of 'a's and 'b's and a string with
442:
322:
73:
1521:
525:, for example, specify string patterns in many contexts, from office productivity software to
302:
278:
121:, which may be a set of strings, natural numbers, or other objects taken from some larger set
1030:
948:
874:
800:
460:
388:
102:
54:
29:
770:
585:
infinite-memory stack, although only the top element of the stack is accessible at any time.
45:
is the ability to solve a problem in an effective manner. It is a key topic of the field of
1036:
912:
838:
744:
710:
667:
635:
534:
530:
526:
238:
232:
217:
46:
21:
8:
1481:
1122:
986:
755:
be the number of 'a's that our machine read in order to get from the first occurrence of
384:
245:
that is meant to perform the task at hand. General models of computation equivalent to a
17:
1211:
1186:
1156:
84:, while computability notions stronger than Turing machines are studied in the field of
1065:
1025:
606:
Computer scientists call any language that can be accepted by a finite-state machine a
579:
538:
522:
509:
50:
473:
1552:
1529:
1506:
1499:
1130:
549:
508:
provided only by the tape. Instead of rewriting the current symbol, it can perform a
270:
154:
33:
1466:
1440:
608:
466:
448:
242:
161:
114:
85:
58:
1544:
1461:
1113:
1095:
595:
545:
257:
81:
77:
1494:
1433:
1055:
484:
264:
246:
213:
1569:
1271:
478:
295:-calculus, but also important differences exist (e.g. fixed point combinator
153:
the set of prime numbers. The corresponding decision problem corresponds to
1284:
61:. The computability of a problem is closely linked to the existence of an
1183:
will eventually halt if the input program would never halt, we know that
502:
25:
529:. Another formalism mathematically equivalent to regular expressions,
1254:
514:
62:
1420:, the Zeno machine would complete a countably infinite execution in
533:
are used in circuit design and in some kinds of problem-solving.
452:
1024:
Computer scientists define a language that can be accepted by a
1517:
Part Two: Computability Theory, Chapters 3–6, pp. 123–222.
1452:
the question of whether a given Oracle machine will ever halt.
1142:
languages which are not even recursively enumerable, however.
1047:. An example of such a language is the set of prime numbers.
1275:, models of computation that go beyond Turing computability.
176:. An instance of the problem is to compute, given an element
541:
are another formalism equivalent to context-free grammars.
1136:
1208:
will eventually have one of its parallel versions halt.
537:
specify programming language syntax. Non-deterministic
68:
The most widely studied models of computability are the
106:, which is a task whose computability can be explored.
1520:
1299:
1214:
1189:
1159:
989:
951:
915:
877:
841:
803:
773:
713:
670:
638:
305:
281:
835:'a's must end up in the same state as the string of
1498:
1404:
1225:
1200:
1170:
1001:
975:
933:
901:
859:
827:
785:
731:
688:
656:
311:
287:
1260:
601:
204:may be the set of all finite binary strings, and
39:Ability to solve a problem in an effective manner
16:"Computable" redirects here. For other uses, see
1567:
867:'a's. This implies that if our machine accepts
555:Other restricted models of computation include:
299:has normal form in combinatory logic but not in
1543:
548:that the model can generate; in such a way the
226:
1493:
1446:
1129:An extension of the halting problem is called
129:of the problem is to decide, given an element
96:A central idea in computability is that of a (
1019:
797:. This means that we know that a string of
1240:
1050:
1245:A number of computational models based on
1540:Chapter 3: Computability, pp. 57–70.
1501:Introduction to the Theory of Computation
275:A concept which has many similarities to
1551:(1st ed.). Chapman & Hall/CRC.
1045:Pumping lemma for context-free languages
1137:Beyond recursively enumerable languages
1568:
1290:step...), the execution would require
1089:
1278:
793:) 'a's and we will be again at state
109:There are two key types of problems:
871:, it must also accept the string of
589:
1249:have been developed, including the
1014:Pumping lemma for regular languages
13:
1427:
1322:
149:be the set of natural numbers and
14:
1592:
570:Nondeterministic finite automaton
1528:(1st ed.). Addison Wesley.
624:must have some number of states
481:foundations of these techniques.
212:Other types of problems include
1477:Computational complexity theory
1072:recursively enumerable language
365:appear, then terms of the form
1261:Stronger models of computation
1251:parallel random-access machine
1034:, which can be specified as a
970:
952:
928:
916:
896:
878:
854:
842:
822:
804:
763:, we can add in an additional
726:
714:
683:
671:
651:
639:
602:Power of finite-state machines
560:Deterministic finite automaton
1:
1487:
1472:List of undecidable problems
227:Formal models of computation
184:, the corresponding element
7:
1455:
1447:Limits of hyper-computation
628:. Now consider the string
91:
10:
1597:
1431:
1282:
1093:
1020:Power of pushdown automata
552:of languages is obtained.
455:-like rules to operate on
230:
15:
1526:Computational Complexity
1241:Concurrency-based models
1051:Power of Turing machines
494:Multitape Turing machine
443:String rewriting systems
312:{\displaystyle \lambda }
288:{\displaystyle \lambda }
976:{\displaystyle (n+d+1)}
902:{\displaystyle (n+d+1)}
828:{\displaystyle (n+d+1)}
164:consists of a function
1522:Christos Papadimitriou
1406:
1326:
1227:
1202:
1172:
1003:
977:
935:
903:
861:
829:
787:
786:{\displaystyle d>0}
733:
690:
658:
425:to appear, terms like
313:
289:
65:to solve the problem.
1581:Theory of computation
1407:
1306:
1228:
1203:
1173:
1031:Context-free language
1004:
978:
936:
934:{\displaystyle (n+1)}
904:
862:
860:{\displaystyle (n+1)}
830:
788:
734:
732:{\displaystyle (n+1)}
691:
689:{\displaystyle (n+1)}
659:
657:{\displaystyle (n+1)}
535:Context-free grammars
527:programming languages
461:Post canonical system
323:ÎĽ-recursive functions
314:
290:
218:optimization problems
74:ÎĽ-recursive functions
55:theory of computation
30:Theory of computation
1576:Computability theory
1549:Computability Theory
1297:
1267:Church–Turing thesis
1212:
1187:
1157:
1081:Church–Turing thesis
1037:Context-free grammar
987:
949:
913:
875:
839:
801:
771:
745:pigeonhole principle
711:
668:
636:
303:
279:
251:Church–Turing thesis
239:model of computation
233:Model of computation
47:computability theory
22:Computability theory
1482:Computability logic
1090:The halting problem
1002:{\displaystyle n+1}
747:. Call this state
523:Regular expressions
391:. For instance if
385:primitive recursion
145:. For example, let
18:Computable function
1505:. PWS Publishing.
1439:topic of study in
1402:
1279:Infinite execution
1226:{\displaystyle M'}
1223:
1201:{\displaystyle M'}
1198:
1171:{\displaystyle M'}
1168:
1066:recursive language
1026:pushdown automaton
999:
973:
931:
899:
857:
825:
783:
751:, and further let
729:
686:
654:
580:Pushdown automaton
510:modular arithmetic
479:number theoretical
309:
285:
51:mathematical logic
1558:978-1-58488-237-4
1394:
1381:
1368:
1355:
1342:
909:'a's followed by
664:'a's followed by
598:can they accept?
590:Power of automata
550:Chomsky hierarchy
539:pushdown automata
459:of symbols; also
449:Markov algorithms
271:Combinatory logic
155:primality testing
70:Turing-computable
34:Computable number
1588:
1562:
1539:
1516:
1504:
1467:Abstract machine
1441:recursion theory
1411:
1409:
1408:
1403:
1395:
1387:
1382:
1374:
1369:
1361:
1356:
1348:
1343:
1341:
1340:
1328:
1325:
1320:
1232:
1230:
1229:
1224:
1222:
1207:
1205:
1204:
1199:
1197:
1177:
1175:
1174:
1169:
1167:
1008:
1006:
1005:
1000:
982:
980:
979:
974:
940:
938:
937:
932:
908:
906:
905:
900:
866:
864:
863:
858:
834:
832:
831:
826:
792:
790:
789:
784:
738:
736:
735:
730:
695:
693:
692:
687:
663:
661:
660:
655:
609:regular language
546:formal languages
467:Register machine
438:
431:
424:
417:
378:
371:
364:
349:
338:
318:
316:
315:
310:
294:
292:
291:
286:
243:abstract machine
196:. For example,
162:function problem
115:decision problem
86:hypercomputation
59:computer science
1596:
1595:
1591:
1590:
1589:
1587:
1586:
1585:
1566:
1565:
1559:
1545:S. Barry Cooper
1536:
1513:
1490:
1462:Automata theory
1458:
1449:
1436:
1430:
1428:Oracle machines
1386:
1373:
1360:
1347:
1336:
1332:
1327:
1321:
1310:
1298:
1295:
1294:
1287:
1281:
1263:
1243:
1215:
1213:
1210:
1209:
1190:
1188:
1185:
1184:
1160:
1158:
1155:
1154:
1139:
1114:Halting problem
1098:
1096:Halting problem
1092:
1056:Turing machines
1053:
1022:
988:
985:
984:
950:
947:
946:
914:
911:
910:
876:
873:
872:
840:
837:
836:
802:
799:
798:
772:
769:
768:
712:
709:
708:
669:
666:
665:
637:
634:
633:
604:
592:
531:Finite automata
474:Gödel numbering
433:
426:
419:
392:
373:
366:
351:
340:
329:
304:
301:
300:
280:
277:
276:
258:Lambda calculus
235:
229:
214:search problems
125:. A particular
94:
82:automata theory
78:lambda calculus
40:
37:
12:
11:
5:
1594:
1584:
1583:
1578:
1564:
1563:
1557:
1541:
1534:
1518:
1511:
1495:Michael Sipser
1489:
1486:
1485:
1484:
1479:
1474:
1469:
1464:
1457:
1454:
1448:
1445:
1434:Oracle machine
1432:Main article:
1429:
1426:
1413:
1412:
1401:
1398:
1393:
1390:
1385:
1380:
1377:
1372:
1367:
1364:
1359:
1354:
1351:
1346:
1339:
1335:
1331:
1324:
1319:
1316:
1313:
1309:
1305:
1302:
1283:Main article:
1280:
1277:
1272:hypercomputers
1262:
1259:
1242:
1239:
1221:
1218:
1196:
1193:
1179:simulation of
1166:
1163:
1138:
1135:
1131:Rice's theorem
1109:
1108:
1094:Main article:
1091:
1088:
1052:
1049:
1021:
1018:
998:
995:
992:
972:
969:
966:
963:
960:
957:
954:
930:
927:
924:
921:
918:
898:
895:
892:
889:
886:
883:
880:
856:
853:
850:
847:
844:
824:
821:
818:
815:
812:
809:
806:
782:
779:
776:
743:states by the
739:'a's and only
728:
725:
722:
719:
716:
685:
682:
679:
676:
673:
653:
650:
647:
644:
641:
632:consisting of
603:
600:
591:
588:
587:
586:
582:
577:
573:
567:
563:
519:
518:
505:
500:
496:
491:
487:
485:Turing machine
482:
469:
464:
445:
440:
339:the functions
325:
320:
308:
284:
273:
268:
265:beta reduction
260:
247:Turing machine
231:Main article:
228:
225:
210:
209:
158:
93:
90:
38:
9:
6:
4:
3:
2:
1593:
1582:
1579:
1577:
1574:
1573:
1571:
1560:
1554:
1550:
1546:
1542:
1537:
1535:0-201-53082-1
1531:
1527:
1523:
1519:
1514:
1512:0-534-94728-X
1508:
1503:
1502:
1496:
1492:
1491:
1483:
1480:
1478:
1475:
1473:
1470:
1468:
1465:
1463:
1460:
1459:
1453:
1444:
1442:
1435:
1425:
1423:
1419:
1399:
1396:
1391:
1388:
1383:
1378:
1375:
1370:
1365:
1362:
1357:
1352:
1349:
1344:
1337:
1333:
1329:
1317:
1314:
1311:
1307:
1303:
1300:
1293:
1292:
1291:
1286:
1276:
1274:
1273:
1268:
1258:
1256:
1252:
1248:
1238:
1236:
1219:
1216:
1194:
1191:
1182:
1164:
1161:
1152:
1148:
1143:
1134:
1132:
1127:
1125:
1124:
1117:
1115:
1107:
1104:
1103:
1102:
1097:
1087:
1084:
1082:
1076:
1074:
1073:
1068:
1067:
1060:
1057:
1048:
1046:
1041:
1039:
1038:
1033:
1032:
1027:
1017:
1015:
1010:
996:
993:
990:
967:
964:
961:
958:
955:
944:
925:
922:
919:
893:
890:
887:
884:
881:
870:
851:
848:
845:
819:
816:
813:
810:
807:
796:
780:
777:
774:
766:
762:
758:
754:
750:
746:
742:
723:
720:
717:
706:
702:
697:
680:
677:
674:
648:
645:
642:
631:
627:
623:
619:
613:
611:
610:
599:
597:
583:
581:
578:
574:
571:
568:
564:
561:
558:
557:
556:
553:
551:
547:
542:
540:
536:
532:
528:
524:
516:
511:
506:
504:
501:
497:
495:
492:
488:
486:
483:
480:
475:
470:
468:
465:
462:
458:
454:
450:
446:
444:
441:
436:
429:
422:
415:
411:
407:
403:
399:
395:
390:
386:
382:
376:
369:
362:
358:
354:
347:
343:
336:
332:
326:
324:
321:
306:
298:
282:
274:
272:
269:
266:
261:
259:
256:
255:
254:
252:
248:
244:
240:
234:
224:
221:
219:
215:
207:
203:
199:
195:
191:
187:
183:
179:
175:
171:
167:
163:
159:
156:
152:
148:
144:
140:
136:
132:
128:
124:
120:
116:
112:
111:
110:
107:
105:
104:
99:
98:computational
89:
87:
83:
79:
75:
71:
66:
64:
60:
56:
52:
48:
44:
43:Computability
35:
31:
27:
23:
19:
1548:
1525:
1500:
1450:
1437:
1424:time units.
1421:
1417:
1414:
1288:
1285:Zeno machine
1270:
1264:
1244:
1234:
1180:
1150:
1146:
1144:
1140:
1128:
1121:
1118:
1110:
1105:
1099:
1085:
1077:
1070:
1064:
1061:
1054:
1042:
1035:
1029:
1023:
1011:
942:
868:
794:
764:
760:
756:
752:
748:
740:
704:
700:
698:
629:
625:
621:
617:
614:
607:
605:
593:
554:
543:
520:
434:
427:
420:
413:
409:
405:
401:
397:
393:
374:
367:
360:
356:
352:
345:
341:
334:
330:
296:
236:
222:
211:
205:
201:
197:
193:
189:
185:
181:
177:
173:
169:
165:
150:
146:
142:
138:
134:
130:
126:
122:
118:
117:fixes a set
108:
101:
97:
95:
67:
42:
41:
1247:concurrency
1123:undecidable
451:, that use
418:, then for
389:ÎĽ-recursion
381:composition
253:) include:
168:from a set
26:Computation
1570:Categories
1488:References
377:(3,2) = 10
137:, whether
76:, and the
1400:⋯
1323:∞
1308:∑
1255:Petri net
983:'a's and
703:reads in
620:exists.
596:languages
515:Brainfuck
447:Includes
437:(5,6) = 3
307:λ
283:λ
172:to a set
63:algorithm
1547:(2004).
1524:(1993).
1497:(1997).
1456:See also
1253:and the
1220:′
1195:′
1165:′
127:instance
92:Problems
53:and the
767:(where
457:strings
453:grammar
430:(5) = 6
423:(5) = 3
370:(5) = 7
103:problem
57:within
49:within
1555:
1532:
1509:
1009:'b's.
696:'b's.
141:is in
32:, and
1028:as a
572:(NFA)
562:(DFA)
499:tape.
249:(see
192:) in
1553:ISBN
1530:ISBN
1507:ISBN
1265:The
778:>
576:DFA.
432:and
400:) =
350:and
216:and
200:and
72:and
1147:not
699:As
503:P′′
387:or
372:or
180:in
133:of
1572::
1443:.
1392:16
1126:.
1075:.
416:))
383:,
237:A
220:.
160:A
113:A
100:)
88:.
28:,
24:,
20:,
1561:.
1538:.
1515:.
1422:n
1418:n
1397:+
1389:1
1384:+
1379:8
1376:1
1371:+
1366:4
1363:1
1358:+
1353:2
1350:1
1345:=
1338:n
1334:2
1330:1
1318:1
1315:=
1312:n
1304:=
1301:1
1235:M
1217:M
1192:M
1181:M
1162:M
1151:M
997:1
994:+
991:n
971:)
968:1
965:+
962:d
959:+
956:n
953:(
943:M
929:)
926:1
923:+
920:n
917:(
897:)
894:1
891:+
888:d
885:+
882:n
879:(
869:x
855:)
852:1
849:+
846:n
843:(
823:)
820:1
817:+
814:d
811:+
808:n
805:(
795:S
781:0
775:d
765:d
761:S
757:S
753:d
749:S
741:n
727:)
724:1
721:+
718:n
715:(
705:x
701:M
684:)
681:1
678:+
675:n
672:(
652:)
649:1
646:+
643:n
640:(
630:x
626:n
622:M
618:M
517:.
463:.
435:h
428:g
421:f
414:x
412:(
410:g
408:,
406:x
404:(
402:h
398:x
396:(
394:f
375:h
368:g
363:)
361:y
359:,
357:x
355:(
353:h
348:)
346:x
344:(
342:g
337:)
335:x
333:(
331:f
297:Y
267:.
206:f
202:V
198:U
194:V
190:u
188:(
186:f
182:U
178:u
174:V
170:U
166:f
157:.
151:S
147:U
143:S
139:u
135:U
131:u
123:U
119:S
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.