En informática y lógica , se dice que un sistema formal es completo en el sentido de Turing o Turing-completo (mediante el rastreo del inglés Turing-complete ) si tiene un poder expresivo al menos equivalente al de las máquinas de Turing . En tal sistema, por lo tanto, es posible programar cualquier máquina de Turing.
Esta noción adquiere relevancia con la tesis de Church , que postula la existencia de una noción natural de computabilidad. Así, el poder expresivo de las máquinas de Turing coincide con el de las funciones recursivas , el cálculo lambda o incluso las máquinas contadoras .
Aunque algunos modelos de cálculo, llamados hipercomputadores , son estrictamente más expresivos que las máquinas de Turing, estos modelos son objetos de especulación (que requieren, por ejemplo, realizar un número infinito de operaciones, o calcular sobre el conjunto de números reales) y no es saber si son físicamente factibles. En estas condiciones, la tesis de Church conjetura la universalidad del modelo computacional de la máquina de Turing: cualquier sistema completo de Turing sería de hecho equivalente a las máquinas de Turing.
Al igual que un modelo computacional, se dice que un lenguaje de computadora es Turing completo si permite que todas las funciones computables se representen en el sentido de Turing y Church (a pesar de la finitud de la memoria de la computadora).
Algunos autores toman esta propiedad para la definición de un lenguaje de programación , pero se pueden elegir otras definiciones.
Los lenguajes de programación habituales ( C , Java …) son Turing-complete porque tienen todos los ingredientes necesarios para la simulación de una máquina Turing universal (contar, comparar, leer, escribir, etc.). El lenguaje C ++ también es Turing-completo, y el subconjunto que permite la programación genérica ( plantillas ) también es .
El lenguaje SQL , originalmente incompleto en el sentido de Turing, se volvió así con el estándar SQL: 1999 permitiéndole escribir consultas recursivas .
El lenguaje LaTeX (de TeX ), destinado a la composición de documentos, también es Turing-completo.
El lenguaje HTML por sí solo no es Turing completo, aunque se ha demostrado que el lenguaje CSS (versión 3) permite construir el código 110 de autómata celular elemental (ver Regla 110 (en) ), conocido por ser universal en el sentido de Turing . Estos dos lenguajes son a menudo inseparables, podemos concluir que HTML + CSS es Turing-completo, y esta asociación, por lo tanto, teóricamente lo convierte en un lenguaje de programación.
Un lenguaje completo de Turing hereda las características de una máquina de Turing. Por ejemplo, el problema de apagado es indecidible , por lo que es imposible escribir un programa que diga si un programa arbitrario que se le dio termina o no.
Algunos lenguajes dedicados a tratar problemas específicos no están completos en Turing. El sistema F , un formalismo de cálculo lambda, es un ejemplo. Además, por diseño, los lenguajes totales (en) , donde todos los cálculos terminan necesariamente (como el lenguaje Gallina del asistente de pruebas Coq ), tampoco son Turing completos. Sin embargo, estos últimos son en la práctica capaces de calcular todo lo que les interesa, es decir, pueden implementar todas las funciones que podamos necesitar en la vida práctica; los cálculos que se les escapan, o tienen una complejidad más allá de lo imaginable y realizable, o no terminan. La compilación debe entonces demostrar la terminación de los programas, o requerir la interacción con el programador para algunas demostraciones, pero este es el precio a pagar por la calidad del código que es correcta por construcción.
Algunos juegos y software se completan con Turing por accidente, sin que sus autores lo deseen o lo consideren:
" El hecho de que todos los lenguajes de programación estándar expresan precisamente la clase de funciones recursivas parciales a menudo se resume en la afirmación de que todos los lenguajes de programación son Turing completo. "
“ Un lenguaje de programación es un lenguaje que está destinado a la expresión de programas informáticos y que es capaz de expresar cualquier programa informático. Ésta no es una noción vaga. Existe una forma teórica precisa de determinar si un lenguaje de computadora puede usarse para expresar cualquier programa, es decir, mostrando que es equivalente a una máquina de Turing universal. "