Skip to main content

Posts

Showing posts from April, 2009

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.

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 in

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)) Noti

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.

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.

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.