Turing complet

En la teoria de computadoras reals i virtuals, dels llenguages de programació i d'atres sistemes llògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina de Turing universal. En atres paraules, el sistema i la màquina universal de Turing poden emular-se entre sí.

Aun cuando és físicament impossible que existixquen estes màquines degut a que requerixen d'almagasenament illimitat i provabilitat zero de falla, de forma coloquial la completitud de Turing s'atribuïx a màquines físiques o llenguages de programació que podrien ser universals si tingueren almagasenament infinit i foren absolutament fiables. La primera d'eixes màquines va aparéixer en 1941: la Z3 de Konrad Zuse, que era controlada per programes. La seua universalitat, no obstant, va ser demostrada molt despuix per Raúl Rojas en 1998. En eixe sentit laxo, totes les computadores modernes són també Turing completes.

La completitud de Turing és significativa, puix, cada disseny verosímil d'un dispositiu de computació, per més alvançat que siga (encara les computadores quàntiques), poden ser emulades per una màquina universal de Turing. Aixina, una màquina que puga actuar com una màquina universal de Turing pot, en principi, fer qualsevol càlcul que qualsevol atra computadora és capaç de fer (vore Tesis de Church-Turing). Observe's, no obstant, que no diu res sobre l'esforç d'escriure un programa per a la màquina o sobre el temps que pot prendre el càlcul.

A partir d'esta descripció, emana d'ella la hipòtesis de que l'Univers és Turing complet (vore implicacions filosòfiques en la Tesis de Church-Turing i en Física digital), com una forma de metafísica computacional.

Vore l'artícul en Teoria de la computabilidad per a una llarga llista de sistemes que són Turing complets, aixina com varis sistemes que són menys poderosos, i varis sistemes teòrics que serien encara més poderosos que la màquina universal de Turing.

Eixemples

Molts sistemes aparentment simples resulten ser Turing complets. Eixemples de sistemes de menor poder computacional podrien ser les séries de fòrmules matemàtiques en una hoja sense cicles. Mentres que és possible fer vàries operacions interessants en eixe sistema, este falla en ser Turing complet ya que és impossible fer cicles. El llenguage de macros d'Excel, no obstant, és Turing complet. Atres eixemples de llenguages Turing incomplets són les expressions regulars, o el llenguage script de tipo pila. Una llista de llenguages Turing complets està baix el rubro de teoria de la computabilidad.

Un important resultat de la teoria de la computabilidad és que, en general, és impossible saber si un programa escrit en un llenguage Turing complet es continuarà eixecutant indefinidament o es detindrà en un periodo finito de temps. Un método per a previndre que succeïxca lo primer és fer que els programes es detinguen despuix d'un periodo fix de temps. Estrictament, eixos sistemes no són Turing complets.

El càlcul lambda sense tipo és Turing complet, pero molts càlculs lambda en tipo, incloent el Sistema F no ho són. El valor dels sistemes en tipo es basa en la seua habilitat de representar molts dels programes de computadora "típics" mentres es detecten els seus errors.

Vore també

• Tesis de Church-Turing
• Teoria de l'informació algorítmica
• El llibre de Stephen Wolfram Un nou tipo de ciència
• Algoritme quàntic
• Hipergrafo
• Realitat simulada
• Univers holográfico