2009-03-10

λ calculus: a two times function

Japanese version

Let's continue the λ calculus.

Let's write down a function which outputs two times of the input number. The input is 'x,' then the output is '2x.' Therefore, we could write it as

λ x . 2 x

If you see the last article's Figure 1, this is a function and its input is 'x' and the output is '2x.' Then this becomes a function which multiples the input with two.

However, this is not so exact. Here I cheated you a bit. We are now thinking about the functions. Do we know a function `multiplication?' We should start with something fundamental, then we would like to develop it. But here we already use an undefined function, `multiplication.' Let's think again, do we know about numbers? If we did not define numbers like ``2,'' we can not use it. One of my motivation to learn Lambda calculus was to build a machine which can compute the numbers. Functions like addition, multiplication, subtraction might be easy for human being, but how can a machine know them? We should define each of them, addition, multiplication, ...

What we already have is Church numbers. Let's get back to Church numbers later, but for the meantime, I would like to continue to talk about functions.

According to my school teacher, this function (λx.2x) is f(x) := 2x. g(x) := 2x also represents the same function. Input is x, then two times of input will be outputted. The names f(x) or g(x) are just an identifier as in the numbers which you might get in your townhall. (By the way, ``:='' means ``define'' here.) Names are usually important for understanding. But if you ask it is really substance or not, then sometimes it does not matter. There are no difference between f or g in this example. In the notation of λ expression, we can read λx.2x as ``the function which input is x and the output is 2x.'' In this way, we do not need to write a name like f or g.

We call a function as Lambda in Lambda calculus all the time. I think that is related with that ``the name is not the substance of a function.'' To concentrate this, every function is called Lambda. It does not matter the function is called as a, b, f, or g. In this way, I could imagine that there are people who are seriously thinking about functions. I assume these people have an idea, we do not want to be bothered by names, but we would like to study what the function is.

No comments: