Completitud de Turing

En la teoría de la computabilidad, se dice que un sistema de reglas de manipulación de datos (como el conjunto de instrucciones de una 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 (ideada por el matemático e informático inglés Alan Turing). Esto significa que este sistema puede 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 un conjunto de reglas de manipulación de datos de este tipo. Prácticamente todos los lenguajes de programación actuales son Turing-completos.

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 pueden ser calculado por un algoritmo puede ser calculado 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 el equivalente de Turing a una máquina de Turing. Se puede usar una máquina de Turing universal para simular cualquier máquina de Turing y, por extensión, los aspectos computacionales de cualquier computadora posible del mundo real.

Para mostrar que algo es Turing completo, basta con mostrar que se puede usar para simular algún sistema Turing completo. Ningún sistema físico puede tener una 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.

Uso no matemático

En el uso coloquial, los términos "Turing-completo" y "equivalente de Turing" se utilizan para indicar que cualquier computadora o lenguaje informático de propósito general del mundo real puede simular aproximadamente los aspectos computacionales de cualquier otra computadora o lenguaje informático de propósito general del mundo real. En la vida real, esto lleva a los conceptos prácticos de emulación y virtualización informática.

Las computadoras reales construidas hasta el momento pueden analizarse funcionalmente como una máquina de Turing de una sola cinta (la "cinta" correspondiente a su 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 limitados completos. En contraste, una computadora universal se define como un dispositivo con un conjunto completo de instrucciones de Turing, memoria infinita y tiempo disponible infinito.

Definiciones formales

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):

Completación Turística

Un sistema computacional que puede calcular cada función compatible con Turing se llama Turing-complete (o Turing-powerful). Alternativamente, tal sistema es uno que puede simular una máquina de Turing universal.

equivalencia de Turing

A Turing-complete system is called Turing-equivalent if every function it can compute is also Turing-computable; i.e., que compute precisamente la misma clase de funciones que las máquinas Turing. Alternativamente, un sistema de Turing-equivallent es uno que puede simular, y ser simulado por, una máquina de Turing universal. (Todos los sistemas de Turing-completo físicamente conocidos son Turing-equivalente, lo que añade apoyo a la Iglesia-Turing thesis.)

(Computacional) universalidad

Un sistema se llama universal respecto a una clase de sistemas si puede calcular cada función computable por sistemas de esa clase (o puede simular cada uno de esos sistemas). Típicamente, el término 'universalidad' se utiliza tácitamente con respecto a una clase completa de sistemas Turing. El término "debilidad universal" se utiliza a veces para distinguir un sistema (por ejemplo, un autómata celular) cuya universalidad se logra sólo modificando la definición estándar de la máquina de Turing para incluir flujos de entrada con infinitamente muchos 1s.

Historia

La integridad de Turing es importante porque cada diseño del mundo real para un dispositivo informático se puede simular mediante una máquina de Turing universal. La tesis de Church-Turing establece que esta 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. 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 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 completa de Turing si se hubiera construido en el momento en que se diseñó. Babbage apreció que la máquina fuera capaz de grandes hazañas de cálculo, incluido el razonamiento lógico primitivo, pero no apreció que ninguna otra máquina pudiera hacerlo mejor. 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 bifurcación condicional y, por lo tanto, no eran 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álculo de memoria, pero no son suficientes para hacer una computadora universal, porque las instrucciones que las calculan no permiten un ciclo 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 podría realizar 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. Estas reglas fueron probadas por Kurt Gödel en 1930 como suficientes para producir todos los teoremas.

La noción real de computación se aisló poco después, comenzando con el teorema de incompletitud de Gödel. Este teorema mostró que los sistemas de axiomas estaban limitados al 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 no tenía solución, identificando así el problema computacional núcleo 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, pueden 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, el Z3 carecía de instalaciones dedicadas para un salto condicional, lo que impedía que fuera Turing completo. Sin embargo, en 1998, Rojas demostró que el Z3 es capaz de simular saltos condicionales y, por lo tanto, Turing 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.

La primera computadora capaz de bifurcación condicional 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ó la bifurcación condicional hasta 1950.

Teoría de la computabilidad

La teoría de la computabilidad utiliza modelos de computación para analizar problemas y determinar si son computables y en qué circunstancias. El primer resultado de la teoría de la computabilidad es que existen problemas para los que es imposible predecir qué hará un sistema (Turing-completo) durante un tiempo arbitrariamente largo.

El ejemplo clásico es el problema de detención: cree un algoritmo que tome como entrada un programa en algún lenguaje completo de Turing y algunos datos para alimentar a ese programa, y determine 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 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 al 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 causarían bucles infinitos.

En cambio, se puede limitar un programa para que se ejecute solo durante un período de tiempo fijo (tiempo de espera) o limitar el poder de las instrucciones de control de flujo (por ejemplo, proporcionando solo bucles que iteran sobre los elementos de una matriz existente). Sin embargo, otro teorema muestra que hay problemas que se pueden resolver con los lenguajes completos de Turing que no se pueden resolver con ningún lenguaje que solo tenga capacidades finitas de bucle (es decir, cualquier lenguaje que garantice que todos los programas finalmente se detendrán). Entonces, cualquier lenguaje de este tipo no es Turing-completo. Por ejemplo, un lenguaje en el que se garantiza que los programas se completan y detienen no puede calcular la función computable producida por el argumento diagonal de Cantor en todas las funciones computables en ese lenguaje.

Oráculos de Turing

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 puede contener la solución al problema de detención o algún otro problema indecidible de Turing. Tal 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 solo hay muchos cálculos contables pero muchos oráculos incontables. Entonces, una computadora con un oráculo de Turing aleatorio puede calcular cosas que una máquina de Turing no puede.

Física digital

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 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 ninguna computadora más poderosa que una máquina de Turing universal.

Ejemplos

Los sistemas computacionales (álgebras, cálculos) que se describen como sistemas completos de Turing son aquellos destinados al estudio de la informática teórica. Están destinados a ser lo más simples posible, para que sea más fácil comprender los límites de la computación. Aquí hay algunos:

• Teoría de Automata
• Gramática formal (generadores lingüísticos)
• Lenguaje formal (reconocimientos de idiomas)
• Lambda cálculo
• Post-Turing machines
• Cálculo de proceso

La mayoría de los lenguajes de programación (sus modelos abstractos, tal vez con algunas construcciones particulares que asumen que se omite la memoria finita), convencionales y no convencionales, son completos de Turing. Esto incluye:

• Todos los idiomas de uso general en uso amplio.
  • Idiomas de programación procesal como C, Pascal.
  • Idiomas orientados a objetos como Java, Smalltalk o C#.
  • Idiomas multiparadigma como Ada, C++, Common Lisp, Fortran, JavaScript, Object Pascal, Perl, Python, R.
• La mayoría de los idiomas que utilizan paradigmas menos comunes:
  • Idiomas funcionales como Lisp y Haskell.
  • Idiomas de programación lógica como Prolog.
  • Procesador macro de uso general, como m4.
  • Idiomas declarativos como XSLT.
  • VHDL y otros idiomas de descripción de hardware.
  • TeX, un sistema de clasificación.
  • Lenguas de programación esotérica, una forma de recreación matemática en la que los programadores trabajan cómo lograr construcciones de programación básica en un lenguaje extremadamente difícil pero matemáticamente equivalente Turing.

Algunos sistemas de reescritura son Turing-completos.

La completitud de Turing es una declaración abstracta de habilidad, en lugar de 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 sentencias goto para lograr la repetición; Haskell y Prolog, que carecen casi por completo de bucles, utilizarían la recursividad. 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 Turing sea completa. Incluso los lenguajes funcionales puros son completos de Turing.

La integridad de Turing en SQL declarativo se implementa a través de expresiones de tablas comunes recursivas. Como era de esperar, las extensiones de procedimiento de SQL (PLSQL, etc.) también están 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 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, fomentando su uso. extensión hasta que es Turing-completo.

El cálculo lambda sin tipo es completo de Turing, pero muchos cálculos lambda con 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 mientras detectan más errores.

La Regla 110 y el Juego de la vida de Conway, ambos autómatas celulares, son Turing completos.

Integridad de Turing involuntaria

Algunos juegos y otro software están completos con Turing por accidente, es decir, no por diseño.

Software:

• Microsoft Excel
• Microsoft PowerPoint

Videojuegos:

• Dwarf Fortress
• Ciudades: Skylines
• Opus Magnum
• Minecraft

Redes sociales:

• Habbo Hotel

Lenguajes computacionales:

• Plantillas C++
• string formato printf
• Sistema de tipo TipoScript

Hardware informático:

• instrucción MOV x86

Biología:

• Las redes de reacción química y las computadoras de ADN basadas en enzimas han demostrado ser equivalentes en Turing

Lenguajes no completos de Turing

Existen muchos lenguajes computacionales que no son completos de Turing. Un ejemplo de ello es el conjunto de lenguajes regulares, que son generados por expresiones regulares y que son reconocidos por autómatas finitos. Una extensión más poderosa pero aún no completa de Turing de 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 de Direct3D y OpenGL.

En los lenguajes de programación funcional total, como Charity y Epigram, todas las funciones son totales y deben terminar. Charity usa un sistema de tipos y construcciones de control basadas en la teoría de categorías, mientras que Epigram usa tipos dependientes. El lenguaje LOOP está diseñado para calcular solo las funciones que son recursivas primitivas. Todos estos calculan subconjuntos propios de las funciones computables totales, ya que el conjunto completo de funciones computables totales no es enumerable computablemente. 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 tipo) es Turing-completo, el cálculo lambda simplemente mecanografiado no lo es.