2008-10-22

A machine which execute a procedure: SUCC mark I

Japanese version

Blaise Pascal made a calculator for helping his father's job (tax calculation). Usually it is painful to calculate a huge amount of accounting. I am not good at calculation. So, I thought if I have a computer, I do not need to compute anything myself. That's one of the motivation I took a computer science course in my University. Some people totally misunderstand that a computer scientist is good at arithmetic. No. If someone is good at arithmetic, why does she/he need to learn that? If a human can fly faster than sound, maybe we do not need to use a plane. If people can communicate without speaking between thousand kilometers away, why we need a telephone? I can not do arithmetic, therefore I learned computer science. So, let's make a computer.


Figure 4 is a computer SUCC mark 1 by Sirius Cybernetics corp. This computer gets one Church number as an input, and outputs another Church number. This computer does not understand what the number is, but just execute one procedure (it will be shown up soon). It is a kind of vending machine. As a vending machine can calculate changes, this SUCC mark I also can compute something.

SUCC mark I runs computation as the following.



1. Figure 5. Initial state. Given an input Church number on the 'input' board. Here, Church number 0 (Zero) is the input as an example. (Do you remember that the Church number 0 is one circle and one square?)



2. Figure 6. The input is copied on the output. SUCC mark I scan the input and choose the same tile from left to right.



3. Figure 7. The calculation result. After the copy, SUCC mark 1 puts one more square tile at the end of the output.

As you see, when we input the Church number 0, then the machine outputs Church number 1. The same procedure can generate 2 from 1, 3 from 2, and so forth. Finally, we have a computer! and please shut up, Marvin.

Marvin: ....

It seems ridiculously simple, but this is the basic of our computer. By the way, SUCC represents Successor. This is a successor number generator. As we have already seen, this function and Zero generates all natural numbers. We could add more procedures. Next time we will see a little bit more complex computation.

2008-10-18

Church numerals continued

Japanese version

Last time, a circle was a symbol to represent a number. But, there is no such thing (a symbol to represent a number) in the Peano's axiom. Peano's axiom only define a Zero and a successor. we employed a square to represent Zero. But when we tell two numbers to a machine, we can not distinguish two numbers if we have only Zeros. See Figure 2. Therefore, we use a circle as a delimiter. One could say, we can use a space, but we also need to tell a space to a machine, otherwise any machine can not know a space exist. We need something like a number 0. 0 means ``there is nothing.'' If we write down nothing, how we could know something is missing. If we put 0, then we know nothing actively exists. 0 can represent ``existence of nothing.'' This is an excellent invention of human being.



By the way, speaking about space, there is no space character in Japanese. I think also Korean and Chinese do not have space character. Therefore, a processing of Asian text starts with finding words. A space character represents no character, but existence of no character makes so easy to find words. Space character is also a brilliant invention. I remind myself that Lao-tsu's ``usefulness of
uselessness.''

The Church numerals, one of the representations of numbers of lambda calculus, are defined as follows:

0 := λ f x. x
1 := λ f x. f x
2 := λ f x. f (f x)
3 := λ f x. f (f (f x))

It seems these are not numbers, but these satisfies Peno's axiom, therefore, these are numbers. Because no matter what it looks like, Peano's axiom defines what the number should be. If the condition is satisfied, they are numbers. That's the rule. If you closely look this numbers, the number of 'f' is represents the number. Zero has no `f,' 1 has one `f'. Two has two `f's . Three are also the same. This is the definition of Church numerals. As you see in Figure 3, this is almost the same as Figure 1's number. (Almost means both f and x are square. Different things should have different symbols. This is not good, but this is for computation.)


Marvin: What a long story to define just NUMBERS! You spent nine articles to define it. In the Wikipedia's lambda calculus page, when the Church numerals are defined, it has already defined all formal lambda expressions. You said just one is one square, two is two squares, ... this simple thing took so long. It is ok to explain something simple, but it is so pedantic. You have not even defined how to compute numbers. I have experienced five universes time. But this is too slow for me. So depressed.

But Marvin, this is the way I understand the Church number. I am a armature mathematician, so I could not understand if only the definitions of Peano's axiom is presented. It is so abstracted and dry for me.

