# How math and computation are related

I would like to illustrate to you how math and computation are related. Consider the well-known theorem that 2 + 2 = 4. Like any theorem, it is the result of a proof, which necessarily follows from a set of assumptions. We might prove such a theorem to a child by counting on fingers, starting with 2, then counting on 2 more. We might also prove it using Peano arithmetic. You might even consider a lookup table as a method of proof. What matters is that we have some point of agreement, and from that point of agreement, the theorem that 2 + 2 = 4 necessarily follows. The set of assumptions that we take on, which include our definitions and rules of inference, are very much like a computer program. We could build a program that adds, and verify that 2 + 2 indeed results in 4. We could also design a computer that verifies equations such as 2 + 2 = 4. We plug in an equation, and get a response of true or false.

Computer programs and functions are nearly the same thing. A computer program which always halts is a total function. A computer program which doesn't always halt is a partial function. The inputs to a function are the questions we have, and the output is the answer to our question. If we were to build a computer program to verify theorems of Peano arithmetic, that program would be a partial function, as Peano arithmetic is an undecidable theory.