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 puede usarse 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 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. 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 denominan equivalentes si P puede simular Q y Q puede simular P. La tesis de Church-Turing conjetura que cualquier función cuyos valores pueden 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 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. [NOTA 1]
Para mostrar que algo es Turing-completo, es suficiente mostrar que puede usarse para simular algún sistema Turing-completo. Por ejemplo, un lenguaje imperativo es Turing-completo si tiene bifurcaciones condicionales (p. ej., declaraciones "si" y "ir a", o una instrucción "bifurcar si cero"; 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). 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.
En el uso coloquial , los términos "Turing-completo" y "Turing-equivalente" 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. 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 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.
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 ):