Marvin: Doesn't matter. I am tired. You defined numbers. Now what? Roman number is better than this for computing. How can you write 2008? My co-processor will be depressed.

OK. We have now numbers, let's compute it... so functions.

2008-10-15

DDR Gebaeude

Last Saturday, I walked around the city with my friend. DDR buildings are a bit chilly... Or it is already winter here.

2008-10-14

Church numerals

Japanese version

Last time we were talking about how Peano defined the natural number. Because Lambda calculus defines the numbers based on that. Mathematical formulation makes the discussion (proof) more exact, this ``exact'' is important for mathematician. But, the formulation causes increasing the exactness, which means, there are no such thing, like ``You know about the numbers, just do something like calculation in appropriate way.'' Because even every single obvious issue should be defined in formulation. As the side effect, we could execute these rules on a machine --- we can make a computer! That's the interesting point for me.

There are many ways to how to implement a computer as a machine. Pascaline and Charles Babbage's differential engine are gear based. Here our base is Peano's axiom.

Before Marvin points out, this explanation is Masahiko Sato and Takafumi Sakurai's ``Basic theory of programming.'' (By the way, It is not so convenient that I left all my books in Japan. In Japanese version of my blog is written by SKK input method, which was first implemented by Masahiko Sato.) Prof. Sato's class was tough. At least I had totally no idea if I only attended. However, when I asked questions, even though it is extremely stupid questions, he answered the question until I said ``thanks I understand.'' The problem is the class was so tough, therefore I do not have any questions, except ``What can I ask?'' It is very difficult to figure out what is I don't figure out.

Here, I use a circle as a sign of ``This is a number.'' I use a square as Peano's ``zero,'' and a successor number is represented by reputation of ``zero''. See Figure 1.


As you see, there is no one or two. We have only a sign of ``number'' and ``zero.'' Our number system is depends on base 10 system. We could also use Roman number system, Babylonian system, or Chinese characters. These are all for human's convenience, and all of these number representations are not substance. Zero is sufficient to represent the Peano's system. I use zero as a square, since I would like to stress that ``zero'' is also a name for something. It does not matter if it is ``hoge,'' or "Petrosiliuszwackelmann." Then I use a square as following the Prof. Sato's book.

When you see one square, then I understand you want to call it one. I agree with that. But, we need to represent Zero. The usual number 0 means ``There is nothing here'' -- nothing exists here. If we want to start the number zero, then I think this is the way. Although, Peano's system can start any number of natural number, one, two, or 42. It does not matter. But still I would agree with Figure 1's zero looks like one.

Next time let's start with why we need a circle instead of using only Zero.

2008-10-13

Defining natural numbers 2

Japanese version

This is continued from the last article. Please refer the Peano's axiom in the last article.

The second definition means that we can create a next natural number from the current one. This function creates a successor number from the current number, therefore it called ``successor'' function. This defines ``plus one'' function. We have already the first natural number, zero, then we can make a successor number from zero. This successor number is ``something'' of zero. It is usually called one, but not necessary. This definition just said, it is something different from zero. We have now:

1. there is the first number,
2. we can make a successor number from a number.

Out of these two definitions/rules, it seems we can make the whole natural numbers, but this is not enough for that.

The third definition said that there is no loop of successor function, i.e., if you repeat the successor function staring with x, the result of them will never return to the number x. This seems natural since x + 1 + 1 ... + 1 != x. There is such mathematics (modulo), however, Peano's natural number does not think about that. For example, there are such system, like 12 + 1 = 1, or 31 + 1 = 1. If you think this is odd, think about your calender. Amazingly, the next day of December 31st (31.12) is January 1st (1.1). If you look at the month part, 12 + 1 = 1 and days part is 31 + 1 = 1. Time has also similar system, next of 23:59 is 00:00, means 59 + 1 = 0. Some might say that is not a calculation, but, there is such calculation in your computer. Someone may think 1 + 1 = 2 is the simplest mathematics. I think it is not so simple.

The fourth definition said that the same number's successors are always the same. In other word, different two numbers's successors are never the same. The calender example also does not follow this rule. 31 + 1 = 1 for January, 28 + 1 = 1 for February, 30 + 1 = 1 for April. 31, 28, 30 are not the same number, but the + 1's result are all 1. This definition tells you that the calender system never happens in the natural number.

