3 ms·
The typed lambda calculus is not Turing complete.
by jonathanstrange 1y ago
The typed lambda calculus is not Turing complete.
- js8 1y agoNot 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.
- jonathanstrange 1y agoYes, I had Church's simply typed lambda calculus in mind. You need to add a fix point combinator or general recursion.