287:
908:
1198:
882:
of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is
325:
How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition. The other is to imagine that
1032:
Intuitively speaking, while a quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch
845:
It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting a string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more
1024:
are NTMs. However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa. In particular, it is likely that
863:
Another construction simulates NTMs with 3-tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree. The 3-tape DTMs are easily simulated with a normal
854:
One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever the transition relation defines multiple
623:
330:" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If at least one branch of the tree halts with an "accept" condition, the NTM accepts the input.
711:
The input for an NTM is provided in the same manner as for a deterministic Turing machine: the machine is started in the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise.
236:
In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal
719:
of the possible computational paths starting from that string puts the machine into an accepting state. When simulating the many branching paths of an NTM on a deterministic machine, we can stop the entire simulation as soon as
735:
The head movement in the output of the transition relation is often encoded numerically instead of using letters to represent moving the head Left (-1), Stationary (0), and Right (+1); giving a transition function output of
887:, the most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time.
800:
398:
1002:
534:
950:
704:
relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the
732:
As a mathematical construction used primarily in proofs, there are a variety of minor variations on the definition of an NTM, but these variations all accept equivalent languages.
499:
527:
471:
443:
245:. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3."
228:, which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer.
205:) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is
1033:
then does not, in general, represent the sought-for solution, unlike the NTM, which is allowed to pick the right solution among the exponentially many branches.
687:
667:
647:
421:
302:) the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to:
268:
the symbol to be written to the tape (it may be the same as the symbol currently in that position, or not even write at all, resulting in no practical change),
708:
relation is no longer single-valued. (If the machine is deterministic, the possible computations are all prefixes of a single, possibly infinite, path.)
1215:
278:
For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5.
17:
825:
Any computational problem that can be solved by a DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the
1262:
1234:
837:
NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM.
1241:
802:. It is common to omit the stationary (0) output, and instead insert the transitive closure of any desired stationary transitions.
739:
1248:
1347:
1230:
618:{\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)}
341:
955:
1331:
1309:
1136:
918:
1281:
1075:
899:
then it halts in a bounded number of steps, and therefore can only have a bounded number of possible configurations.
180:
1092:
1219:
697:
is that, for deterministic Turing machines, the transition relation is a function rather than just a relation.
1255:
1042:
254:
210:
194:
98:
895:
An NTM has the property of bounded nondeterminism. That is, if an NTM always halts on a given input tape
809:
state, which causes the NTM to halt without accepting. This definition still retains the asymmetry that
220:
to examine the abilities and limits of computers. One of the most important open problems in theoretical
478:
286:
123:
108:
73:
47:
128:
118:
113:
103:
506:
1368:
1208:
450:
154:
93:
52:
1354:
C++ Simulator of a
Nondeterministic Multitape Turing Machine download link from sourceforge.net
1319:
1120:
257:(DTM), the set of rules prescribes at most one action to be performed for any given situation.
88:
57:
1017:
428:
78:
879:
173:
8:
873:
225:
1298:
1169:
1125:
1064:
672:
652:
632:
406:
327:
217:
1327:
1305:
1132:
1071:
1021:
1009:
221:
1353:
1020:
of states, rather than conventional bits, there is sometimes a misconception that
884:
826:
264:
that, for a given state and symbol under the tape head, specifies three things:
166:
1155:
1131:(1st ed.). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211.
1116:
1029:
problems are solvable by NTMs but not by quantum computers in polynomial time.
907:
694:
33:
1362:
209:
completely determined by its action and the current symbol it sees, unlike a
1151:
133:
1296:
Martin, John C. (1997). "Section 9.6: Nondeterministic Turing machines".
1026:
1013:
338:
A nondeterministic Turing machine can be formally defined as a six-tuple
271:
the direction (left, right or neither) in which the head should move, and
149:
878:
In the second construction, the constructed DTM effectively performs a
1066:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
883:
believed to be a general property of simulations of NTMs by DTMs. The
1197:
1174:
795:{\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)}
1348:
1004:. If this is not true then the figure should look different.
290:
Comparison of deterministic and nondeterministic computation
1123:(1981). "Section 4.6: Nondeterministic Turing machines".
912:
1300:
Introduction to
Languages and the Theory of Computation
1168:
Tušarová, Tereza (2004). "Quantum complexity classes".
849:
820:
552:
393:{\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}
1061:
997:{\displaystyle {\mathsf {NP}}\neq {\mathsf {PSPACE}}}
958:
921:
742:
675:
655:
635:
537:
509:
481:
453:
431:
409:
344:
902:
294:
In contrast to a deterministic Turing machine, in a
1222:. Unsourced material may be challenged and removed.
1322:(1993). "Section 2.7: Nondeterministic machines".
1297:
1124:
1115:
1063:
996:
944:
867:
817:branch must reject for the string to be rejected.
794:
681:
661:
641:
617:
521:
493:
465:
437:
415:
392:
1360:
1326:(1st ed.). Addison-Wesley. pp. 45–50.
945:{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}
913:solvable by quantum computers in polynomial time
1304:(2nd ed.). McGraw-Hill. pp. 277–281.
832:
693:The difference with a standard (deterministic)
625:is a relation on states and symbols called the
320:
248:
715:An NTM accepts an input string if and only if
445:is a finite set of symbols (the tape alphabet)
1318:
911:The suspected shape of the range of problems
174:
1062:Garey, Michael R.; David S. Johnson (1979).
784:
760:
607:
589:
306:Write a Y, move right, and switch to state 5
316:Write an X, move left, and stay in state 3.
274:the subsequent state of the finite control.
727:
181:
167:
1282:Learn how and when to remove this message
1173:
890:
1167:
1152:The Orion Quantum Computer Anti-Hype FAQ
906:
858:
840:
813:nondeterministic branch can accept, but
285:
14:
1361:
1295:
989:
986:
983:
980:
977:
974:
964:
961:
937:
934:
924:
529:is the set of accepting (final) states
1127:Elements of the Theory of Computation
915:(BQP). Note that the figure suggests
260:A deterministic Turing machine has a
1220:adding citations to reliable sources
1191:
1090:
1084:
850:Multiplicity of configuration states
821:Computational equivalence with DTMs
724:branch reaches an accepting state.
24:
1093:"Nondeterministic Turing Machines"
754:
583:
561:
494:{\displaystyle \sqcup \in \Sigma }
488:
432:
360:
25:
1380:
1341:
1231:"Nondeterministic Turing machine"
1055:
903:Comparison with quantum computers
1196:
27:Theoretical model of computation
18:Non-deterministic Turing machine
1207:needs additional citations for
868:Time complexity and P versus NP
296:nondeterministic Turing machine
199:nondeterministic Turing machine
84:Nondeterministic Turing machine
1161:
1145:
1109:
1098:. U. Illinois Urbana-Champaign
387:
351:
13:
1:
1048:
805:Some authors add an explicit
689:is the movement to the right.
649:is the movement to the left,
333:
243:what symbol it currently sees
231:
1043:Probabilistic Turing machine
833:DTM as a special case of NTM
522:{\displaystyle A\subseteq Q}
321:Resolution of multiple rules
281:
255:deterministic Turing machine
249:Deterministic Turing machine
211:deterministic Turing machine
195:theoretical computer science
99:Probabilistic Turing machine
7:
1036:
466:{\displaystyle \iota \in Q}
216:NTMs are sometimes used in
10:
1385:
1187:
871:
124:Unambiguous Turing machine
109:Multi-track Turing machine
74:Alternating Turing machine
48:Turing machine equivalents
423:is a finite set of states
1324:Computational Complexity
129:Universal Turing machine
114:Symmetric Turing machine
104:Multitape Turing machine
1320:Papadimitriou, Christos
1121:Papadimitriou, Christos
728:Alternative definitions
700:Configurations and the
438:{\displaystyle \Sigma }
155:Category:Turing machine
53:Turing machine examples
1005:
998:
946:
891:Bounded nondeterminism
796:
683:
663:
643:
619:
523:
495:
467:
439:
417:
394:
291:
89:Quantum Turing machine
58:Turing machine gallery
999:
947:
910:
859:Multiplicity of tapes
841:DTM simulation of NTM
829:may not be the same.
797:
684:
664:
644:
620:
524:
496:
468:
440:
418:
395:
289:
79:Neural Turing machine
1216:improve this article
956:
919:
880:breadth-first search
740:
673:
669:is no movement, and
653:
633:
535:
507:
479:
473:is the initial state
451:
429:
407:
342:
119:Total Turing machine
874:P versus NP problem
627:transition relation
501:is the blank symbol
262:transition function
226:P versus NP problem
218:thought experiments
94:Post–Turing machine
1016:, which can be in
1006:
994:
942:
792:
679:
659:
639:
615:
519:
491:
463:
435:
413:
390:
292:
1292:
1291:
1284:
1266:
1070:. W. H. Freeman.
1022:quantum computers
1010:quantum computers
864:single-tape DTM.
682:{\displaystyle R}
662:{\displaystyle S}
642:{\displaystyle L}
416:{\displaystyle Q}
191:
190:
16:(Redirected from
1376:
1350:(free software).
1337:
1315:
1303:
1287:
1280:
1276:
1273:
1267:
1265:
1224:
1200:
1192:
1181:
1179:
1177:
1165:
1159:
1149:
1143:
1142:
1130:
1113:
1107:
1106:
1104:
1103:
1097:
1091:Erickson, Jeff.
1088:
1082:
1081:
1069:
1059:
1003:
1001:
1000:
995:
993:
992:
968:
967:
951:
949:
948:
943:
941:
940:
928:
927:
801:
799:
798:
793:
791:
787:
688:
686:
685:
680:
668:
666:
665:
660:
648:
646:
645:
640:
624:
622:
621:
616:
614:
610:
568:
564:
528:
526:
525:
520:
500:
498:
497:
492:
472:
470:
469:
464:
444:
442:
441:
436:
422:
420:
419:
414:
399:
397:
396:
391:
222:computer science
183:
176:
169:
30:
29:
21:
1384:
1383:
1379:
1378:
1377:
1375:
1374:
1373:
1359:
1358:
1344:
1334:
1312:
1288:
1277:
1271:
1268:
1225:
1223:
1213:
1201:
1190:
1185:
1184:
1166:
1162:
1150:
1146:
1139:
1117:Lewis, Harry R.
1114:
1110:
1101:
1099:
1095:
1089:
1085:
1078:
1060:
1056:
1051:
1039:
973:
972:
960:
959:
957:
954:
953:
933:
932:
923:
922:
920:
917:
916:
905:
893:
876:
870:
861:
855:continuations.
852:
843:
835:
827:time complexity
823:
747:
743:
741:
738:
737:
730:
674:
671:
670:
654:
651:
650:
634:
631:
630:
576:
572:
548:
544:
536:
533:
532:
508:
505:
504:
480:
477:
476:
452:
449:
448:
430:
427:
426:
408:
405:
404:
343:
340:
339:
336:
323:
284:
251:
234:
187:
34:Turing machines
28:
23:
22:
15:
12:
11:
5:
1382:
1372:
1371:
1369:Turing machine
1357:
1356:
1351:
1343:
1342:External links
1340:
1339:
1338:
1333:978-0201530827
1332:
1316:
1311:978-0073191461
1310:
1290:
1289:
1204:
1202:
1195:
1189:
1186:
1183:
1182:
1160:
1156:Scott Aaronson
1144:
1138:978-0132624787
1137:
1108:
1083:
1076:
1053:
1052:
1050:
1047:
1046:
1045:
1038:
1035:
1018:superpositions
991:
988:
985:
982:
979:
976:
971:
966:
963:
939:
936:
931:
926:
904:
901:
892:
889:
885:P = NP problem
872:Main article:
869:
866:
860:
857:
851:
848:
846:than one way.
842:
839:
834:
831:
822:
819:
790:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
746:
729:
726:
695:Turing machine
691:
690:
678:
658:
638:
613:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
575:
571:
567:
563:
560:
557:
554:
551:
547:
543:
540:
530:
518:
515:
512:
502:
490:
487:
484:
474:
462:
459:
456:
446:
434:
424:
412:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
335:
332:
322:
319:
318:
317:
308:
307:
283:
280:
276:
275:
272:
269:
250:
247:
233:
230:
189:
188:
186:
185:
178:
171:
163:
160:
159:
158:
157:
152:
144:
143:
139:
138:
137:
136:
131:
126:
121:
116:
111:
106:
101:
96:
91:
86:
81:
76:
68:
67:
63:
62:
61:
60:
55:
50:
42:
41:
37:
36:
26:
9:
6:
4:
3:
2:
1381:
1370:
1367:
1366:
1364:
1355:
1352:
1349:
1346:
1345:
1335:
1329:
1325:
1321:
1317:
1313:
1307:
1302:
1301:
1294:
1293:
1286:
1283:
1275:
1264:
1261:
1257:
1254:
1250:
1247:
1243:
1240:
1236:
1233: –
1232:
1228:
1227:Find sources:
1221:
1217:
1211:
1210:
1205:This article
1203:
1199:
1194:
1193:
1176:
1171:
1164:
1157:
1153:
1148:
1140:
1134:
1129:
1128:
1122:
1118:
1112:
1094:
1087:
1079:
1077:0-7167-1045-5
1073:
1068:
1067:
1058:
1054:
1044:
1041:
1040:
1034:
1030:
1028:
1023:
1019:
1015:
1011:
969:
929:
914:
909:
900:
898:
888:
886:
881:
875:
865:
856:
847:
838:
830:
828:
818:
816:
812:
808:
803:
788:
781:
778:
775:
772:
769:
766:
763:
757:
751:
748:
744:
733:
725:
723:
718:
713:
709:
707:
703:
698:
696:
676:
656:
636:
628:
611:
604:
601:
598:
595:
592:
586:
580:
577:
573:
569:
565:
558:
555:
549:
545:
541:
538:
531:
516:
513:
510:
503:
485:
482:
475:
460:
457:
454:
447:
425:
410:
403:
402:
401:
384:
381:
378:
375:
372:
369:
366:
363:
357:
354:
348:
345:
331:
329:
326:the machine "
315:
314:
313:
312:
305:
304:
303:
301:
297:
288:
279:
273:
270:
267:
266:
265:
263:
258:
256:
246:
244:
240:
229:
227:
223:
219:
214:
212:
208:
204:
200:
196:
184:
179:
177:
172:
170:
165:
164:
162:
161:
156:
153:
151:
148:
147:
146:
145:
141:
140:
135:
132:
130:
127:
125:
122:
120:
117:
115:
112:
110:
107:
105:
102:
100:
97:
95:
92:
90:
87:
85:
82:
80:
77:
75:
72:
71:
70:
69:
65:
64:
59:
56:
54:
51:
49:
46:
45:
44:
43:
39:
38:
35:
32:
31:
19:
1323:
1299:
1278:
1272:January 2019
1269:
1259:
1252:
1245:
1238:
1226:
1214:Please help
1209:verification
1206:
1163:
1147:
1126:
1111:
1100:. Retrieved
1086:
1065:
1057:
1031:
1014:quantum bits
1007:
896:
894:
877:
862:
853:
844:
836:
824:
814:
810:
806:
804:
734:
731:
721:
717:at least one
716:
714:
710:
705:
701:
699:
692:
626:
337:
324:
310:
309:
299:
295:
293:
277:
261:
259:
252:
242:
238:
235:
215:
206:
202:
198:
192:
134:Zeno machine
83:
1027:NP-complete
150:Alan Turing
1242:newspapers
1175:cs/0409051
1102:2019-04-07
1049:References
334:Definition
232:Background
970:≠
930:≠
764:−
758:×
755:Σ
752:×
587:×
584:Σ
581:×
570:×
562:Σ
559:×
553:∖
542:⊆
539:δ
514:⊆
489:Σ
486:∈
483:⊔
458:∈
455:ι
433:Σ
385:δ
373:⊔
367:ι
361:Σ
282:Intuition
1363:Category
1037:See also
1008:Because
400:, where
328:branches
66:Variants
1256:scholar
1188:General
224:is the
142:Science
40:Machine
1330:
1308:
1258:
1251:
1244:
1237:
1229:
1135:
1074:
807:reject
706:yields
702:yields
1263:JSTOR
1249:books
1170:arXiv
1096:(PDF)
815:every
253:In a
239:state
1328:ISBN
1306:ISBN
1235:news
1133:ISBN
1072:ISBN
1012:use
952:and
241:and
197:, a
1218:by
811:any
722:any
300:NTM
207:not
203:NTM
193:In
1365::
1154:,
1119:;
629:.
311:or
213:.
1336:.
1314:.
1285:)
1279:(
1274:)
1270:(
1260:·
1253:·
1246:·
1239:·
1212:.
1180:.
1178:.
1172::
1158:.
1141:.
1105:.
1080:.
990:E
987:C
984:A
981:P
978:S
975:P
965:P
962:N
938:P
935:N
925:P
897:T
789:)
785:}
782:1
779:+
776:,
773:0
770:,
767:1
761:{
749:Q
745:(
677:R
657:S
637:L
612:)
608:}
605:R
602:,
599:S
596:,
593:L
590:{
578:Q
574:(
566:)
556:A
550:Q
546:(
517:Q
511:A
461:Q
411:Q
388:)
382:,
379:A
376:,
370:,
364:,
358:,
355:Q
352:(
349:=
346:M
298:(
201:(
182:e
175:t
168:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
