2009-04-27

e: The meaning of the base of natural logarithm's definition

Base of natural logarithm appears almost everywhere in mathematics. Many of the sciences also use this number. When I came Germany, I found it on the 10 DM note. 10DM note has a portrait of Gauss. I saw why Germany's science level is high when I found a graph of normal distribution on a 10 DM note. When children got allowance from their parents, they would ask ``what is this curve? who is this?'' Then the parents would answer ``This is Karl Friedrich Gauss. A great mathematician. This curve is called normal distribution. It represents....'' I'm not sure how accurate my imagination is. I think Euro is a good idea, but I missed Gauss on a note.

Famous transcendental numbers are e and π. It is well known how the π is defined (circumference/diameter), why e's definition is
was not on my high school text book.

I found a slide of this explanation and put the link here with the author's permission. Thanks a lot.

2009-04-09

Conclusion of lambda

Japanese version

Recently I saw this advertisement, ``For the finance specialists: Let's start from the simple thing.'' I assume the simple thing means, 1+1=2. I try to explain in this blog that how to teach 1 + 1 to a machine. I took more than eight months and yet not quite complete. (By the way, this is a tobacco advertisement.)


For human beings, this seems simple. But once you want to teach what 1+1 means to a machine, you must know more about it. For example, we discussed what is the numbers, and we represent it as Church numbers since a machine does not know what the meaning of '1' or '2''s sign. Someone may think this is paranoia since this is so natural.

I believe ``natural'' does not mean simple. It is just familiar to us. It is not simple at all for me. Some of you might feel it is natural to spend time with your family or your lover. But it is just you are familiar with that, it is not simple thing. It is important for me to see back into the natural things.

I would like to conclude this Hitchhiker's guide to λ calculus at the moment.

One day, I searched lambda calculus in Wikipedia. It said, ``it can be verified that PLUS 2 3 and 5 are equivalent lambda expressions.'' on the PLUS function. However, I did not understand how it works. I needed a large help of my friends. I do not want to forget about this. This is the motivation of writing this blog.

We talked about what is λ calculus, why people care about that, and several concrete examples. I hope this blog could help the people like me.

But this is not everything about the λ calculus. λ calculus is deep, I am hardly just open the door of this area. I still do not understand combinators. If I could understand it, I would like to continue this blog. I learned that writing is learning or teaching is learning. Also I learned that I could write an article only if I really like it.

I try to keep this article more understandable in informal way. I did neither mention about formal λexpression construction method, nor conversion procedure (α-conversion, β-conversion, and η-conversion). If you wan to know further, Wikipedia would be a good starting point.


Acknowledgments

Thanks to Uchida to give me the cue to write this blog. Thanks to my friends Hoedicke and Rehders to help to understand the examples. Thanks to Maeda who gave me an implementation of Y combinator. This blog is dedicated to my friend Tateoka. I wanted to show him this blog, but unfortunately it is not possible anymore.

SUB

Japanese version

These series of the examples might be not so fun if you don't try to apply them by yourself. If you do not follow them step by step, these are just a bunch of equations. Therefore, I recommend to try it.

We will define the subtraction using PRED function.

SUB := λ m n. n PRED m

SUB 3 2 = (λ m n. n PRED m) (λ f x. f (f (f x))) (λ f x. f (f x))

= (λ n. n PRED (λ f x. f (f (f x)))) (λ f x. f (f x))

= (λ f x. f (f x)) PRED (λ f x. f (f (f x)))

= (λ x. PRED (PRED x)) (λ f x. f (f (f x)))

You see that the PRED is duplicated as the second argument (= 2). This is the trick. If the second argument (subtrahend) is ten, then PRED is repeated ten times.

= PRED (PRED (λ f x. f (f (f x))))

This is PRED (PRED 3).

= PRED 2

= 1

Therefore, 3 - 2 = 1. We can do subtraction.

PRED

Japanese version

We have addition and multiplication. Next I would like to subtraction. But, we do not have minus numbers of Church numbers. Because we construct the numbers by number of f-s. For simplicity, we do not think about minus numbers here. If you want to know more, you can look up Wikipedia.

We prepare PRED before we go to subtraction. The PRED (predecessor) function generates one Church number before the input number. Here we will not think about before the number 0.

The definition of PRED is

PRED := λ n f x. n (λ g h. h (g f)) (λ u. x) (λ u. u).

Let's compute PRED 2.

PRED 2 := (λ n f x. n (λ g h. h (g f)) (λ u. x) (λ u. u)) (λ f x. f (f x))

= (λ f x. (λ f x. f (f x)) (λ g h. h (g f)) (λ u. x) (λ u. u))

= (λ f x. (λ x. (λ g h. h (g f)) ((λ g h. h (g f)) x)) (λ u. x) (λ u. u))

= (λ f x. (λ x. (λ g h. h (g f)) (λ h. h (x f))) (λ u. x) (λ u. u))

= (λ f x. (λ g h. h (g f)) (λ h. h ( (λ u. x) f)) (λ u. u))

= (λ f x. (λ h. h ((λ h. h ( (λ u. x) f)) f)) (λ u. u))

Notice, one 'f' is vanished here. Number of 'f's represent Church number, therefore, remove one 'f' is minus 1.

= (λ f x. (λ h. h ((λ h. h x) f)) (λ u. u))

= (λ f x. (λ h. h ((f x))) (λ u. u))

= (λ f x. ((λ u. u) ((f x))) )

= (λ f x. (f x))

= (λ f x. f x)

= 1


It is curious to compute PRED 0. What is the predecessor of 0?

PRED 0 := (λ n f x. n (λ g h. h (g f)) (λ u. x) (λ u. u)) (λ f x. x)
= (λ f x. (λ f x. x) (λ g h. h (g f)) (λ u. x) (λ u. u))

