M??quina de Turing no determinista
De Viquip??dia
En teoria de la computaci??, una M??quina de Turing no determinista (MTN) ??s una M??quina de Turing on el seu mecanisme de control treballa com un aut??mat finit no determinista.
Taula de continguts |
[edita] Descripci??
Una M??quina de Turing ordin??ria (MTD) t?? una funci?? de transfer??ncia tal que, donat un estat i un s??mbol sota el cap??al de la cinta, especifica tres coses: el s??mbol a escriure a la cinta, el sentit (esquerra o dreta) cap on s'ha de moure el cap??al, i el seg??ent estat del control finit. Per exemple, una X en la cinta en l'estat 3 pot fer que la M??quina de Turing escrigui una Y a la cinta, mogui el cap??al una posici?? cap a la dret i canvi?? a l'estat 5.
Una MTN es difer??ncia en que l'estat i el s??mbol de la cinta ja no especifiquen ??nicament aquests par??metres ??? accions diferents poden succeir per la mateixa combinaci?? d'estat i s??mbol. Per exemple, una X en la cinta en l'estat 3 pot permetre a la MTN escriure una Y, moure cap a la dreta i canviar a l'estat 5 o escriure una X, moure cap a l'esquerra, i quedar-se en l'estat 3.
Com ???sap??? la MTN quines accions ha de prendre? Hi ha dues maneres de veure-ho. Una ??s que la m??quina t?? ???molta sort??? i sempre tria la transici?? que eventualment la porta a un estat correcte, si existeix tal transici??. L'altre manera ??s imaginar-se que la m??quina ???es divideix??? en v??ries c??pies, i cada una segueix una de les possibles transicions. On una MTD t?? un sol ???cam?? de computaci????? a seguir, una MTN t?? un ???arbre de computaci?????. Si alguna de les branques de l'arbre s'atura amb una condici?? ???accepta???, es diu que la MTN accepta l'entrada.
[edita] Definici??
M??s formalment, una M??quina de Turing no determinsta ??s un 6-tupla 
, on
- Q ??s un conjunt finit d'estats
- ?? ??s un conjunt finits de s??mbols de cinta (l'alfabet de cinta)
??s l'estat inicial
??s un s??mbol denominat blanc (
)
??s el conjunt d'estats finals d'aceptaci??
??s una funci?? multivaluada sobre els estats i els s??mbols anomenada funci?? de transici??, on L ??s un moviment a l'esquerra i R ??s el moviment a la dreta. En les M??quines de Turing convencionals, aquesta funci?? no ??s multivaluada.
[edita] Equival??ncia amb MTDs
Intu??tivament es pot veure que les MTNs s??n m??s potents que no pas les MTDs, ja que poden realitzar moltes possibles computacions, requerint tant sols que una d'elles sigui acabi amb ??xit. Per?? qualsevol llenguatge reconegut per una MTN pot ser reconegut tamb?? per una MTD; la MTD pot simular cada transici?? de la MTN, fent m??ltiples c??pies de l'estat simulat quan hi ha m??ltiples transicions, i simular-les totes en paral??lel, no gaire diferent a un sistema operatiu multitasca
??s evident que aquesta simulaci?? requerir?? for??a m??s temps. Quan m??s temps normalment no es coneix ??? aquesta ??s, resumint, la definici?? del problema ?????s P = NP????. Vegeu P versus NP.
[edita] Vegeu tamb??
[edita] Refer??ncies
- Harry R. Lewis, Christos Papadimitriou (1981). Elements of the Theory of Computation. 1era edici??, Prentice-Hall. ISBN 0-13-273417-6. Secci?? 4.6: Nondeterministic Turing machines, pp.204???211.
- John C. Martin (1997). Introduction to Languages and the Theory of Computation. 2ona edici??, McGraw-Hill. ISBN 0-07-040845-9. Secci?? 9.6: Nondeterministic Turing machines, pp.277???281.
- Christos Papadimitriou (1993). Computational Complexity. 1era edici??, Addison-Wesley. ISBN 0201530821. Secci?? 2.7: Nondeterministic machines, pp.45???50.
