Good Math

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 ...