2 ms·
It is exactly that: you can simulate a Turing machine using lambda calculus and vice versa. But the variable substitution schemes you mention are not complex a
by rbonvall 8y ago
It is exactly that: you can simulate a Turing machine using lambda calculus and vice versa.
But the variable substitution schemes you mention are not complex at all. The main rule is beta-reduction, which is really simple: just replace all appearances of the parameter with the value of the argument.
(λ x . (x y) x) m → (m y) m
β
- WorldMaker 8y agoIt's designed as a silly game for kids, but I still think Alligator Eggs is a good example of how fundamentally simple the Lambda Calculus substitution rules are (especially for people that want a more visual/metaphorical representation): http://worrydream.com/AlligatorEggs/ http://worrydream.com/AlligatorEggs/