Turing complet

En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programacio i d'altres sistemes logics, un sistema Turing complet es aquell que te un poder computacional equivalent a la maquina universal de Turing. En altres paraules, el sistema i la maquina universal de Turing poden emular-se entre si.

Encara quan es fisicament impossible que existeixin aquestes maquines a causa que requereixen emmagatzematge il*limitat i probabilitat zero d'error, de forma col*loquial la completesa de Turing s'atribueix a maquines fisiques o llenguatges de programacio que podrien ser universals si tinguessin emmagatzematge infinit i fossin absolutament fiables. La primera d'aquestes maquines va apareixer en 1941: la Z3 de Konrad Zuse, que era controlada per programes. La seva universalitat, no obstant aixo, va ser demostrada molt de temps despres per Raul Rojas en 1998.^[1] En aquest sentit, tots els ordinadors moderns son tambe Turing complets.

La completesa de Turing es significativa, doncs, cada disseny plausible d'un dispositiu de computacio, per mes avancat que sigui (adhuc els ordinadors quantics), poden ser emulades per una maquina universal de Turing. Aixi, una maquina que pugui actuar com una maquina universal de Turing pot, en principi, fer qualsevol calcul que qualsevol altre ordinador es capac de fer (en altres paraules, es programable). No obstant aixo, no hi ha esforc d'escriure un programa per a la maquina o sobre el temps que pot prendre el calcul.^{[NB 1]}

Hi ha la hipotesi que l'Univers es Turing complet (vegeu implicacions filosofiques en la Tesi de Church-Turing i en Fisica digital).

Vegeu l'article de Teoria de la computabilitat per a una llarga llista de sistemes que son Turing complets, aixi com diversos sistemes que son menys potents, i diversos sistemes teorics que son encara mes potents que la maquina universal de Turing.

Es dificil trobar exemples de llenguatges no Turing complets, ja que aquests llenguatges son molt limitats. Un exemple podrien ser les series de formules matematiques en un full de calcul sense cicles. Mentre que es possible fer diverses operacions interessants en aquest sistema, aquesta mancanca l'impedeix ser Turing complet. Per contra, el llenguatge de macros d'Excel es Turing complet, ja que aquest llenguatge de programacio si que incorpora cicles. Un altre famos exemple de llenguatges no Turing complets son les expressions regulars contingudes en llenguatges com perl. Una llista de llenguatges Turing complets esta sota el marc de la teoria de la computabilitat.

Un important resultat de la teoria de la computabilitat es que, en general, es impossible saber si un programa escrit en un llenguatge Turing complet es continuara executant indefinidament o es detindra en un periode finit de temps. Un metode per prevenir que succeeixi es fer que els programes es detinguin despres d'un periode fix de temps. Estrictament, aquests sistemes no son Turing complets.

El calcul lambda sense tipus es Turing complet, pero molts calculs lambda amb tipus, incloent el Sistema F no ho son. El valor dels sistemes amb tipus es basa en la seva habilitat de representar molts dels programes d'ordinador "tipics" mentre es detecten els seus errors.

• Tesi de Church-Turing
• Teoria de la informacio algoritmica
• El llibre de Stephen Wolfram Un nou tipus de ciencia
• Algorisme quantic

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley. ISBN 0-471-09585-0
• Simplest 'universal computer' wins student $25,000 by Jim Giles, New Scientist, October 24, 2007.
• The Universal Turing Machine: A Half-Century Survey (1995), ed. Rolf Herken, Springer Verlag. ISBN 3-211-82637-8
• Turing, A. M. <<On Computable Numbers, with an Application to the Entscheidungsproblem>>. Proceedings of the London Mathematical Society, 42, 1936, pag. 230-65. DOI: 10.1112/plms/s2-42.1.230. (and Turing, A.M. <>. Proceedings of the London Mathematical Society, p. 544-6.)

• c2.com