Numbers That Compute Themselves
To show that λ calculus is Turing complete, we said we need to show two more things. We need to be able to do arithmetic, and we need to be able to do flow control. For arithmetic, we get—once again!—to create numbers. But this time we’ll do them with λ expressions. We’ll also see how to take the same basic mechanics that we’ll use to create numbers, and turn them into a form of conditional if/then/else construct, which will give us the first half of what we need for full flow control in λ calculus.
As we’ve seen, all we have to work with in λ calculus is functions written as λ expressions. If we want to create numbers, we have to do it by devising some way of creating objects that we can use to do Peano arithmetic ...
Get Good Math now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
