Tengo tres preguntas secundarias relacionadas, que se destacan con viñetas a continuación (no, no se pueden dividir, si se lo pregunta). Andrej Bauer escribió, aquí , que algunas funciones son realizables a través de una máquina de Turing, pero no a través del cálculo lambda. Un paso clave de su razonamiento es:
Sin embargo, si usamos el cálculo lambda, entonces [el programa] c debe calcular un número que representa una máquina de Turing a partir de un término lambda que representa una función f. Esto no se puede hacer (puedo explicar por qué, si lo hace como una pregunta por separado).
- Me gustaría ver una explicación / prueba informal.
No veo cómo aplicar el teorema de Rice aquí; se aplicaría al problema "¿son esta máquina de Turing T y este término lambda L equivalente?", porque la aplicación de este predicado a términos equivalentes da el mismo resultado. Sin embargo, la función requerida podría calcular TM diferentes pero equivalentes para términos lambda diferentes pero equivalentes.
- Además, si el problema es con la introspección de un término lambda, creo que pasar una codificación Gödel de un término lambda también sería aceptable, ¿no?
Por un lado, dado que su ejemplo implica calcular, en el cálculo lambda, el número de pasos que necesita una máquina de Turing para completar una tarea determinada, no estoy muy sorprendido.
- Pero como aquí el cálculo lambda no puede resolver un problema relacionado con la máquina de Turing, me pregunto si se puede definir un problema similar para el cálculo lambda y demostrar que no se puede resolver para las máquinas de Turing, o si existe una diferencia de poder a favor de Máquinas de Turing (lo que me sorprendería).
fuente
Lo que dijo Neel, y también lo siguiente.
fuente