3 ms·
See http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis Labda Calculus can be shown equivalent t
by joelhaasnoot 16y ago
See http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
Labda Calculus can be shown equivalent to Turing machines.
- davidmathers 16y agoSure, 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 16y agoThanks 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 16y agoSome things just don't have an algorithm. You have to figure out each case by itself.