In order to show that Lambda calculus and Turing machines are equivalent it is sufficient to show that you can simulate one in the other [both ways].

We can observe it in action. Can one do the same on general recursive functions [ie mathematical functions as defined by Godel]

Are there any reference reading materials?


1 Answer 1


To simulate the lambda calculus on a Turing machine, all you need to do is build an interpreter for the lambda calculus. That is easy. If you want a reference, I recommend Structure and Interpretation of Computer Programs. In general, what are describing falls within computability theory, so I recommend studying a good textbook on that subject. There are many.

  • $\begingroup$ The question already acknowledges that it is possible to simulate lambda calculus on turing machines. I want to know how to simulate lambda calculus by using mathematical functions in the theory of general recursive functions [partial recursive functions] $\endgroup$
    – RFV
    Oct 11, 2022 at 18:23
  • $\begingroup$ @RFV, I encourage you to edit the question to make it clearer what you already know and what you are asking, then. I didn't realize you already know this and that you were asking that. I think it would help to state those explicitly in the question. $\endgroup$
    – D.W.
    Oct 12, 2022 at 2:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.