Completitud de Turing - Turing completeness

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 . Esto significa que este sistema puede reconocer o decidir otros conjuntos de reglas de manipulación de datos. La completitud 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. El concepto lleva el nombre del matemático e informático inglés Alan Turing .

Un concepto relacionado es el de la 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 ser calculados por un algoritmo puede ser calculada por un Turing, y por lo tanto, si cualquier computadora del mundo real puede simular una máquina de Turing, es Turing equivalente 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 del mundo real posible.

Para demostrar que algo es Turing completo, basta con mostrar que se puede usar para simular algún sistema Turing completo. Por ejemplo, un lenguaje imperativo es Turing-completo si tiene bifurcaciones condicionales (p. Ej., Declaraciones "if" y "goto", o una instrucción "branch if zero"; ver computadora con un conjunto de instrucciones ) y la capacidad de cambiar una instrucción arbitraria cantidad de memoria (por ejemplo, la capacidad de mantener un número arbitrario de elementos de datos). Por supuesto, 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 por lo demás Turing-completos.

Uso no matemático

En el uso coloquial , los términos "Turing-completo" y "Turing-equivalente" se utilizan para significar que cualquier computadora de propósito general del mundo real o lenguaje de computadora puede simular aproximadamente los aspectos computacionales de cualquier otra computadora de propósito general del mundo real o lenguaje de ordenador.

Las computadoras reales construidas hasta ahora 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 un autómata delimitado lineal completo. En contraste, una computadora universal se define como un dispositivo con un conjunto de instrucciones completo 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 ):

Completitud de Turing
Un sistema computacional que puede calcular todas las funciones computables de Turing se llama Turing-completo (o Turing-poderoso). Alternativamente, tal sistema es uno que puede simular una máquina de Turing universal .
Equivalencia de Turing
Un sistema completo de Turing se denomina equivalente de Turing si todas las funciones que puede calcular también lo son; es decir, calcula precisamente la misma clase de funciones que las máquinas de Turing . Alternativamente, un sistema equivalente de Turing es uno que puede simular y ser simulado por una máquina de Turing universal. (Todos los sistemas Turing completos que se pueden implementar físicamente son equivalentes a Turing, lo que añade apoyo a la tesis de Church-Turing ).
Universalidad (computacional)
Un sistema se denomina universal con respecto a una clase de sistemas si puede calcular todas las funciones computables por los sistemas de esa clase (o puede simular cada uno de esos sistemas). Típicamente, el término universalidad se usa tácitamente con respecto a una clase de sistemas completa de Turing. El término "débilmente universal" se usa a veces para distinguir un sistema (por ejemplo, un autómata celular ) cuya universalidad se logra solo modificando la definición estándar de máquina de Turing para incluir flujos de entrada con infinitos unos.

Historia

La completitud de Turing es significativa 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 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 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 que no tenga nada que ver con la computación.

El motor analítico 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 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. 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 rama 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 se pueden calcular mediante el cálculo de memoria, pero no son suficientes para hacer 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 podrían ser realizadas por una máquina. Pronto quedó claro que un pequeño conjunto de reglas de deducción son suficientes 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 se aisló poco después, comenzando con el teorema de incompletitud de Gödel . Este teorema mostró que los sistemas de axiomas eran limitados al razonar sobre el cálculo que deduce sus teoremas. Church y Turing demostraron de forma independiente que el problema de decisión ( Entscheidungsproblem) de Hilbert era irresoluble, 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, 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, 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 realizar saltos condicionales, y por lo tanto Turing completo, al utilizar algunas de sus características de manera no intencionada.

Teoría de la computabilidad

La teoría de la computabilidad usa 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 que es imposible predecir lo que hará un sistema (Turing completo) durante un tiempo arbitrariamente largo.

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

En su lugar, 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, proporcionar solo bucles que iteren sobre los elementos de una matriz existente). Sin embargo, otro teorema muestra que hay problemas que se pueden resolver con lenguajes completos de Turing que no pueden ser resueltos por ningún lenguaje con solo habilidades de bucle finito (es decir, cualquier lenguaje que garantice que cada programa eventualmente terminará en un punto muerto). Entonces, tal lenguaje no es Turing completo. Por ejemplo, un lenguaje en el que los programas están garantizados para completarse y detenerse 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 la detención o algún otro problema indecidible de Turing. Una cinta de datos tan infinita 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 innumerables cálculos pero incontables oráculos. 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 físicas conocidas tienen consecuencias que se pueden calcular mediante una serie de aproximaciones en una computadora digital. Una hipótesis llamada física digital establece que esto no es un accidente porque el universo mismo es computable en una máquina de Turing universal. Esto implicaría que ninguna computadora más poderosa que una máquina universal de Turing puede construirse físicamente.

Ejemplos de

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 . Están pensados ​​para ser lo más simples posible, para que sea más fácil comprender los límites de la computación. A continuación, presentamos 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, más que 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 usarían construcciones de bucle o posiblemente incluso declaraciones goto para lograr la repetición; Haskell y Prolog, que carecen de bucles casi por completo, usarí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 Turing completos.

La completitud de Turing en SQL declarativo se implementa mediante expresiones de tabla comunes recursivas . Como era de esperar, las extensiones de procedimiento de SQL ( PLSQL , etc.) también son Turing-complete. Esto ilustra una razón por la cual 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, lo que fomenta su desarrollo. extensión hasta que sea Turing-completo.

El cálculo lambda sin tipo es Turing completo, pero muchos cálculos lambda con tipo, incluido el Sistema F , no lo son. El valor de los sistemas escritos se basa en su capacidad para representar la mayoría de los programas informáticos típicos mientras detectan más errores.

Rule 110 y Game of Life de Conway , ambos autómatas celulares , son Turing completos.

Completitud involuntaria de Turing

Algunos juegos y otro software se completan con Turing por accidente, es decir, no por diseño.

Software:

Juegos de vídeo:

Medios de comunicación social:

Juegos de cartas:

Juegos de cero personas (simulaciones):

Lenguajes computacionales:

Hardware de la computadora:

  • instrucción MOV x86

Biología:

Idiomas no completos de Turing

Existen muchos lenguajes computacionales que no son Turing completos. Un ejemplo 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 los autómatas finitos es la categoría de autómatas pushdown y gramáticas libres de contexto , que se utilizan comúnmente para generar árboles de análisis sintáctico 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 incrustados en las extensiones Direct3D y OpenGL .

En los lenguajes de programación funcional total , como Charity y Epigram , todas las funciones son totales y deben finalizar. Charity usa un sistema de tipos y constructos de control basados ​​en la teoría de categorías , mientras que Epigram usa tipos dependientes . El lenguaje LOOP está diseñado para que solo calcule las funciones que son recursivas primitivas . Todos estos calculan subconjuntos adecuados 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 enumerables recursivamente 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 tipado no lo es.

Idiomas de datos

La noción de completitud de Turing no se aplica a lenguajes como XML , HTML , JSON y YAML , porque generalmente se usan para representar datos estructurados, no para describir computación. A veces se los denomina lenguajes de marcado o, más propiamente, "lenguajes contenedores" o "lenguajes de descripción de datos".

Ver también

Notas

Referencias

Otras lecturas

enlaces externos