Tuve algunos pensamientos acerca de cómo demostrar la completitud de turing de un lenguaje de programación. Llegué a la conclusión, que si podía escribir un programa que es capaz de analizar un programa de máquina de turing, ambos deberían ser equivalentes como podría ejecutar cada programa de la máquina de turing con ese analizador escrito en ese idioma. Por lo tanto el lenguaje debe ser turing completo. ¿Estoy correcto? ¿Cuáles son otras formas de la prueba de lo completo de turing?
Respuestas
¿Demasiados anuncios?
Un lenguaje de programación es Turing completo si y sólo si podemos escribir cada computable de la función en este idioma. Para demostrar que podemos emular una máquina de turing es una buena manera de demostrar que un lenguaje no es turing completo, por la forma en que esta no es la única manera, de otra forma puede ser para demostrar que el lenguaje es capaz de describir todas las $\mu$-funciones recursivas. Para hacer que usted sólo tiene que demostrar que se puede escribir algunos de los programas que calculan algunas funciones especiales (la constante de la función cero, el sucesor de operación y la proyección de las funciones) y la muestra de que se puede escribir de las operaciones de la composición de funciones y $\mu$-recursividad (recursión primitiva ser un caso especial de $\mu$-recursividad) en el plazo de las operaciones de los programas.
Espero que esto ayude.
sxd
Puntos
2637
El análisis no es realmente correcto. Creo que quisiste decir que si se puede simular una máquina de Turing en su lenguaje de programación.
Otro método: podría escribir un programa que evalúa todas las expresiones lambda computable cálculo. (O cualquier sistema formal que equivale a máquinas de Turing, por ejemplo, ábacos).
Justin Bennett
Puntos
2513
El análisis no es el punto, y aquí es por qué. El lenguaje de todos los programas sintácticamente correctos en una lengua dada es (o debería ser) recursivo, lo cual es inferior en la jerarquía de los idiomas definidos por Turing-completo de programación de sistemas, que es recursivamente enumerable. De hecho, para un modelo muy simple (como la de Turing de la formulación original), el lenguaje de todos los sintácticamente correcta "programas" podría ser tan bajo en la jerarquía de estado finito (regular).
En otras palabras, hay muy poca relación entre la dificultad de análisis de programas (estático de un tipo de tarea) y la simulación de los/emulación de la ejecución de un programa (una forma muy dinámica de la tarea).
Así que, como los demás, aquí dicen, usted necesita demostrar que el lenguaje de programación/modelo quieres demostrar Turing-completo puede llevar a cabo ciertas operaciones básicas y se pueden combinar operaciones para hacer más, arbitrariamente complejos programas.
Luego está el tema del almacenamiento ilimitado de modelos teóricos-como el de dos vías sin límites de cinta de una clásica Máquina de Turing -- frente a las limitaciones prácticas en el almacenamiento de la vida real de los lenguajes de programación y sistemas. Pero eso es un sutil tema que no suele ser abordado en responder a preguntas como la tuya, como lleva en un conjunto diferente de problemas teóricos.
