La guía paso a paso o código que hallarás en este post es la solución más sencilla y efectiva que encontramos a tu duda o problema.
Solución:
Aquí está la explicación más breve:
Un sistema completo de Turing significa un sistema en el que se puede escribir un programa que encontrará una respuesta (aunque sin garantías con respecto al tiempo de ejecución o la memoria).
Entonces, si alguien dice “mi novedad es Turing Complete”, eso significa que en principio (aunque a menudo no en la práctica) podría usarse para resolver cualquier problema de cálculo.
A veces es una broma… un tipo escribió un simulador de la Máquina de Turing en vi, por lo que es posible decir que vi es el único motor computacional que se necesita en el mundo.
Aquí está la explicación más simple.
Alan Turing creó una máquina que puede tomar un programa, ejecutarlo y mostrar algún resultado. Pero luego tuvo que crear diferentes máquinas para diferentes programas. Así que creó la “Máquina Universal de Turing” que puede tomar CUALQUIER programa y ejecutarlo.
Los lenguajes de programación son similares a esas máquinas (aunque virtuales). Toman programas y los ejecutan. Ahora, un lenguaje de programación se llama “Turing completo”, si puede ejecutar cualquier programa (independientemente del idioma) que una máquina de Turing pueda ejecutar con suficiente tiempo y memoria.
Por ejemplo: Digamos que hay un programa que toma 10 números y los suma. Una máquina de Turing puede ejecutar fácilmente este programa. Pero ahora imagine que, por alguna razón, su lenguaje de programación no puede realizar la misma suma. Esto lo haría “Turing incompleto” (por así decirlo). Por otro lado, si puede ejecutar cualquier programa que pueda ejecutar la máquina universal de Turing, entonces es Turing completo.
La mayoría de los lenguajes de programación modernos (p. ej., Java, JavaScript, Perl, etc.) están completos en Turing porque cada uno de ellos implementa todas las funciones necesarias para ejecutar programas como suma, multiplicación, condición if-else, declaraciones de retorno, formas de almacenar/recuperar/borrar datos y así sucesivamente.
Actualización: puede obtener más información en la publicación de mi blog: “JavaScript se está completando” – Explicación
Definición informal
Un lenguaje completo de Turing es aquel que puede realizar cualquier cálculo. La tesis de Church-Turing establece que cualquier cálculo realizable puede ser realizado por una máquina de Turing. Una máquina de Turing es una máquina con una memoria infinita de acceso aleatorio y un ‘programa’ finito que dicta cuándo debe leer, escribir y moverse a través de esa memoria, cuándo debe terminar con un resultado determinado y qué debe hacer a continuación. La entrada a una máquina de Turing se guarda en su memoria antes de que comience.
Cosas que pueden hacer que un idioma NO esté completo en Turing
Una máquina de Turing puede tomar decisiones basadas en lo que ve en la memoria – El ‘lenguaje’ que solo soporta +, -, *y / en enteros no es Turing completo porque no puede tomar una decisión en función de su entrada, pero una máquina de Turing sí puede.
Una máquina de Turing puede funcionar eternamente – Si tomamos Java, Javascript o Python y eliminamos la capacidad de realizar cualquier tipo de bucle, GOTO o llamada de función, Turing no estaría completo porque no puede realizar un cálculo arbitrario que nunca finaliza. Coq es un probador de teoremas que no puede expresar programas que no terminan, por lo que no es Turing completo.
Una máquina de Turing puede usar memoria infinita – Un lenguaje que era exactamente como Java pero que terminaría una vez que usara más de 4 Gigabytes de memoria no sería Turing completo, porque una máquina de Turing puede usar memoria infinita. Es por eso que en realidad no podemos construir una máquina de Turing, pero Java sigue siendo un lenguaje completo de Turing porque el Java idioma no tiene ninguna restricción que le impida usar memoria infinita. Esta es una de las razones por las que las expresiones regulares no están completas en Turing.
Una máquina de Turing tiene memoria de acceso aleatorio – Un lenguaje que solo te permite trabajar con la memoria a través de push y pop las operaciones a una pila no estarían completas de Turing. Si tengo un ‘idioma’ que lee un string una vez y solo puede usar la memoria empujando y sacando de una pila, puede decirme si cada ( en el string tiene su propio ) luego empujando cuando ve ( y salta cuando ve ). Sin embargo, no puede decirme si cada ( tiene su propio ) mas tarde y todos [ has its own ] más tarde (tenga en cuenta que ([)] cumple con este criterio pero ([]] no es). Una máquina de Turing puede usar su memoria de acceso aleatorio para rastrear ()‘arena []‘s por separado, pero este lenguaje con solo una pila no puede.
Una máquina de Turing puede simular cualquier otra máquina de Turing – Una máquina de Turing, cuando se le da un ‘programa’ apropiado, puede tomar el ‘programa’ de otra máquina de Turing y simularlo con una entrada arbitraria. Si tuviera un lenguaje que tuviera prohibido implementar un intérprete de Python, no sería Turing completo.
Ejemplos de lenguajes completos de Turing
Si su idioma tiene una memoria de acceso aleatorio infinita, ejecución condicional y alguna forma de ejecución repetida, probablemente Turing esté completo. Hay sistemas más exóticos que aún pueden lograr todo lo que puede lograr una máquina de Turing, lo que los hace también completos de Turing:
- Cálculo lambda sin tipo
- El juego de la vida de Conway
- Plantillas C++
- Prólogo
Recuerda algo, que puedes valorar esta noticia si encontraste tu preocupación en el momento exacto.