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 completo de Turing o computacionalmente universal si puede usarse para simular cualquier máquina de Turing (ideada por el matemático e informático inglés Alan Turing ). Esto significa que este sistema es capaz de reconocer o decidir otros conjuntos de reglas de manipulación de datos. La integridad de Turing se utiliza como una forma de expresar el poder de dicho conjunto de reglas de manipulación de datos. Prácticamente todos los lenguajes de programación actuales son Turing completo.
Un concepto relacionado es el de equivalencia de Turing : dos computadoras P y Q se llaman equivalentes si P puede simular Q y Q puede simular P. La tesis de Church-Turing conjetura que cualquier función cuyos valores puedan calcularse mediante un algoritmo puede calcularse mediante un Máquina de Turing y, por lo tanto, que si cualquier computadora del mundo real puede simular una máquina de Turing, es Turing equivalente a una máquina de Turing. Se puede utilizar una máquina de Turing universal para simular cualquier máquina de Turing y, por extensión, los aspectos puramente computacionales de cualquier posible computadora del mundo real.
Para demostrar que algo es Turing completo, basta demostrar que puede usarse 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, por lo demás, completos de Turing.
En el uso coloquial , los términos "Turing-completo" y "Turing-equivalente" se utilizan para significar que cualquier computadora o lenguaje informático de propósito general del mundo real puede simular aproximadamente los aspectos computacionales de cualquier otra computadora de propósito general del mundo real o lenguaje de ordenador. En la vida real, esto conduce a los conceptos prácticos de virtualización y emulación informática . [ cita necesaria ]
Las computadoras reales construidas 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 operación lo suficiente. Sin embargo, las computadoras reales tienen recursos físicos limitados, por lo que solo son autómatas lineales y completos. En contraste, la abstracción de una computadora universal se define como un dispositivo con un conjunto de instrucciones completo de Turing, memoria infinita y tiempo disponible infinito.
En la teoría de la computabilidad , se utilizan varios términos estrechamente relacionados para describir el poder computacional de un sistema computacional (como una máquina abstracta o un lenguaje de programación ):
La integridad de Turing es importante porque cada diseño del mundo real de un dispositivo informático puede simularse mediante una máquina de Turing universal . La tesis de Church-Turing afirma que ésta es una ley de las matemáticas: que una máquina universal de Turing puede, en principio, realizar cualquier cálculo que cualquier otra computadora programable pueda realizar. Esto no dice nada sobre el esfuerzo necesario para escribir el programa , o el tiempo que le puede tomar a la máquina realizar el cálculo, o cualquier habilidad que la máquina pueda poseer y que no tenga 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 el momento en que fue diseñada. Babbage apreciaba que la máquina fuera capaz de realizar grandes hazañas de cálculo, incluido el razonamiento lógico primitivo, pero no apreciaba que ninguna otra máquina pudiera hacerlo mejor. [ cita necesaria ] Desde la década de 1830 hasta la década de 1940, se construyeron y mejoraron máquinas calculadoras mecánicas como sumadores y multiplicadores, pero no podían realizar una rama condicional y, por lo tanto, no estaban completas de Turing.
A finales del siglo XIX, Leopold Kronecker formuló nociones de computabilidad, definiendo funciones recursivas primitivas . Estas funciones se pueden calcular 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 de deducción precisas que pudieran realizarse mediante 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 demostró que los sistemas de axiomas eran limitados a la hora de razonar sobre el cálculo que deduce sus teoremas. Church y Turing demostraron de forma independiente 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 existen conjuntos de instrucciones simples que, juntas, son capaces de producir cualquier cálculo. El trabajo de Gödel demostró 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, el Z3 carecía de instalaciones dedicadas para un salto condicional, lo que le impedía ser Turing completo. Sin embargo, en 1998, Rojas demostró que el Z3 es capaz de simular saltos condicionales y, por lo tanto, Turing es completo en teoría. Para hacer esto, su programa de cinta tendría que ser lo suficientemente largo para ejecutar todos los caminos posibles a ambos lados de cada rama. [2]
La primera computadora capaz de realizar bifurcaciones condicionales en la práctica y, por lo tanto, Turing completo en la práctica, fue la ENIAC en 1946. La computadora Z4 de Zuse estuvo operativa en 1945, pero no admitió bifurcaciones 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 de Turing) durante un tiempo arbitrariamente largo.
El ejemplo clásico es el problema de la detención : crear un algoritmo que toma como entrada un programa en algún lenguaje completo de Turing y algunos datos que se alimentarán a ese programa, y determina si el programa, operando en la entrada, eventualmente se detendrá o continuará. para siempre. Es trivial crear un algoritmo que pueda hacer esto para algunas entradas, pero imposible hacerlo en general. Para cualquier característica del resultado 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 escribir una herramienta que proteja por completo a los programadores de escribir bucles infinitos o que proteja a los usuarios de proporcionar entradas que provocarían bucles infinitos.
En cambio, se puede limitar la ejecución de un programa solo durante un período de tiempo fijo ( 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 que pueden resolverse con lenguajes completos de Turing que no pueden resolverse con ningún lenguaje que sólo tenga capacidades de bucle finitas (es decir, cualquier lenguaje que garantice que cada programa terminará finalmente por detenerse). 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 completarán y detendrán no puede calcular la función computable producida por el argumento diagonal de Cantor en todas las funciones computables en ese lenguaje.
Una computadora con acceso a una cinta infinita de datos puede ser más poderosa 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 para Turing. Esta cinta infinita de datos se llama oráculo de Turing . Incluso un oráculo de Turing con datos aleatorios no es computable ( con probabilidad 1 ), ya que sólo hay muchos cálculos contables pero muchos oráculos son incontables. Entonces, una computadora 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 son computables mediante una serie de aproximaciones en una computadora digital. Una hipótesis llamada física digital afirma que esto no es un accidente porque el universo mismo es computable en una máquina de Turing universal. Esto implicaría que no se puede construir físicamente ningún ordenador más potente que una máquina de Turing universal. [4]
Los sistemas computacionales (álgebras, cálculos) que se discuten como sistemas completos de Turing son aquellos destinados al estudio de la informática teórica . Se pretende que sean lo más simples posible, de modo que sea más fácil comprender los límites del cálculo. Aquí hay 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 integridad de Turing es una declaración abstracta de habilidad, más que una prescripción de características específicas del lenguaje utilizadas para implementar esa habilidad. Las características utilizadas para lograr la integridad de Turing pueden ser bastante diferentes; Los sistemas Fortran usarían construcciones de bucle o posiblemente incluso declaraciones goto para lograr la repetición; Haskell y Prolog, al carecer casi por completo de bucles, utilizarían la recursividad . La mayoría de los lenguajes de programación describen cálculos sobre arquitecturas von Neumann , que cuentan con 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 integridad de Turing en SQL declarativo se implementa mediante expresiones de tabla comunes recursivas . Como era de esperar, las extensiones de procedimientos de SQL ( PLSQL , etc.) también son completas en Turing. Esto ilustra una de las razones por las que los lenguajes no completos de Turing relativamente poderosos son raros: cuanto más poderoso es inicialmente el lenguaje, más complejas son las tareas a las que se aplica y más pronto su falta de integridad se percibe como un inconveniente, lo que fomenta su extensión hasta que esté completo en Turing.
El cálculo lambda sin tipo es Turing completo, pero muchos cálculos lambda tipo, 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 al mismo tiempo detectar más errores.
La Regla 110 y el Juego de la vida de Conway , ambos autómatas celulares , son Turing completos.
Algunos software y videojuegos son Turing completos por accidente, es decir, no por diseño.
Software:
Juegos:
Medios de comunicación social:
Lenguajes computacionales:
Biología:
Existen muchos lenguajes computacionales que no son completos en Turing. 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 poderosa, pero aún no completa de Turing, de los autómatas finitos es la categoría de autómatas pushdown y gramáticas libres de contexto , que se usan comúnmente para generar árboles de análisis en una etapa inicial de 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 necesaria ]
En lenguajes de programación totalmente funcionales , 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 calcular sólo las funciones que son recursivas primitivas . Todos estos calculan subconjuntos adecuados del total de funciones computables, 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 escribir) es completo en Turing, el cálculo lambda simplemente escrito no lo es.