8
¿Cómo defiendes el hecho de que el cálculo lambda es Turing completo (de la manera más simple posible)?Turing la integridad del cálculo lambda?
A
Respuesta
8
La manera más sencilla es implementar una Máquina de Turing en el Cálculo Lambda. Esto es bastante fácil, porque el cálculo Lambda es prácticamente un lenguaje de programación de alto nivel. Este enfoque tiene la ventaja de no requerir ninguna otra dependencia matemática, y por lo tanto debe proporcionar la forma más simple posible de proporcionar su argumento.
En términos de una demostración matemática, el camino más corto aplica otro paradigma que ya se ha demostrado que es completo, como las funciones μ-recursivas. Estos ya están definidos de forma recursiva, por lo que su expresión en el cálculo Lambda es ligeramente más elegante que la Máquina de Turing.
1
Brainfuck es un lenguaje que muy de cerca los modelos de máquinas de Turing, y usted puede encontrar un intérprete de cálculo lambda explicado en http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck
Cuestiones relacionadas
- 1. cálculo lambda
- 2. Lambda Operadores de cálculo precedencia
- 3. Mantenimiento de la integridad del mensaje
- 4. Llamar por valor en el cálculo lambda
- 5. C++ templates Turing-complete?
- 6. consulta en Booleanos en cálculo lambda
- 7. Cálculo lambda y números de la iglesia confusión
- 8. ¿La metaprogramación del preprocesador C++ es Turing-completa?
- 9. ¿Qué es una máquina de Turing?
- 10. ¿El cifrado garantiza la integridad?
- 11. Función predecesora de cálculo lambda pasos de reducción
- 12. Números de iglesia: cómo codificar cero en cálculo lambda?
- 13. ¿Cuáles son algunos recursos para aprender el cálculo de Lambda?
- 14. ¿De qué tipo de cálculo lambda sería un ejemplo Lisp?
- 15. Alternativas a la prueba de Turing
- 16. Código ejercicio de las posibilidades únicas de cada borde del cálculo lambda
- 17. Cálculo del percentil
- 18. Cálculo del divisor CRC
- 19. Lambda dentro del bucle
- 20. ¿CouchDB es compatible con la integridad referencial?
- 21. lambda Python y la determinación del alcance
- 22. Mi máquina de turing simple
- 23. ¿Exigir integridad referencial en la ruta materializada?
- 24. ¿Cuándo la integridad referencial no es apropiada?
- 25. Preservar la integridad relacional con Mnesia
- 26. Integridad de la búsqueda en profundidad
- 27. ¿Es la ramificación condicional un requisito de Turing-completitud?
- 28. Cálculo del porcentaje del total de la fila con plyr
- 29. ¿Está completo el cálculo basado en Constexpr?
- 30. Cálculo del uso de CPU
Usted muestra que todos [Mu funciones recursivas] (https: //en.wikipedia .org/wiki /% CE% 9C-recursive_function) se puede expresar en el cálculo lambda, luego se basa en el resultado de Turing-completitud para aquellos –