O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required