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$
    – lemontree
    Sep 10, 2021 at 18:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.