Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The typed lambda calculus is not Turing complete.


Not quite true, depends on the flavor of the type system you use. Church's simply typed is not, but other type systems are.

I think one way to make it Turing complete is to add typing rule for Y combinator as an axiom to your simple type system, but I am not sure.


Yes, I had Church's simply typed lambda calculus in mind. You need to add a fix point combinator or general recursion.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: