Masahiro Miyakawa
A Memory of Andrei Petrovi´c Ershov
"I wrote about people whom I met with by destiny"
(I.G. Erenburg, People, Years, Life, Moskva, tom. 2, 1963)
It was a day near the end of 1975 that we invited Andrei Petrovi´c and Nina Mikhailovna for a dinner to our apartment house on the Morskoi street. I was given a book "The destiny of a man" by Mikhail Sholokhov as a present. Indeed, looking back my life, I notice that many things are set just by destiny.
It has passed 16 years since Andrei Petrovi´c has gone and my age already exceeded 3 years over his age. Overlaying the years I lived upon years he lived, I can realize how influential and productive he was. He was able to see things as they were and to express them precisely in the languages understandable to many other people. He was thoughtful. He left many things for us.
I have met him on five occasions; in May 1973 when he visited Japan for the first time[2], during our family’s stay in Akademgorodok from October, 1975 till August, 1977, in August 1979 when I visited him on the way to Szeged for a conference, in the autumn of 1980 when he visited Tokyo for IFIP conference[3], and on July 1st-5th, 1987 when I visited him on my way back from FCT conference held at Kazan. Our two-years stay in Akademgorodok is the most glorious pages in our family album, during which I spent at the Computing Center, Siberian Division of the Academy of Sciences where he was the host (I was the sixth man who stayed for a long term from Japan; the first 4 are physicists and the previous one is an archaeologist who stayed for 2 months). I have written an article in a Japanese journal on my stay [5].
I want to write about my researches which started while I was in Novosibirsk and ended long after my return to Japan in rather, from my standpoint, a dramatic way. I want to share my good luck with you which originated from Akademgorodok.
At that time I have been engaged in an optimization of decision trees which appears in many situations related to "branching". For example, it appears typically in identification of patterns: Given a set of blood samples, you have to classify them into 4 blood types by testing their properties (tests to separate samples are given). The problem is to choose a first test so that you can classify the entire set of samples in a minimum number of tests (so the test may be called an "optimal test", and my finding is about this topic though I used the word "variable" instead of "test"). This problem is an extension of optimum digital search trees which I have considered successfully before, and so I was very eager to solve it. However, the problem is a difficult one which allows no efficient algorithms I have expected vaguely. Indeed, Victor Sabelfeld showed me that this problem belongs to CoNP when I talked him about this problem (the jointwork is my sole publication in Novosibirsk). I remember that it was one cold day that I heard for the first time about NP problems on which Mark Trakhtenbrot was talking with someone while we were standing near each other in a long queue at the cafeteria "Ve-Ce". I had heard about NP problems so far while I was in Japan, but I could not have a concrete image of the problems. Apart from this optimization problem, I started a study of program schemata with Volodya Itkin under his guidance. But all these problems I could not lead to a concrete result, so my "stagirovka" (research fellowship) in Novosibirsk ended without any result and I came back to ETL (Electrotechnical Laboratory), Japan with empty hands. This was a painful event and I was deeply hurt my self-respectiveness. (It is a pity that research activity with Volodya ended by his sudden death in 1991 without any publication, and similarly I ended without any coauthorship with Andrei Petrovi´c by his early death in 1988.)
From 1977 to 1983, those years just after my return, was the most painful struggle in my research life. However, in early 1983 I experienced a dramatic theorem finding, which shed a glorious light on my stay in Akademgorodok and turned it into a bright memory. I am telling you the story referring to my diary.
At that time as a research scientist at ETL I was engaged in the theory of closed sets (clones) of three-valued logical functions as well as the construction problem of a minimum decision network by branch and bound method. For the first problem I managed to enumerate all bases of three-valued logical functions and could prove that the maximum number of functions of a base of three-valued logical function is, unexpectedly, 6, rather than 7 or more which had been suggested implicitly by the late Prof Sergei V. Jablonkij in his 1954 paper (this result became a chapter of my dissertation). I could report this computational result at Szeged in 1979 (in the meanwhile I met Prof. Sergei V. Jablonskij and Prof. Y.I. Janov only once at the conference which, I guess, has lead me invited later to come and report in the conference at Kazan in 1987). For the latter problem I reported an algorithm in 10th IFIP Conference on System Modeling and Optimization, held at New York City in Aug.31-Sep.4, 1981. However, I could not make the result into a journal paper (there was not enough material as a journal paper). While on this journey I visited Banff for a conference to see Prof. Ivo G. Rosenberg. So, looking back from present time, I can see that there was something worthwhile for my life in these years. But at that time I was extremely pessimistic about my future. Moreover, in the personal life there was a very sad incident which has given a deep influence on my spiritual life: my aunt with whom I spent my childhood and whom I felt very close to me, was operated a cancer at age 50 and the result was the worst. As I was young and lacked experience, I could not accept her doom. In my diary for December 31, 1981 I wrote: "There was no progress this year. I had nothing burning in my heart."
For November 20-28, 1982 I have been to my native home in Kumamoto prefecture to see my aunt, and unfortunately I was injured my knee badly. I had to drag this injury in the whole my life. December 5 I had a long conversation with my aunt through the telephone. She told me that she was feeling exhausted and therefore unable to come to Tsukuba for a treatment (she chose to spend her remaining life with her family: she had a sole daughter (age 10), a very late born). January 1, 1983 I reached 40 years old and I was to recognize that I lived many years. I wrote "I wish I could work vividly and only this remains in my future life." The little progress in my professional life was a source of continuous pain in the throat and I was losing the pleasure of everyday living. The injury of knee worsened to the degree that I could barely walk; I was to consult continually with doctors. Toshiko is staying in the university hospital on the edge of miscarriage. Thus I was at the bottom in my physical, social, and professional life. In these situations the finding came abruptly. I was to write up a final report on the decision network to say "good-bye" to this "cursed" problem, and even to my professional life. I was stuck and desperate. February 11th (we are national holiday) I wrote in my diary: "I can get no new result in the optimization of decision trees," and February 12 (Saturday) I wrote: "It is not clear that dividing with one-side constancy is optimal or not". This is the first time I noticed the notion of dividing a decision table by a test which results in one-side constancy (such a test I called "semi-decisive"). Probably I have come to the point while I have been thinking about Dynamic Programming approach. On February 13, I wrote something about Hegel’s words about "originality" referring page 285 of the book by Prof. Gurii Ivanovi´c Marchuk. On February 15 (Tuesday), after visiting my wife in the hospital, from 21:00 to 1:00 I was thinking about "whether one-side constancy separation is a optimal or not." February 16 (Wednesday) was fine day but late in the night it started to rain. I worked 11 hours at ETL: "12:00-17:00" and "21:30-3:30" (there was no writing about what I was doing in the hours between; most likely I visited hospital to see my wife). Then I wrote: "I could prove that separation with one-side constancy is a sufficient condition for optimal variable. Good day! How many years have passed since 1975?" February 17 (Thursday) was rain. After visiting my wife in the hospital I worked till 0:00. I wrote: "Today I have sent a Congratulation letter for "8-ogo Marta" (International Women’s Day) to Novosibirsk."
The result was published in 1985[6]. One evening in December 1985 I went up to the 8th floor of ETL to the library to see my paper (Ivan Stojmenovi´c was visiting me and he told me to check it by myself). Reading a long list of Novosibirsk people I acknowledged in the paper, I realized that my stay in Novosibirsk came to an end, after 10 years since I touched Siberian land. The theorem I found is almost a trivial one. Only a few days were needed for a proof. After an extreme joy of finding (I shouted in the room!), soon came a feeling of deep disappointment and sorrow fully over me: Why I could not see it in 1975? What were these years of struggle and despair from 1975? I was angry at me and I have pitied on me. Stupidity! I was stupid to adhere to a single problem for so many years. But on the other hand, I believed and still believe that there is some essence of epistemological process mixed with my stupidity in my experience. After all, I have quietly accepted the years. I was glad and thankful that I could get a result. I have come to a conclusion that it was a gift from the heaven who looked on me for years of struggle and despair. Though the theorem is extremely simple (I wondered that this might be a known fact and might be reported elsewhere by someone; I was to wait for referee’s judgement for its originality), I think it is one of the few basic rules which govern the optimal dividing of decision tables. Indeed, it seems to me that, though implicit, my story (paper) says that there is no recognizable structure in the construction of optimal decision trees and hence it is inevitable to enumerate all decision trees to get an optimum one. I was given warm words explicitly by two persons on my finding: one is Andrei Petrovi´c who sent me a card specially from Novosibirsk (April 3, 1986), and the other is the late Prof. Osamu Ishii, Director of the division I belonged to, who invited me to his room to say his words.
Epilogue. My stay in Novosibirsk is becoming a history as well as my warm thought over Andrei Petrovi´c. Looking at maturity of computer science, especially the invention of the Internet by my own eyes, I understand that I am becoming old and obsolete. I feel myself like "Kˆodayuu," a wrecked fisherman who spent 10 years (1782-1792) in Siberia before returning to Japan, might have felt (the novel[1] was written by a famous Japanese novelist Yasushi Inoue; the Russian translation was given to me by Olya Ochakovskaya). Several people are already missing including Andrei Petrovi´c and Igor Wasilievi´c. I feel myself as Andrei himself wrote[4] in the last paragraph:
"I jealously felt myself obsolete and died, my ash gradually dissolving in the quiet waters of the Ganges. But a few minutes later, a saving thought came to my mind that there is no higher award for a scientist if a person’s notion became an anonymous general commodity. I cannot inhibit this thought ..."
Still, our life is continuing. We have young people to follow us. Knowing that Tanya Bulyonkova, whom I saw in 1987 as a four-year-old child, is translating the article I wrote about her grandfather[7], I feel that the rings of destiny connecting me and Novosibirsk is not broken yet at all. [I believe that rather many people have an experience of finding after a long struggle like I had. My aunt Michiko Kinjo passed away on July 19, 1983, to whom the theorem was dedicated; There was the birth of a son with us on Sept. 1, 1983; Operations were done on my knee on Sept. 7, 1984 and Jan. 17, 1991.]
I thank my Novosibirsk friends, especially Natalya Cheremnykh for their kind urging to write this memoir without which I had missed this great opportunity and my story could be lost forever.
Masahiro Miyakawa, Tsukuba
October 18, 2004
References
[1] Y. Inoue, "Dreams about Russia (Snui o Rosii)", Bungeisyunjyusya Pub., Tokyo, 1968.
[2] A.P. Ershov, S. Igarshi, T. Shimauti, S. Takasu, E. Wada, "Topics in Current Soviet Computer Science", a record of the round-table talks held on May 16, 1973 at Kyoto, bit, vol. 5, no. 9, pp.1022-1029, 1973.
[3] A.P. Ershov, "On Futamura’s projections", bit, vol. 12, no. 14, pp.1852-1853, 1980.
[4] A.P. Ershov, "Opening Key-Note Speech" (the workshop on mixed computation held by IFIP TC2 in Denmark, October 18-24, 1987), New Generation Computing, 6 (1988) 79-86, Ohmsha Pub. and Springer-Verlag; Japanese translation: "My view on scientific researches–on partial evaluation and mixed computation–," bit, vol. 21, no 12, pp.1586-1591, 1989.
[5] M. Miyakawa, "A stay in Siberian Akademgorodok," bit, vol. 10, no. 6, pp.698-704, 1978.
[6] M. Miyakawa, "Optimum decision trees–An optimal variable theorem and its related applications," Acta Informatica 22, 475-498, 1985.
[7] M. Miyakawa, "A memory of Professor Ershov," bit, vol. 21, no. 12, pp.1592-1593, 1989.