Skip to main content

Posts

Showing posts from February, 2009

lambda and name

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

function = lambda

Japanese version The first my problem about lambda calculus is that there is only one function, lambda. Actually, lambda means function, therefore, it is natural to call function as ``function'' -- lambda. This sounded strange for me. But lambda calculus's function is a bit different from the conventional function at that time, I assume they needed a name to distinguish them. Anyway, function is lambda. I don't know that why the symbol ``lambda'' is selected as representing function. There are several hypotheses, but we don't exploit it here. (One hypothesis is the lambda calculus is first started in logic. Greek `L' is lambda. But actually I don't know, so it is nice way to write that ``We don't exploit it here.'') My second trouble was why ``calculus?'' lambda calculus seems more like Algebra. In symbolic logic, these are called calculus. However, I am a amateur mathematician, I do not know about this also.

Abstraction --- Infinite can live in finite (2)

Japanese version Human has an ability to abstract each concrete numbers, like, 1, 2, 3, ... to ``(general) numbers'' by name. And we can understand that they (numbers) can include all possible numbers. This is outstanding ability of human. It is enough interesting for me that any people have this counting ability and ability of speak except in case of diseases. But a machine seems not have such ability (yet). Human can easily perform this abstraction. For example, human can have a concept of ``chairs.'' It is still a difficult problem to search pictures of chairs. Human can see a catalog book of IKEA (a famous furniture shop now in 2009) and can recognize chairs. How can we use it is also easy to be understood. A word ``chair'' includes infinite type of chairs. But, a human can recognize a new design chair of this year which never existed until this year. Similarly, lambda calculus does not treat each concrete function. It concerns all kind of functions. We can

Abstraction --- Infinite can live in finite (1)

Japanese version Here I would like to remind you about abstraction . Abstraction derives a common idea that is not associated with any specific instance from many ideas associated with instances. Because this blog is oriented to ``getting a feeling of understanding,'' I need to explain the motivation, ``why we should need to mention about abstraction?'' We introduced the idea, abstraction, because concrete instances are not sufficient. If someone can understand about what is the addition, s/he can add a pair of numbers out from infinite combination of numbers. Because any memory devices have a limit in size, there is a limit to add the numbers in finite combination. It is a strong idea that understanding we can add any number. We could design a machine that seems compute numbers by memorize the answers. This is a different approach to make machine to compute. We could teach 1 + 1 equals 2, 1 + 2 equals 3. Then if you ask this machine, what is 1 + 2? Then you can ask

The idea of next level

Japanese version So far, we saw machines that can compute numbers like SUCC1 or Pop1. Each machine executes own procedures. A procedure is a sequence of instructions, for example, what does the machine do on an input, what does the machine do to create an output. Here we intentionally limited that the machine can only execute one instruction at a time for simplicity, means there is no parallel processing. The examples of instruction are: copy the input number on the input table to the output table, remove head and tail from the number on the output table. We show the possibility of calculation by a machine which executes a procedure. The concrete examples are SUCC1 and Pop1. We can construct arbitrary machines in the same way. But, do we need to design machines for each problem? To compute addition, do we need Pop1? To compute subtraction, do we need Subtraction1? Or, can we design a little bit more general machine, that one machine can do addition, subtraction, multiplication, and div

A machine which executes a procedure ... Pop1 (2)

Japanese version I show you the instructions of Pop1 at the last session. Pop1's program is fixed, this means we can not change the program. The Cybernetics coorp. considers their software is top secret matter. Even the people working for the company can not see it. Actually developers of the software can not read that. But, if you run the program, Pop1 displays what instruction is currently executed. So we can just write them down (Figure (I)). (The references (a), (b), (c) are in the last blog.) You may find that Pop1 has only three instructions. Marvin``It's a waste to have three instructions in such a machine.'' Of course, we could construct a computer with one single instruction, which is Turing equivalent to the any computers we have. But, human needs understandings, Marvin. Please do not forget that. (There are several variations of one instruction set machine. My favorite one instruction computer is in the book, Computer Architecture: a Quantitative Approach.)