Màquina universal de Turing

Una màquina universal de Turing (o també màquina de Turing universal) és una màquina de Turing que pot simular qualsevol màquina de Turing amb una entrada arbitrària. La màquina universal ho aconsegueix llegint una descripció de la màquina a simular i l'entrada a computar des de la seva pròpia cinta. Va ser el propi Alan Turing qui va introduir aquesta idea, i es considera que és l'origen de la idea d'un computador amb el programa emmagatzemat desenvolupat per John von Newmann en el "Electronic Computing Instrument" i que s'ha consolidat amb el nom d'arquitectura de von Newmann.^[1]

En termes de complexitat computacional, una màquina universal de Turing amb multicinta és només un factor logarítmic més lenta que la màquina que simula.^[2]

Introducció

Tota màquina de Turing computa una funció computable parcial fixada des d'una cadena d'entrada sobre el seu alfabet. En aquest sentit, es comporta com un ordinador amb un programa fixat. Tot i això, es pot codificar el conjunt de transicions (també dita taula d'acció) de qualsevol màquina de Turing en una cadena i, per tant, es pot construir una màquina de Turing que espera llegir de la seva cinta una cadena descrivint una taula d'acció seguida d'una cadena descrivint la cinta d'entrada i computa la cinta tal com ho hagués fet la màquina codificada. Turing va descriure aquesta construcció amb detall al seu article del 1936:

És possible inventar una única màquina que pot ser utilitzada per computar qualsevol seqüència computable. Si aquesta màquina U està proveïda amb una cinta on hi és escrit el S.D. ("Descripció Estàndard" d'una taula d'acció) d'alguna màquina de computació M, llavors U computarà la mateixa seqüència que M.^[3]

Formalisme matemàtic

Amb la codificació de la taula d'acció d'una màquina de Turing com cadenes, és possible per una màquina de Turing respondre qüestions sobre el comportament d'altres màquines de Turing. Moltes d'aquestes qüestions, però, son indecidibles, això és, que la qüestió no es pot resoldre d'una forma mecànica. Per exemple, el problema de saber si una màquina de Turing s'aturarà segons una certa entrada (conegut com a problema de la parada) és, en general, indedicible. El teorema de Rice demostra que qualsevol qüestió no trivial sobre la sortida d'una màquina de Turing és indecidible.^[2]

Una màquina universal de Turing pot calcular qualsevol funció recursiva, decidir qualsevol llenguatge recursiu i acceptar qualsevol llenguatge enumerable recursivament. Segons la tesi de Church-Turing, els problemes solucionables per una màquina universal de Turing son els mateixos solucionables per un algorisme o un mètode efectiu de computació per qualsevol definició raonable d'aquests termes. Per aquest motiu, la màquina universal de Turing serveix com un estàndard amb qui comparar sistemes computacionals. Un sistema que pot simular una màquina universal de Turing se'n diu que és Turing complet.

Una versió abstracta d'una màquina universal de Turing és la funció universal, una funció computable que es pot fer servir per computar qualsevol altre funció computable. El teorema UTM demostra que tal funció existeix.

Eficiència

Sense perdre generalitat, l'alfabet d'entrada d'una màquina de Turing es pot assumir que és {0,1} i qualsevol altre alfabet finit es pot codificar en aquest. La funció de transferència també es pot codificar com una cadena en aquest alfabet. També es pot convenir l'ordre de diferents símbols i estats a la cinta, fent, per exemple, que els dos primers estats a la cinta es corresponguin amb l'estat inicial i l'estat que accepta. Per tant, tota màquina de Turing es pot codificar com una cadena de símbol de l'alfabet {0,1}. A més, també es pot convenir que qualsevol codificació errònia es mapeja a una màquina trivial que s'atura immediatament i que cada màquina de Turing es pot codificar amb un nombre infinit de cadenes afegint tants '1' com es vulgui al final de la cadena. Aquesta cadena es pot fer correspondre amb un valor numèric (el nombre de Gödel) i aquest valor α es pot fer correspondre a una màquina M_a.

Es pot demostrar que si existeix una màquina de Turing M_a que s'atura per una entrada x en N passos, llavors existeix una màquina universal de Turing multicinta que s'atura per l'entrada a, x (cada cadena a una cinta diferent) en CN log N, on C és una constant específica de cada màquina universal i que no depèn de l'entrada x. Això és, doncs, una simulació en ${\displaystyle {\mathcal {O}}\left(N\log {N}\right)}$.^[2]

Màquines mínimes

Quan Alan Turing va descriure aquesta màquina universal, tenia al cap el model computacional més simple possible però amb prou potència per a computar qualsevol funció computable. Claude Shannon va ser el primer en plantejar de trobar la màquina de Turing universal més petita possible el 1956. Va demostrar que dos símbols son suficients si es fan servir prou estats (i a l'inrevés) i que sempre és possible intercanviar símbols per estats.

Marvin Minsky va presentar una màquina de Turing universal amb 7 estats i 4 símbols fent servir màquines de Post. S'han dissenyat altres màquines de Turing universals seguint aquesta aproximació. Si es denota per (m, n) la classe de màquines de Turing universals amb m estats i n símbols, s'han trobat les següents tuples: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), i (2, 18). Yurii Rogozhin va dissenyar una màquina (4, 6) amb només 22 instruccions i és la màquina més petita coneguda.^[4][5][6]

Si es generalitza la màquina de Turing universal es poden obtenir màquines encara més petites. Una d'aquestes generalitzacions és permetre que una paraula es repeteixi indefinidament en un o els dos costats de l'entrada de la màquina (conegudes com a semi-dèbil o dèbil respectivament). S'han dissenyat màquines de Turing universals dèbils molt petites que simulen l'autòmat cel·lular Regla 110, que se sap que és Turing complet, amb les tuples següents: (6, 2), (3, 3) i (2, 4).^[7]

Referències

1. Davis, Martin. The universal computer : the road from Leibniz to Turing. Nova York: Norton, 2000. ISBN 0393047857.
2. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
3. Turing, A. M. «On Computable Numbers, with an Application to the Entscheidungsproblem» (en anglès). Proceedings of the London Mathematical Society, s2-42, 1, 1937, pàg. 230–265. Arxivat de l'original el 2019-06-27. DOI: 10.1112/plms/s2-42.1.230. ISSN: 1460-244X [Consulta: 22 desembre 2018].
4. Rogozhin, Yurii; Kudlek, Manfred «A Universal Turing Machine with 3 States and 9 Symbols» (en anglès). International Conference on Developments in Language Theory. Springer, Berlin, Heidelberg, 16-07-2001, pàg. 311–318. DOI: 10.1007/3-540-46011-X_27.
5. «Small universal Turing machines» (en anglès). Theoretical Computer Science, 168, 2, 20-11-1996, pàg. 215-240. DOI: 10.1016/S0304-3975(96)00077-1. ISSN: 0304-3975.
6. Woods, Damien; Neary, Turlough «Four Small Universal Turing Machines» (en anglès). International Conference on Machines, Computations, and Universality. Springer, Berlin, Heidelberg, 10-09-2007, pàg. 242–254. DOI: 10.1007/978-3-540-74593-8_21.
7. Woods, Damien; Neary, Turlough «Small Weakly Universal Turing Machines» (en anglès). International Symposium on Fundamentals of Computation Theory. Springer, Berlin, Heidelberg, 02-09-2009, pàg. 262–273. DOI: 10.1007/978-3-642-03409-1_24.