The Turing machine model has been extended to “infinitary turing machines”, which are Turing machines that can perform a countably and uncountably infinite amount of computations in finite time.

Is there a similar model for the lambda calculus that is computationally equivalent to the infinite Turing machine? (I.e. that is “infinitarily turing complete”?).

I’ve seen some papers on infinitary lambda calculus, but I’m not sure if the concept is computationally equivalent to infinite turing machines.


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.