Good Math

But Is It Turing Complete?

λ calculus, as we described it in the previous chapter, is Turing complete. The question that you should be asking yourself now is how. Remember the three properties of computation? You need to have unbounded storage; you need to be able to do arithmetic; and you need to be able to do control flow. How can we do that in λ calculus?

The storage part is easy. You can store arbitrarily complicated values in a variable, and we can generate as many functions as we need without bound. So unbounded storage is pretty obvious.

But arithmetic? In our work so far we’ve just handwaved arithmetic by treating it as a primitive. In fact, we can create a very cool way of doing arithmetic using nothing but λ expressions.

And ...