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

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

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