I think now Marvin want to complain my explanation since these are so obvious and not need to explain. The last definition said all the natural numbers follows this rule are also the natural number. (This is the base of mathematical induction.)

Marvin: ``By the way, this explanation is quite similar to the explanation from Kouji Shiga's book. You should refer that.'' That's true. This explanation comes from ``A story of growing mathematics.'' Unfortunately, I do not have this book now. I left them Japan... I like all the Shiga's book. When I found out that he had a open seminar at Yokohama, I visited his class. But it took four hours to go and back the class by train. It was fantastic classes. When I left Japan, I regret that I could not take his class anymore.

Peano's axiom reminds me two things: Lao-tsu and Wittgenstein. The coincidence works again for the guide. The section 42 of Lao-tsu starts with ``Tao is created by one. One bears two, two bears three, and three bears everything...'' Excellent.

I have no idea about what Wittgenstein try to explain, however, his word: the words are just projection of the world. I think it sounds right. Lambda calculus projects back this words to a machine. I.e., logic (logos) is projected to the world again. So far, I just describe calculation with words. But no matter what words I use, this can be run on a machine, which belong to the world. I am satisfied when I see the logic really runs on a machine. Then I feel this is not just meaningless words.

Next time, let me describe the natural numbers by lambda.

Blaues Wunder


Japanese version

A few weeks ago, I visited Dresden and saw a bridge called Blauses Wunder. The formal name of the bridge is Loschwitzer Bruecke, but even this name is on a map. The literal meaning of this word is ``Blue Wonder,'' but in German, there is another meaning -- very surprising in a bad way. This is bit strange... The originally this bridge was blue. Dresden is a beautiful city. I have friends there, so I visited there several times.

I first know the word, Blauses Wunder in the book from Preussler, ``Der Raueber Hotzenploz.'' (Am Ende der Spur sollte jeder von beiden sein blaues Wunder erleben, dafuer hatte Hotzenploz vorgesorgt. in Chapter 6)







Größere Kartenansicht

2008-10-08

Defining natural numbers 1

Japanese version

Peano defined natural numbers.

He actually described properties of natural number, not seems to try to define the natural numbers. But these are somehow the same. The following five definitions are called Peano's axiom which defines the natural numbers. If you are not familiar with mathematical notation, it might be hard to get what they said. But, the basics are not so difficult. These are copied from Mathworld.
  1. Zero is a number.
  2. If a is a number, the successor of a is a number.
  3. zero is not the successor of a number.
  4. Two numbers of which the successors are equal are themselves equal.
  5. (induction axiom.) If a set S of numbers contains zero and also the successor of every number in S, then every number is in S.
The first definition said, there is the first number called Zero. Here it said Zero, but it does not matter which number is. It should be a ``something.'' However, you may ask ``What is something?'' It is really just ``something.'' Why we need to say the first number as Zero? It is fine as One, 42, -1, or x... You can write in Japanese ``Rei'', or in German, ``Null.'' In short, this is ``something.'' But, one thing I would like to make this clear, this ``Zero'' is not the number 0. Because we want to define numbers, so we do not know any numbers, even 0. It is just something the first number and we can just call it Zero. Personally, I prefer to write x since it seems more ``something.''

Definitions are similar to rules of a game. Therefore, we should not think about why this is defined. That is just a starting point of the discussion. It is easy to imagine that this is hard for especially someone who is not familiar with mathematics. This is the same as rules of some game, like soccer game, ``A player is not allowed to touch a ball by hand except goalkeepers.'' If you ask ``Why a player can not use his/her hands?'' Then one can only answer that ``That's a rule of the soccer game.'' This is also true as the rule of chess, shougi, or go... If there are ten kind of games, there are ten kind of rules. Mathematics is the same, there are many rules of mathematics and each rule makes different mathematics. We can make arbitrary kind of mathematics, only necessary condition is such mathematical system must be consistent. But, most of the arbitrary rules can not make interesting mathematics. ``Interesting'' is quite subjective word and it seems not so fit to mathematics. But, many can feel that. I sometimes encountered that some people believe that the mathematics is a kind of truth in the universe. But, mathematics is nothing related with how the universe is. That's the physics' area. However, well established mathematics can describe our universe well. I am fascinated this interesting point of mathematics. It is like a game/sport that has a well established rule are so fun and interesting. As there are many kind of games and sports, there are many mathematics and each mathematics may have different rules. Although, many rules can be shared in mathematics. One can make up new rules and can create a new sports. But it is difficult to create a new interesting sports. It is the same in mathematics, you can create own mathematics easily by making up several definitions, but it is very difficult to make an interesting new mathematics.


