Lx=d: SundayResearch

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...

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.

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...

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. ...

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.

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.

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.

Japanese version Let's compute the SUCC function one by one. First time, I was confused and I tried to use `0' or `1' as a number. But here, a number is a Church number, then 0 is (λf x. x). You can see I am a totally amateur. Please keep the left-associative in mind, SUCC 0 := (λn f x. f (n f x)) (λf x. x) = (λ f x. f ( (λf x. x) f x) ). Because of left-associative `n' is (λf x. x). Here the underlined part, ((λf x. x) f x)) Can you see that any `f' will vanish? For example, One argument function (λf. 3) means, f(x) := 3. Therefore, this function is always 3 for any `x.' Such variable `x' is called free variable (or the variable does not bound). It is like Marvin in the Heart of Gold. Anything does not matter for Marvin. Zaphod always forgets him. But this free variable is necessary as Marvin in Hitchhiker's guide to the Galaxy. The vending machine gensym3141 does not bound any variables until you put your credit card. Without credi...

Japanese version A definition, like function application is left-associative, is alike a rule of a sport. One of the rules of basketball is a player with the ball must dribble a ball when the player moves. Why is it? Because it is a rule of the game. If someone dribbles a ball in baseball, it does not make any sense (in case baseball makes sense). If a soccer player uses hands except the goal-keeper, it is a foul. Why is it so even they all use a ball? That is out of question. It is the rules of the game. Mathematics also has the similar aspect. ``Why is it left-associative?'' ``Because it is a definition. (means that's the rule.)'' Unfortunate starts when someone teaches this mathematical rule is the unique and unalterable truth. If one believe 1+1=2 is the unique and unalterable truth, then s/he could not understand mathematics at some point. For example, there is a mathematics 1+1=1. This mathematics is used in nowadays computer. Nowadays computer widely uses bin...

Japanese version Last time, we told about a rule, function application is left-associative. First of all, why we need to think about something associative? Because it is not so useful when the answers are different even the expressions are the same. If one computes 1-2-3 as (1-2)-3 (=-4) and the other computes 1-(2-3) (=2), the values are different. Someone might think useful if a calculator gives different answers every time, however, I assume many people could agree such calculator is not so useful. We need to define associativity if the input expressions are the same, then the answer are also the same. This is the reason why we need to think about associativity. Then the next question might be why we use left-associative? Actually this is just definition and it does not matter which one we take as long as it is defined one of them. Someone defined it as left long time ago. I think I use to use it for a long time, then it is almost natural for me. Maybe it is unnatural I fell it natu...

Japanese version I forget to explain one rule that function application is ``left-associative.'' f x y = (f x) y, The function is processed from left to right. For example, 1 - 2 - 3 is not a λ expression, but it is a left-associative example , means (1 - 2) - 3. Enclosed by parentheses '()' is calculated first. Therefore, 1-2-3 = (1-2)-3 = -1-3 = -4. If this is right-associative, 1-2-3 = 1-(2-3) = 1-(-1) = 2. Please note the answer is different. If we write this function as a λ expression, (λx. λy. λz. x - y - z) 1 2 3 This concludes (λ x. λy. λz. x - y - z) 1 2 3 ... apply x to 1 = (λ y . λz. 1 - y - z) 2 3 ... apply y to 2 = (λ z. 1 - 2 - z) 3 = (λ z . -1 - z) 3 ... apply z to 3 = -1 - 3 = -4. x = 1, y = 2, and z = 3 if this is left-associative and x = 3, y = 2, and z = 1 if this is right-associative. We use left-associative in λ calculus unless it is explicitly mentioned.

Japanese version An important part of Peano's axiom is the successor function. Do you remember it? The successor function is a fucntion to make a successor number of the input number. We described a machine called ``SUCC1'' as an implementation of the successor function. When we define numbers as the answer of what is the numbers, we could define numbers by enumerating all numbers. But, mathematicians are lazy, or must be lazy, and it is quite difficult to enumerate all the numbers which is infinite. Mathematicians' answer is that: 1. create the first number, 2. create a function which generates the next number. Then each mathematician applies them to generate an arbitrary number. They do not use concrete examples 1,2,3, ..., but, they abstract the property of numbers and use the property to define the numbers. Do you also remember the story of abstraction? A generator of ``successor number'' is a function, thetefore it is a λ. If we have the first number and th...

Japanese version We have already made Church numbers by boxes. It is about how can we define the numbers for a machine. I wanted to talk about computation, for that, I needed numbers. Without numbers, it is a bit hard to talk about computation. Marvin complains the story line was not natural, but the author's writing skill level was apparently not enough to make it natural. As we have already introduced Church numbers, I will show you them again. I would like to use them later. 0 := λf x. x 1 := λf x. f x 2 := λf x. f (f x) 3 := λf x. f (f (f x)) Please remember, the number of 'f's is corresponds to each number. For example, the number 0 has two inputs, f and x, but the output is only one, x, means no f. The number 1 has output f x, which contains one f. This is like Chinese characters. The Chinese character of 1 is ``'一'', 2 is ``' 二'', 3 is ``三''. If 4, 5, 6, are in the same way, that's Church numbers. But, the ancient C...

Japanese version A vending machine ``gensym3141'' is a product of Sirius Cybernetics corporation. This machine's sales point is that it can generate infinite kind of vending machines. This machine can only provide vending machines, but, you can buy anythiFng -- a cap of coffee, a car, or a computer -- from gensym3141. If you want to have a cup of coffee, then you first buy a vending machine which sells a cup of coffee. Here, you must notice that there is a vending machine which gensym3141 can not provide. Some people easily misunderstand that a vending machine can provide infinite kind of vending machine, that can provide everything. If you are a one of them, Marvin will laugh at you. But since laughing at you does not help you, let's think about such machine a bit. The vending machine gensym3141 has a keypad, you can input a number 1, 2, 3, ... This means you can input infinite kind of numbers to gensym3141. For example, the number of a vending machine of Vogon poetry ...

Japanese version A few months ago, there was a question, what if the vending machine is broken? Since I use a vending machine as an analogy of a function, we could also think about a broken function. First of all, what is ``broken'' means? 1. If you put anything to the machine, nothing comes out. 2. If you put anything to the machine, the output is always the same. 3. If you put anything to the machine, the output is always unexpected. If a vending machine behaves one of them, we could say it is ``broken.'' But, a word ``broken'' is a still ambiguous. If the machine always behave one of them, such machine might just fulfill its specification. I would like to say, if the machine could not fulfill the specification, then I define the machine is broken. If we agree with this definition, we can only say a machine is broken or not by looking up the specification. λ expression is enough powerful to express these specifications. 1. Nothing comes out: First we define or...

Japanese version In λ calculus, a function only has one argument. An argument is a parameter of function, or an input of function. We can talk about more than one argument case later. When the argument value is determined -- this means when the input is determined --, put the value to right to the λ expression (= function), and apply the function to the value. In case of the vending machine, someone just put the money into it. The machine waits the money to be feed, once some money is in, it computes the output. Many of the functions are also similar. They wait an argument. When an argument is determined, the computation starts. The word ``apply'' seems a big word. I think this ``apply'' is not so far from ``assign'' the value. However, we can assign a non-value, or we can assign another function, so it is better to use to be the word ``apply.'' Let's see an example of applying a function. f(x) := 2x λ x. 2 x These two functions are the same. I w...

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 huma...

Japanese version Let's get back to this ``(_)''. ``(_)'' represents ``something'' here. Marvin: Again, ``something''... I am tired. You may ask ``what is something?'' I understand. But the answer is still ``something'' Or ``something of something''. For example, if I limit the subject to money, I could say this something is ``something of money.'' If you put ``some(thing) of money'', exact the same ``some(thing) of money'' will be out. This is ``λ(_).(_).'' See figure 1. The output amount never larger or smaller than the input. Therefore, if you put 100 Altair dollar, the output is 100 Altair dollar. If you put 200 Altair dollar, the output is 200 Altair dollar. If you put 'some' Altair dollar, the output is exact same 'some' Altair dollar. This is the meaning of ``something''. I can not say more exact since it is abstracted. Some schools teach this ``something'' ...

Japanese version The function itself is more important than the name of function. First we need to recognize this is a function or not. In the lambda calculus, The symbol λ is used as a marker of a function. Since the name of function is not so important compare to its substance, we should be able to represent the substance of the function without the name. If we need a name, we could make a connection between the name and the substance of the function. (It is called binding.) Once we used a vending machine as an analogy of a function in this article. Because we can put something into a function, then we can get something out from the function. If you put some money to a vending machine, then you can get some goods from it. I think the simplest vending machine is that if I put something in, then I can get it out without any change. Such function gets a ``something'' and outputs ``something (the same thing I put).'' If you input (_), then your output is (_). Let's w...

Japanese version In mathematics, we use function names as f , g , and so force. When we have more than one function, these names f and g are useful to distinguish them. I assume the name f comes from English ``function'' in English (an old language on a plant called Earth.) But for any function we made, we wrote it as f:= ... except very special functions. We always wrote f:= ... for functions, for example, f(x):= x, f(x):= x^{2}, f(x):= sin(x) , and so on. It does not matter to write f:= ... or g:= ... . The substance part is this ... part, f is just like a tag of a parcel. If we can get a parcel, the tag does not matter. Every planet has city halls if there are governments. Every planet has banks if there exists money. The people living these planets must wait in a long queue to get the service. This is usually defined by a law. If these services violate the law, i.e., they did not make the people wait, they will be arrested. Surely your planet would be the same. Mo...