Turing complet
En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing. En altres paraules, el sistema i la màquina universal de Turing poden emular-se entre si.
Encara quan és físicament impossible que existeixin aquestes màquines a causa que requereixen emmagatzematge il·limitat i probabilitat zero d'error, de forma col·loquial la completesa de Turing s'atribueix a màquines físiques o llenguatges de programació que podrien ser universals si tinguessin emmagatzematge infinit i fossin absolutament fiables. La primera d'aquestes màquines va aparèixer en 1941: la Z3 de Konrad Zuse, que era controlada per programes. La seva universalitat, no obstant això, va ser demostrada molt de temps després per Raúl Rojas en 1998.[1] En aquest sentit, tots els ordinadors moderns són també Turing complets.
La completesa de Turing és significativa, doncs, cada disseny plausible d'un dispositiu de computació, per més avançat que sigui (àdhuc els ordinadors quàntics), poden ser emulades per una màquina universal de Turing. Així, una màquina que pugui actuar com una màquina universal de Turing pot, en principi, fer qualsevol càlcul que qualsevol altre ordinador és capaç de fer (en altres paraules, és programable). No obstant això, no hi ha esforç d'escriure un programa per a la màquina o sobre el temps que pot prendre el càlcul.[NB 1]
Hi ha la hipòtesi que l'Univers és Turing complet (vegeu implicacions filosòfiques en la Tesi de Church-Turing i en Física digital).
Vegeu l'article de Teoria de la computabilitat per a una llarga llista de sistemes que són Turing complets, així com diversos sistemes que són menys potents, i diversos sistemes teòrics que són encara més potents que la màquina universal de Turing.
Exemples modifica
És difícil trobar exemples de llenguatges no Turing complets, ja que aquests llenguatges són molt limitats. Un exemple podrien ser les sèries de fórmules matemàtiques en un full de càlcul sense cicles. Mentre que és possible fer diverses operacions interessants en aquest sistema, aquesta mancança l'impedeix ser Turing complet. Per contra, el llenguatge de macros d'Excel és Turing complet, ja que aquest llenguatge de programació sí que incorpora cicles. Un altre famós exemple de llenguatges no Turing complets són les expressions regulars contingudes en llenguatges com perl. Una llista de llenguatges Turing complets està sota el marc de la teoria de la computabilitat.
Un important resultat de la teoria de la computabilitat és que, en general, és impossible saber si un programa escrit en un llenguatge Turing complet es continuarà executant indefinidament o es detindrà en un període finit de temps. Un mètode per prevenir que succeeixi és fer que els programes es detinguin després d'un període fix de temps. Estrictament, aquests sistemes no són Turing complets.
El càlcul lambda sense tipus és Turing complet, però molts càlculs lambda amb tipus, incloent el Sistema F no ho són. El valor dels sistemes amb tipus es basa en la seva habilitat de representar molts dels programes d'ordinador "típics" mentre es detecten els seus errors.
Notes modifica
Referències modifica
- ↑ «| Link a paper (en anglès)». Arxivat de l'original el 2014-07-14. [Consulta: 23 agost 2015].
Vegeu també modifica
Bibliografia modifica
- 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, pàg. 230–65. DOI: 10.1112/plms/s2-42.1.230. (and Turing, A.M. «On Computable Numbers, with an Application to the Entscheidungsproblem: A correction». Proceedings of the London Mathematical Society, p. 544–6.)