I have two related questions:

  1. Do you know of any good reference to the recursive function / lambda-calculus equivalence in terms of computability, including proofs?
  2. Do you know of any reference to subclasses of computable layers in lambda-calculus, like you have in recursion theory? It looks like you can't "dumb down" lambda-calculus but I'm not sure about that. And if we can't "dumb it down" to less computable classes, I'd love some reference to why this is so.
  • 1
    $\begingroup$ Although the questions are somewhat related, it might be better to split them. $\endgroup$ Sep 10, 2021 at 17:08
  • $\begingroup$ For 1., see e.g. J. Hindley & J. Seldin (2008), Lambda Calculus and Combinators: An introduction, chapter 4. $\endgroup$ Sep 10, 2021 at 18:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.