Màquina de Turing no determinista

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.

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 diferencia en el fet 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'altra manera és imaginar-se que la màquina "es divideix" en diverses 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.

Definició

Més formalment, una Màquina de Turing no determinsta és un 6-tupla $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , on

$Q$ és un conjunt finit d'estats
$\Sigma$ és un conjunt finits de símbols de cinta (l'alfabet de cinta)
$\iota \in Q$ és l'estat inicial
$\sqcup$ és un símbol denominat blanc ( $\sqcup \in \Sigma$ )
$A\subseteq Q$ és el conjunt d'estats finals d'acceptació
$\delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)$ é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.

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 tan 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.

Vegeu també

Referències

Harry R. Lewis, Christos Papadimitriou (1981). Elements of the Theory of Computation. 1a 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. 2a edició, McGraw-Hill. ISBN 0-07-040845-9. Secció 9.6: Nondeterministic Turing machines, pp.277–281.
Christos Papadimitriou (1993). Computational Complexity. 1a edició, Addison-Wesley. ISBN 0201530821. Secció 2.7: Nondeterministic machines, pp.45–50.