En la teoría de la computabilidad , se dice que un sistema de reglas de manipulación de datos (como un modelo de computación , un conjunto de instrucciones de computadora , un lenguaje de programación o un autómata celular ) es Turing-completo o computacionalmente universal si se puede usar para simular cualquier máquina de Turing [ cita requerida ] (ideada por el matemático y científico informático inglés Alan Turing ). Esto significa que este sistema es capaz de reconocer o decodificar otros conjuntos de reglas de manipulación de datos. La completitud de Turing se usa como una forma de expresar el poder de dicho conjunto de reglas de manipulación de datos. Virtualmente todos los lenguajes de programación actuales son Turing-completos. [ cita requerida ]
Un concepto relacionado es el de equivalencia de Turing : dos computadoras P y Q se consideran equivalentes si P puede simular Q y Q puede simular P. [ cita requerida ] La tesis de Church-Turing conjetura que cualquier función cuyos valores puedan ser calculados por un algoritmo puede ser calculada por una máquina de Turing y, por lo tanto, que si cualquier computadora del mundo real puede simular una máquina de Turing, es equivalente de Turing a una máquina de Turing. Una máquina de Turing universal puede usarse para simular cualquier máquina de Turing y, por extensión, los aspectos puramente computacionales de cualquier posible computadora del mundo real. [ cita requerida ]
Para demostrar que algo es Turing-completo, basta con demostrar que puede utilizarse para simular algún sistema Turing-completo. Ningún sistema físico puede tener memoria infinita, pero si se ignora la limitación de la memoria finita, la mayoría de los lenguajes de programación son Turing-completos. [ cita requerida ]
En el lenguaje coloquial , los términos "Turing-completo" y "Turing-equivalente" se utilizan para indicar que cualquier computadora o lenguaje de programación de uso general del mundo real puede simular aproximadamente los aspectos computacionales de cualquier otra computadora o lenguaje de programación de uso general del mundo real. En la vida real, esto conduce a los conceptos prácticos de virtualización y emulación computacional . [ cita requerida ]
Los ordenadores reales construidos hasta ahora pueden analizarse funcionalmente como una máquina de Turing de una sola cinta (que utiliza una "cinta" como memoria); por lo tanto, las matemáticas asociadas pueden aplicarse abstrayendo su funcionamiento lo suficiente. Sin embargo, los ordenadores reales tienen recursos físicos limitados, por lo que solo son autómatas lineales completos. En contraste, la abstracción de un ordenador universal se define como un dispositivo con un conjunto de instrucciones Turing-completo, memoria infinita y tiempo disponible infinito. [ cita requerida ]
En la teoría de la computabilidad , se utilizan varios términos estrechamente relacionados para describir la potencia computacional de un sistema computacional (como una máquina abstracta o un lenguaje de programación ):
La completitud de Turing es importante porque cada diseño del mundo real para un dispositivo informático puede ser simulado por una máquina de Turing universal . La tesis de Church-Turing afirma que se trata de una ley de las matemáticas: una máquina de Turing universal puede, en principio, realizar cualquier cálculo que cualquier otro ordenador programable pueda. Esto no dice nada sobre el esfuerzo necesario para escribir el programa , ni sobre el tiempo que puede llevar a la máquina realizar el cálculo, ni sobre las capacidades que pueda poseer la máquina que no tengan nada que ver con la computación.
La máquina analítica de Charles Babbage (década de 1830) habría sido la primera máquina Turing-completa si se hubiera construido en la época en que fue diseñada. Babbage apreciaba que la máquina era capaz de grandes hazañas de cálculo, incluido el razonamiento lógico primitivo, pero no apreciaba que ninguna otra máquina pudiera hacerlo mejor. [ cita requerida ] Desde la década de 1830 hasta la de 1940, se construyeron y mejoraron máquinas calculadoras mecánicas como sumadores y multiplicadores, pero no podían realizar una bifurcación condicional y, por lo tanto, no eran Turing-completas.
A finales del siglo XIX, Leopold Kronecker formuló nociones de computabilidad, definiendo funciones recursivas primitivas . Estas funciones pueden calcularse mediante cálculos de memoria, pero no son suficientes para crear una computadora universal, porque las instrucciones que las calculan no permiten un bucle infinito. A principios del siglo XX, David Hilbert dirigió un programa para axiomatizar todas las matemáticas con axiomas precisos y reglas lógicas precisas de deducción que pudieran ser realizadas por una máquina. Pronto quedó claro que un pequeño conjunto de reglas de deducción es suficiente para producir las consecuencias de cualquier conjunto de axiomas. Kurt Gödel demostró en 1930 que estas reglas eran suficientes para producir todos los teoremas.
La noción real de computación fue aislada poco después, comenzando con el teorema de incompletitud de Gödel . Este teorema mostró que los sistemas axiomáticos estaban limitados al razonar sobre el cálculo que deduce sus teoremas. Church y Turing demostraron independientemente que el Entscheidungsproblem (problema de decisión) de Hilbert era irresoluble, [1] identificando así el núcleo computacional del teorema de incompletitud. Este trabajo, junto con el trabajo de Gödel sobre funciones recursivas generales , estableció que hay conjuntos de instrucciones simples, que, cuando se juntan, son capaces de producir cualquier cálculo. El trabajo de Gödel mostró que la noción de computación es esencialmente única.
En 1941, Konrad Zuse completó la computadora Z3 . Zuse no estaba familiarizado con el trabajo de Turing sobre computabilidad en ese momento. En particular, la Z3 carecía de funciones dedicadas a un salto condicional, lo que impedía que fuera completa en términos de Turing. Sin embargo, en 1998, Rojas demostró que la Z3 es capaz de simular saltos condicionales y, por lo tanto, en teoría, completa en términos de Turing. Para hacer esto, su programa en cinta tendría que ser lo suficientemente largo como para ejecutar cada ruta posible a través de ambos lados de cada rama. [2]
El primer ordenador capaz de realizar ramificaciones condicionales en la práctica, y por tanto de realizar operaciones de Turing completas en la práctica, fue el ENIAC en 1946. El ordenador Z4 de Zuse estuvo operativo en 1945, pero no admitió ramificaciones condicionales hasta 1950. [3]
La teoría de la computabilidad utiliza modelos de computación para analizar problemas y determinar si son computables y bajo qué circunstancias. El primer resultado de la teoría de la computabilidad es que existen problemas para los cuales es imposible predecir qué hará un sistema (completo en el sentido de Turing) en un período de tiempo arbitrariamente largo.
El ejemplo clásico es el problema de la detención : crear un algoritmo que tome como entrada un programa en un lenguaje Turing-completo y algunos datos que se le van a suministrar , y determinar si el programa, que opera sobre la entrada, se detendrá eventualmente o continuará para siempre. Es trivial crear un algoritmo que pueda hacer esto para algunas entradas, pero es imposible hacerlo en general. Para cualquier característica de la salida final del programa, es imposible determinar si esta característica se mantendrá.
Esta imposibilidad plantea problemas a la hora de analizar programas informáticos del mundo real. Por ejemplo, no se puede crear una herramienta que proteja por completo a los programadores de escribir bucles infinitos o que proteja a los usuarios de proporcionar datos que causarían bucles infinitos.
En cambio, se puede limitar un programa para que se ejecute solo durante un período fijo de tiempo ( timeout ) o limitar el poder de las instrucciones de control de flujo (por ejemplo, proporcionando solo bucles que iteren sobre los elementos de una matriz existente). Sin embargo, otro teorema muestra que hay problemas solucionables por lenguajes Turing-completos que no pueden ser resueltos por ningún lenguaje con solo capacidades finitas de bucles (es decir, lenguajes que garantizan que cada programa eventualmente terminará en una parada). Por lo tanto, cualquier lenguaje de este tipo no es Turing-completo. Por ejemplo, un lenguaje en el que se garantiza que los programas se completen y se detengan no puede calcular la función computable producida por el argumento diagonal de Cantor en todas las funciones computables en ese lenguaje.
Un ordenador con acceso a una cinta infinita de datos puede ser más potente que una máquina de Turing: por ejemplo, la cinta podría contener la solución al problema de la detención o algún otro problema indecidible según Turing. Una cinta infinita de datos de este tipo se denomina oráculo de Turing . Incluso un oráculo de Turing con datos aleatorios no es computable ( con probabilidad 1 ), ya que solo hay una cantidad contable de cálculos, pero una cantidad incontable de oráculos. Por lo tanto, un ordenador con un oráculo de Turing aleatorio puede calcular cosas que una máquina de Turing no puede.
Todas las leyes conocidas de la física tienen consecuencias que se pueden calcular mediante una serie de aproximaciones en una computadora digital. Una hipótesis llamada física digital afirma que esto no es casualidad, ya que el universo mismo se puede calcular en una máquina de Turing universal. Esto implicaría que no se puede construir físicamente una computadora más potente que una máquina de Turing universal. [4]
Los sistemas computacionales (álgebras, cálculos) que se consideran sistemas Turing-completos son aquellos destinados al estudio de la informática teórica . Su objetivo es que sean lo más simples posible, de modo que resulte más fácil comprender los límites de la computación. A continuación se presentan algunos:
La mayoría de los lenguajes de programación (sus modelos abstractos, tal vez con algunas construcciones particulares que suponen que se omite la memoria finita), convencionales y no convencionales, son Turing-completos. Esto incluye:
Algunos sistemas de reescritura son Turing-completos.
La completitud de Turing es una declaración abstracta de capacidad, en lugar de una prescripción de características específicas del lenguaje utilizadas para implementar esa capacidad. Las características utilizadas para lograr la completitud de Turing pueden ser bastante diferentes; los sistemas Fortran utilizarían construcciones de bucle o posiblemente incluso declaraciones goto para lograr la repetición; Haskell y Prolog, que carecen de bucles casi por completo, utilizarían recursión . La mayoría de los lenguajes de programación describen cálculos en arquitecturas de von Neumann , que tienen memoria (RAM y registro) y una unidad de control. Estos dos elementos hacen que esta arquitectura sea Turing-completa. Incluso los lenguajes funcionales puros son Turing-completos. [7] [8]
La completitud de Turing en SQL declarativo se implementa a través de expresiones de tabla comunes recursivas . No es sorprendente que las extensiones procedimentales de SQL ( PLSQL , etc.) también sean Turing-completas. Esto ilustra una razón por la que los lenguajes no Turing-completos relativamente potentes son raros: cuanto más potente es el lenguaje inicialmente, más complejas son las tareas a las que se aplica y más pronto su falta de completitud se percibe como un inconveniente, lo que fomenta su extensión hasta que sea Turing-completo.
El cálculo lambda no tipificado es Turing-completo, pero muchos cálculos lambda tipificados, incluido el Sistema F , no lo son. El valor de los sistemas tipificados se basa en su capacidad para representar la mayoría de los programas informáticos típicos y detectar más errores.
La regla 110 y el Juego de la Vida de Conway , ambos autómatas celulares , son Turing-completos.
Algunos programas y videojuegos son Turing-completos por accidente, es decir, no por diseño.
Software:
Juegos:
Redes sociales:
Lenguajes computacionales:
Biología:
Existen muchos lenguajes computacionales que no son Turing-completos. Un ejemplo de ello es el conjunto de lenguajes regulares , que se generan mediante expresiones regulares y que son reconocidos por autómatas finitos . Una extensión más potente, pero aún no Turing-completa de los autómatas finitos, es la categoría de autómatas de inserción y gramáticas libres de contexto , que se utilizan comúnmente para generar árboles de análisis en una etapa inicial de la compilación de programas . Otros ejemplos incluyen algunas de las primeras versiones de los lenguajes de sombreado de píxeles integrados en las extensiones Direct3D y OpenGL . [ cita requerida ]
En lenguajes de programación funcional total , como Charity y Epigram , todas las funciones son totales y deben terminar. Charity utiliza un sistema de tipos y construcciones de control basadas en la teoría de categorías , mientras que Epigram utiliza tipos dependientes . El lenguaje LOOP está diseñado para que calcule solo las funciones que son recursivas primitivas . Todas estas calculan subconjuntos propios de las funciones computables totales, ya que el conjunto completo de funciones computables totales no es computablemente enumerable . Además, dado que todas las funciones en estos lenguajes son totales, los algoritmos para conjuntos recursivamente enumerables no se pueden escribir en estos lenguajes, a diferencia de las máquinas de Turing.
Aunque el cálculo lambda (sin tipificar) es Turing-completo, el cálculo lambda simplemente tipificado no lo es.