By the way, one day for one small thema is still too long for blog for me, I will keep an article short from now on.

2008-10-06

Stereo Shadow


One of my friends is an artist. Recently, he made an article, ``Stereo Shadow.'' He used two light sources, one is blue, the other is red. Audiences see their shadow with wearing a red-blue filter glasses. Then they can observe their own ``3D'' shadow in the wall. There were several exhibitions of this in Japan. I heard he has prepared a video of this, and I am looking forward to seeing that.

The black dots in the picture is for audience's safety. He found some children try to touch their shadow and hit the wall without noticing. So the dot shows ``Here, there is a wall'' sign.

2008-10-05

Motivation of Lambda calculus

Japanese version

According to the Wikipedia's page, Lambda calculus was introduced by Church and Kleene in the 1930s as part of an investigation into the foundations of mathematics.

By the way, I am an amateur Sunday mathematician, therefore, please do not believe this blog without check by yourself. This is just I think I understand these stuffs. So I think there must be many errors. I try to avoid errors, but, this is not my profession. I am also not confident about my English. Welcome the comments.

The origin of this blog is Wikipedia. I could say in cool way, I was inspired by the Wikipedia's page. If you understand the Wikipedia's entry, I don't recommend to waste of time by reading this blog. There are bunch of interesting text around the world. When you read ``Lambda calculus was introduced by Church and Kleene in the 1930s as part of an investigation into the foundations of mathematics.'', and if you think ``I see, that's the reason of why lambda calculus was introduced. That's easy.'' then, you don't need to read this blog. But, if you think ``In 1930? It seems very recently as the history of mathematics. Why is the foundations of mathematics considered in this time? Wait, what is the foundations of mathematics? Didn't Pythagoras, Apollonius, or Euclid study the foundations of mathematics in B.C.?'' Then, you may continue to read this text.

The foundations of mathematics means that where the mathematics can start, or what kind of starting point is all right for mathematics system. Mathematics starts with a set of definition. A person should define them. One of the most fundamental mathematical object would be numbers. Also propositions and logic, how to calculate numbers would be fundamental stuffs in mathematics. These seems too obvious and many mathematicians did not care them until 20th century. Or Euclid did too good job about formulation and we needed not re-consider until 20th century.