= (λ f x. (λ x. x) (λ u. x) (λ u. u))

= (λ f x. (λ u. x) (λ u. u))

= (λ f x. x)

It returns 0. This is a nice property of this PRED definition. PRED returns 0 if the input is 0, otherwise it returns one predecessor number.

I am fascinated that Church number itself is part of program. The number is a program here. Of course Church number is a function. Therefore, it is natural in a sense.

If we apply λ n . n (λ g h. h (g f)) to 0,

(λ n . n (λ g h. h (g f))) (λ f x . x)
= (λ f x . x) (λ g h. h (g f))
= (λ x . x)

This is part of PRED function. The output is 0. In PRED function has more terms, so I would like to stop here. The basic mechanism here is that when this part of the function apples to 0, then the first team is ignored. Since Church number 0 (λ x . x) does not have binding to 'f'.

2009-04-08

MULT

Japanese version

Multiplication is defined as the following.

MULT := λ m n f . m (n f)

Since

2 := λ f x. f (f x)
3 := λ f x. f (f (f x)),

MULT 2 3 := (λ m n f . m (n f)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n f . (λ f x. f (f x)) (n f)) (λ f x. f (f (f x)))

You can see that (n f) is copied as many as f-s.

= (λ n f . (λ x. (n f) ((n f) x))) (λ f x. f (f (f x)))

(n f) is copied the first argument (=2) times. The second argument (=3)
is replaced with n of (n f).

= (λ f . (λ x. ((λ f x. f (f (f x))) f) (((λ f x. f (f (f x))) f) x)))

= (λ f . (λ x. (λ x. f (f (f x))) (((λ x. f (f (f x)))) x)))

= (λ f . (λ x. f (f (f (((λ x. f (f (f x)))) x) x))))

= (λ f . (λ x. f (f (f (f (f (f x))) x))))

= (λ f . f (f (f (f (f (f x))))))

= 6


There is another multiplication definition.


MULT := λ m n. m (PLUS n) 0

I thought this 0 is just number 0 instead of Church number 0, when I saw
this in Wilipedia. This is not easy for beginners.


MULT 2 3 := (λ m n. m (PLUS n) (λ f x. x)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n. (λ f x. f (f x)) (PLUS n) (λ f x. x)) (λ f x. f (f (f x)))

You can find the similar pattern as the first definition, (PLUS n) is
copied k-times (k = the first argument number).

= (λ n. (λ x. (PLUS n) ((PLUS n) x)) (λ f x. x)) (λ f x. f (f (f x)))

= (λ n. (PLUS n) ((PLUS n) (λ f x. x))) (λ f x. f (f (f x)))

= (PLUS (λ f x. f (f (f x)))) ((PLUS (λ f x. f (f (f x)))) (λ f x. x))

The underline part, PLUS 3 0 is 3 (= 3 + 0). Therefore,

= (PLUS (λ f x. f (f (f x)))) (λ f x. f (f (f x))).

This is 3 + 3, then,

= 6.

ADD

Japanese version

Addition is defined by the following.

PLUS := λ m n f x. m f (n f x)

Let's calculate 1 + 2.

1 and 2 are

1 := λ f x. f x
2 := λ f x. f (f x),

respectively.


m n f x. m f (n f x)) (λ f x. f x)(λ f x. f (f x))

= (λ n f x. (λ f x. f x) f (n f x)) (λ f x. f (f x))

= (λ n f x. (λ x. f x) (n f x)) (λ f x. f (f x))

= (λ n f x. f (n f x)) (λ f x. f (f x))

= (λ f x. f ((λ f x. f (f x)) f x))

= (λ f x. f ((λ x. f (f x)) x))

= (λ f x. f (f (f x)))

= λ f x. f (f (f x))

= 3

Therefore 1 + 2 = PLUS 1 2 = 3. It seems a magic. But the principle is the same as the Pop1. Church number represents numbers by the number of 'f's. Therefore, addition is basically concatinate the numbers.

If 1 = f and 2 = ff, 1 + 2 = f + ff = fff. In the sama way, for example 3 + 4 = fff + ffff = fffffff = 7.

SUCC1

Japanese version

Now we are ready to calculate SUCC 1.

SUCC 1
= (λ n f x. f (n f x))(λ f x. f x)

= (λ f x. f ((λ f x. f x) f x))

= (λ f x. f ((λ x. f x) x))

= (λ f x. f (f x))

= λ f x. f (f x)

= 2

SUCC 1 is 2.

The red color characters are processed at each line.

In case if ((λ f x. f x) f x)) is not clear, we could change the
variable name more unique to distinguish.

((λ f x. f x) f x)) is the same to ((λ g h. g h) f x)).

((λ g h. g h) f x)) ... f is replaced with g.

((λ h. f h) x)) ... h is replaced with x.

(f x)

I hope this is not ambiguous anymore.

2009-04-07

succ -- Apply numbers (Cont.)

Japanese version

I could not update the blog for a while, since I was in Muenchen for a week.

(λf x. x) f x

is

f x. x) f x
... remove f since f is not bound.

x. x) x
... Input x, output x.

This

(λx. x) x

is

x,

Therefore,

(λ f x. f ((λf x. x) f x))

is

(λ f x. f (x)).

Although parentheses '()' represent priority of the expression, there is not so much meaning in this case. Then lazy mathematicians will write it as

(λ f x. f x)

Almost, but not yet. We can remove the outmost parentheses also.

λ f x. f x

Now, this is Church number 1. Therefore, SUCC 0 is 1.

Finally, it was a long way, but we compute the SUCC 0 in the lambda expression way. Let's move on to SUCC 1.