With Turing machines, by imposing certain restrictions on the form of the transition function, one can get a machine that accepts only regular languages. I am wondering what is the counterpart in lambda calculus? In other words, how to restrict lambda calculus so it accepts only regular languages?

Related papers would be great, just as an explanation if my question does not make any sense, if that is the case.

  • 1
    $\begingroup$ The question does make sense to some degree. The kinds of restrictions are based on "type systems". $\endgroup$ – Dave Clarke Oct 14 '13 at 9:13
  • 1
    $\begingroup$ @bellpeace What alphabet are the languages over, what does acceptance mean in this context? After all, the input and output of $\lambda$-terms are themselves $\lambda$-terms. Regular languages are strings over an alphabet, but without encoding or extensions, $\lambda$-calculus does not feature strings. $\endgroup$ – Martin Berger Oct 15 '13 at 10:55
  • $\begingroup$ Good point. My question maybe should have been more general since this is one of the things I am curious about. $\endgroup$ – bellpeace Oct 15 '13 at 21:28
  • $\begingroup$ The standard definition of regular languages does not take into account the internal structure of elements of the alphabet. That's fine, but if you have something like $\lambda$-terms with a lot of interesting internal structure, you'd probably want to think about how to combine regularity with that internal structure. Have you got a specific application in mind? That could give you some ideas about what properties could be interesting here. $\endgroup$ – Martin Berger Oct 16 '13 at 10:48
  • $\begingroup$ Since untyped $\lambda$ calculus is Turing-complete, I was mainly interested in how to look at Chomsky hierarchy through the lense of lambda calculus. There is no specific application, yet merely theoretical interest. $\endgroup$ – bellpeace Oct 16 '13 at 15:23

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.