¿Importa la ‘integridad de Turing’ en los lenguajes de programación? Si es así, ¿por qué?

Answer 1

Un lenguaje de programación se considera Turing Complete si puede simular cualquier Turing Machine de una sola cinta. De acuerdo con la Tesis de Church-Turing, cualquier operación matemática es informalmente computable (solucionable, posible, tiene sentido en el mundo real) si y solo si es computable por una Máquina de Turing. Por lo tanto, un lenguaje Turing Complete es capaz de completar cualquier operación matemática imaginable (dada la memoria y el tiempo ilimitados). A la inversa, un lenguaje completo que no sea de Turing solo es capaz de completar un subconjunto de operaciones matemáticas imaginables.

“¿Es ‘importante?'”, Pregunta Warren.

Depende de lo que estés tratando de hacer. ¿Necesita una prueba formal de que, por ejemplo, Java es Turing Complete para escribir una aplicación web de pedidos de pizza? Probablemente no. Sin embargo, si comienza a utilizar algunos de los lenguajes de programación puramente funcionales más esotéricos que existen, se separa de una clase de problemas que puede resolver.

Sin embargo, si está utilizando algunos de los lenguajes puramente funcionales más esotéricos, probablemente también sepa en qué se está metiendo.

Answer 2

Cualquier lenguaje de programación que sea Turing Complete puede resolver cualquier problema computable en tiempo polinomial usando recursos finitos. Eso es absolutamente seguro. Un lenguaje de programación que NO es Turing Complete solo puede resolver un subconjunto de esos problemas y no puede saber de antemano qué es ese subconjunto.

Para completar Turing, un lenguaje de programación debe tener la capacidad de realizar las siguientes siete operaciones o algo simbólicamente equivalente: Negar un valor *, restar un valor *, asignar un valor *, derivar si un valor es negativo, saltar a una instrucción específica Salta a una instrucción referenciada, detiene el programa.

* A / desde cualquier ubicación arbitraria en la memoria.

Esto cubre esencialmente todos los lenguajes de primera, segunda y tercera generación y todos los lenguajes de cuarta generación que no terminen de manera comprobable. La cantidad de idiomas que no están completos de Turing es extremadamente limitada y simplemente no existen fuera de entornos altamente especializados.

(No todos los lenguajes de gráficos de computadora son Turing Complete, ni la mayoría de los lenguajes de expresión regular, y habrá casos marginales en la fabricación asistida por computadora, pero los requisitos son tan triviales que estar incompleto es casi inútil).