[shasta]

"The other direction requires more thought: how do you coax such a simple language into providing the features we expect of a modern programming language, such as numbers, Booleans, conditionals, lists and recursion? "

No, the other direction requires simulating a Turing machine with lambda calculus.

[mattmight]

Good point.

But, those are exactly the language features that make it easy to implement a Turing machine.

[jacquesm]

Hey Matt,

Just a quick little note to thank you for your series of posts, not just this one. I've been trying to get my head wrapped around the lambda calculus and your posts have been by far the most enlightening ones on the subject.

Thank you very much!

[mattmight]

Thanks for reading! I'll keep the posts coming.

[davidmathers]

That really is a strange paragraph. Turing machines only consist of a line of memory cells, a pointer to the current cell, and a CRUD mechanism for the cells.

[joelhaasnoot]

See http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis Labda Calculus can be shown equivalent to Turing machines.

[davidmathers]

Sure, but the otherwise excellent OP isn't about that. It's about building higher level concepts out of the lambda calculus. Nothing to do with Turing machines.

Turing machines and lambda calculus are both foundational languages on top of which those higher level concepts can be constructed.

How to translate back and forth from Turing machine to lambda calculus is something I really want to understand actually. I've been meaning to sit down and figure it out but haven't done it yet.

[mattmight]

Thanks for your feedback.

I tweaked the abstract a bit to reflect your point.

I'll do a follow-on post on how to explicitly reduce the lambda calculus to Turing machines and vice versa.

Most of the hard work is done with this post.

[TheSOB88]

Some things just don't have an algorithm. You have to figure out each case by itself.