Good Math

Decisions? Back to Church

With numbers out of the way, we’re closing in on Turing completeness. We’re still missing two things: the ability to make decisions, and repetition.

To make decisions, we’re going to do something very similar to how we did numbers. To represent numbers, we built functions that computed the numbers. To do choice, we’re going to do almost the same trick: we’re going to create Boolean values that select alternatives.

For making decisions, we’d like to be able to write choices as if/then/else expressions, like we have in most programming languages. Following the basic pattern of the Church numerals, where a number is expressed as a function that adds itself to another number, we’ll express true and false values as functions ...