Lx=d: SundayResearch

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