2008-12-15

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

Japanese version

It has been while. We thought about a machine which generates the next number of the input last time. Here, we have seen a procedure of ''increment one.'' We coined this procedure as ''increment one,'' like there is something meaning. Or for human, this procedure has a meaning, ''increment one.'' But, the machine SUCC 1 just moves some symbols around. I think SUCC 1 did not understand the numbers. Here is too much to think about what is ''meaning'' or what is ''understanding.'' There is a hypothesis called ''Society of Mind'' by Marvin Minsky (this is a nice book and I recommend this.) which said a complex combination of simple functionalities creates intelligence, or you can not distinguish such complex thing from an intelligent thing. But SUCC 1 is such a simple machine and I believe I could safely say it has no intelligence. (By the way, are there any relationship between Marvin Minsky and the robot Marvin?) Although human being prefers that a machine performs something meaningful, it does not matter for the machine (or a machine can not matter anything so far). Performing a procedure becomes a computation. It is not necessary to understand what the computation means to perform computations.

SciFi novel usually describes this as a problem. A machine just executes its instructions without any understanding. We can make any dangerous machine (from Cordwainer Smith, The Instrumentality of Mankind's Menschenjager to a movie Terminator, and so on) Only moral can stop this. My favorite is ''Variant 2'' by Philip K. Dick, but it is too much here, so back to lambda calculus.

Figure 1 shows the machine POP1. POP1 can execute three instructions.



Figure 1: Pop1

(a) Copy input to output: Copy the contents of input table to the output table. (Figure (a))
(b) Remove head and tail: Remove head and tail on the output table (Figure (b))
(c) Add head and tail: Add a head and tail to the number on the output table (Figure (c))





These instructions are always valid if the input is a Church number. If the input is not a Church number, POP1 casts an error, usually it gets angry and throws the numbers to you. Sirius Cybernetics Coop.'s manual states that ''Please put a helmet on your head before running the program of POP1.''

Next time, let's write a POP1's program using these POP1 instructions.

2008-12-10

Three guests in a restaurant... meaning of computation (1)

Japanese version

Several weeks ago, one of my friends visited me. We told about lambda calculus and the meaning of computation. Lambda calculus tried to define the computation only in a formal way without thinking its meaning. On the other hand, it is usually important what I am computing in every day life. Interestingly, I started to think about the meaning of computation more deeply when I think about how-to-not-to-think-about-the-meaning. I think something I start to understand when it was missing.

There is a film called ``Paper moon''. In the film, there are several cheating methods which are good examples of using misunderstanding of meaning of the computation. If I remember correctly, a classic Japanese Rakugo, ``Tubozan'' has the same tricks. There is also a good example of how a physicist connects the meaning and computation in a book, ``Surely You're Joking, Mr. Feynman!.'' In this article, ''three guests in a restaurant''is a famous story, but even my friend still needed some time to understand what the problem is

There are three guests in a restaurant. They took a course menu and it costs 300 Euro. A waiter collected money from the guests and backed to the kitchen, then the master said, ''Today is the anniversary day of the restaurant, so the course costs 250 only.'' The waiter came back to the table, but, he thought, ''50 Euro is hard to divide by three persons.'' Then, he said ''Today is our restaurant's anniversary day, so 30 Euro back. Each can get 10 Euro.'' The guests thanked the waiter and left the restaurant. The waiter felt a bit guilty, but, he decided to forget it. However, he realized a bit odd. ''Each paid 90 Euro, so the sum was 270, I have got 20 Euro from them. But the sum is 270 + 20 = 290 instead of 300Euro. Where is the 10 Euro?''

I actually thought this works only in Japanese. But, that worked in German. Later I tried another friend with in English, it seemed working. You might figure out what is wrong here. Even so, it is hard to make a good explanation. If you did not know this story, please think though it.