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. [NB 1]
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"; consulte 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 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 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 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 delimitados lineales completos. En contraste, 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 ):