So far, we saw machines that can compute numbers like SUCC1 or Pop1. Each machine executes own procedures. A procedure is a sequence of instructions, for example, what does the machine do on an input, what does the machine do to create an output. Here we intentionally limited that the machine can only execute one instruction at a time for simplicity, means there is no parallel processing. The examples of instruction are: copy the input number on the input table to the output table, remove head and tail from the number on the output table.
We show the possibility of calculation by a machine which executes a procedure. The concrete examples are SUCC1 and Pop1. We can construct arbitrary machines in the same way. But, do we need to design machines for each problem? To compute addition, do we need Pop1? To compute subtraction, do we need Subtraction1? Or, can we design a little bit more general machine, that one machine can do addition, subtraction, multiplication, and division?
When a mathematician reached this point, s/he can not help thinking: ``How many instruction is sufficient to solve all the mathematical problem?'' ``How can we consider 'all' mathematical problem?'' ``What can we compute and can not compute in this way?''
We have already talk about a motivation of the lambda calculus. The motivation of lambda calculus is to think about the foundations of mathematics. Lambda calculus re-think the mathematics by a formal way. This lead us that calculation can be composed of procedures and that are composed of instructions. Each instruction is performed by a machine. Therefore, calculation can be done by a formal way. It is possible! We saw the possibility. Then people start to ask the next level questions. Many of the science or mathematics develed in the similar patterns.
It's time to go to the next level of lambda calculus.
3 months ago