But, why such obvious things are important at that time? Mathematicians started to think about formalization at that time. It may differ the mathematics between languages, how can we sure they are exactly the same. For example, number `1' is exactly the same in English and Japanese? Then, they wanted to define numbers. If someone want to define numbers, it should be done without using numbers. Otherwise, we can define the numbers as ``numbers are numbers.'' For example, ``Love is love,'' ``Consciousness is conscious of consciousness.'' These may be true, but, we can not use it to think about the foundations of mathematics. Then a question is how can we define numbers without using numbers. This seems paranoia, but, mathematicians are perfectionist.

I found this is an interesting idea. Because these are enough to formalized, abstracted, and simplified. We could make a machine to implement that system. If you want to create a machine to compute something, we need to make it by some kind of materials (water, stone, iron, ...). Zaphod may say with his two heads, ``You know, 1 or 2 or 3, something like that. Just make up a machine which can understand them.'' But I think this is not so easy. Numbers are such an abstracted idea. Abstracted means that there are a lot of applications. ``What is the common idea between the earth, humans, a bread, signals, Zaphod's heads, and a church?'' I can answer that ``they are countable.'' I've already said, but I have no idea how to teach the numbers to children. That's a highly abstracted idea.

The motivation of lambda calculus is to think about the foundations of mathematics. This means that re-thinking all the mathematical system from the numbers and calculus even though they seems so obvious by some kind of formulation. At that time, mathematicians are interested in more in the sanity of the mathematical system by formalization. However, this formalization is based on enough simple system and we could build a machine which can partially process the system. The reason I am interested in lambda calculus is this part ``we can build a machine of that.'' Also this is the reason that lambda calculus is the basic theory of the computer and computer languages.

Next time, let's define the natural numbers without using 1, 2, 3, ...

2008-10-04

Introducing lambda.

Japanese version

Standard mathematics books explain mathematical stuffs as definition, theorem, proof, definition, theorem, proof, .... This is quite simple and enough abstracted. Therefore, we can also explain lambda calculus in the standard way. But Marvin will sure complain that is so depressed. More abstracted theory could be more applicable to many things. It becomes less unnecessary stuffs, then, it becomes simpler and also more beautiful in a sense. The theory is to the point when more abstract.

Japanese sword seeks for the beauty in the sword itself, it never decorates with some kind of jewels. Because a sword maker/master thinks the beauty comes from the sword itself. They shamed if they need to cover a sword with non-sword component. We can find many swords, staffs, ... are decorated with gold or some jewels. I can also see some kind of gorgeousness in that, however, I prefer beauty in these kind of simpleness. A French pilot said ``A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away.'' I sympathize with this word. Also, I like the story about a ship called Vasa, which sank in the sea. The story about a project manager (a Swedish King) requested too many features to his ship. Any software comes from Sirius Cybernetics coop. has too much features and hard to use, because the project managers believe that the customers want to have new features instead of a simple and stable software. (Kode Vicious Pride and Prejudice (The Vasa) CASM Vol.51, No.9)

The beauty of mathematics is in the simpleness and abstraction. I could understand that a mathematician wants to discuss more simple and more abstract entity. But then the mathematics becomes more difficult to the usual people like me. I see here some kind of closeness. If only a few people who knows mathematics well can enjoy the mathematics, that's a bit sad for me.

When I discover some beauty, I sometimes want to keep it to only myself. If I discover some beauty which nobody doesn't know, I feel some privilege. Because I need a lot of effort to find out something beauty in mathematics, it is a kind of reward for me. If I explain them to many people and people also find the beauty, that's nice. On the other hand, I sometimes feel some kind of loneliness. Like it is not only mine anymore. Someone who loves mathematics seeks for more beauty in that, then she/he may search for more abstract form. The result becomes more substance, all the background, history, etc. will be lost. That's also the reward for mathematicians. It is pure substance, however, it is not familiar with me anymore. I do not feel that I understand that anymore.

I also prefer abandoned extra part of mathematics. Why lambda calculus is created? How it is created? What was the first attempt of that? These may be not so important after constructed the lambda calculus. ``What can lambda do?'' becomes more important. Usually ``what is it?'' is not so important in mathematics like operators are more important than some kind of substances like numbers.

Vogons in the guide are extremely officious, their relationship is dry. Only important thing is what others can do for them. ``Who'' did is no matter at all. For them, even relative is only a relationship which people knows whom. Even if their grandmother ask to help her children, they do nothing unless there is a contract. A family may be worse than bureaucracy. A dry software company only asks employees to implement a new feature. This is important of course for business. But, who did it is not so important. This means, it does not matter who did that. It is just a function of the company. However, if a company does not applicate or does not matter the people, the people usually leave such kind of company. So, Vogonism is hardly work in the human society. But it seems Vogonism is working in mathematics theory.

The important thing of lambda is also what the lambda calculus can do. However, this is a Hitchhiker's guide. Let's talk about not-so-important things, like, why lambda is created. lambda calculus is also made by a person. Therefore, there must be some kind of motivation. Marvin is the most depressed existence in the universe, he (she/it?) has no motivation at all. He is always depressed, but he even has no motivation to suicide... But, the designer of Marvin from Sirius Cybernetics coop. did not want to make a depressed robot (I think). The designers just thought if they can combine a few hundreds of genius brains, such thing should be super-genus. However they are enough to smart to design Marvin, but they are not enough smart to imagine that such super-genius is usually insane. There is a purpose of lambda. Let's talk about the motivation of lambda next time.