Donald Knuth: how I started analyzing algorithms and for the sake of this I went to the USSR (37.91.97 / 97)

“Andrey (Ershov), imagine how cool it would be to organize something like a pilgrimage, where programmers from all over the world could come to Khorezm and celebrate the birth of this concept.”
- Donald Knut persuades Ershov to organize an international symposium

Knut and Ershov

In autumn 1967, a conference of mathematicians was held in Santa Barbara, perhaps this was the same year that I also attended a conference in Chapel Hill. I met many people who stimulated me, and there were many interesting problems that we should discuss with each other. But when I got to the conference in Santa Barbara, I realized that this was my only chance to do research. I did not attend lectures. I just sat on the beach and wrote my article on attribute grammar right during the conference. But I attended dinners. I remember how someone asked me what I was doing and I decided to be a programmer, not a mathematician at that moment.

- I think I'm going to become a programmer.
“Oh, so you do numerical analysis?”
“Not really.”
- Ahhh, artificial intelligence.
“No, not artificial intelligence.”
“Then you must be working on programming languages?”

New Area - Algorithm Analysis

In other words, I was eventually asked to write a book about the compiler. In fact, at that time it was believed that programming consisted of three parts: numerical analysis, artificial intelligence, and programming languages. The Stanford faculty was also sort of divided into three main blocks. They had three qualified exams and the like. But I said, “You know, I did a lot of research in the field of programming languages, I was the editor of the journal on programming languages, but my main interest is a little different.” And then I realized that there is no name for what interests me the most. And what do you call it?

By that time, I had already written 3,000 pages of “The Art of Programming”, printed some of them and was almost ready to publish them. And it turned out that we needed a mathematical basis for understanding the quality of computer methods. You wanted to know how good the method is, whether it can be twice as good as the other, etc. It was necessary to say not just “yes, better”, but to explain how much better and why. Therefore, I decided to make this the main theme uniting my books, to find ways to assess computer virtues. But I didn’t have a name for him.

At a conference in Santa Barbara, I realized that if I was going to explain to someone in what field I work, I should have a name for it. Therefore, I decided to call it an analysis of algorithms. I am writing a book and I can explain to people what this means. I talked with my publisher and said, “Let's change the title of the book, let's call it“ Algorithm Analysis ”.”

This idea was not approved, but in any case I decided that it would be my career, that I will focus mainly on the analysis of algorithms. This means that I will determine how good this or that algorithm or computer method is.

Once I was asked to give a lecture at the International Congress of Information Processing in 1971. I entitled the lecture as “Analysis of Algorithms”. I was also asked to give a speech at an international mathematical conference in France in 1970, and I entitled it as “Mathematical Analysis of Algorithms”. I tried to promote this term so that people understand what I do. And I am pleased to report that 10 years or so later, in the late 70s, columns began to appear in magazines and books began to appear called “Analysis of Algorithms”.

In fact, despite the fact that my publishers did not like the name, quite a few books have a similar title. But I needed to somehow name the area in which I work. If someone asked me to explain what this really means, I would say that this is just what I'm interested in.

International Symposium on Algorithms in the USSR

I said that I wanted algorithm analysis to be the work of my life. Most of my work, including writing “The Art of Programming,” was to find a way to determine how good the algorithm is. I liked the study of algorithms most of all, and always was for me in the first place.

I was glad to know that the word "algorithm" comes from the Arabic Al-Khwarizmi. Now Khorezm is a region in Uzbekistan, but then it was a lake. I mean the Aral Sea, which used to be called Khorezmi Lake. This is a part of the world that is completely forgotten.



If you look at the map of Iran, then this place is located north, if you look at the map of Romania, then east, if you look at the map of India or Afghanistan, then west, south of Russia, understand? They just forgot about this part of the world. But I found out that the word "algorithm", Khorezm, came from there. You know, there are places where Armenians live and they call it the Armenian Diaspora? There is a whole Khorezm quarter in Baghdad. And I thought, okay, it would be interesting to visit Khorezm once. I looked into the atlas and was horrified. It's in the very heart of the USSR, how do I get there?!? There are no roads that would lead directly to this place.

I told this to my friend Andrei Ershov, who came from Russia, from the Soviet Academy of Sciences. Well, he was not my friend at that time, I did not know him very well, but he was a friend of John McCarthy and we were at a party in his house. I told Andrei: “Do you know that the word“ algorithm ”comes from a place in the Soviet Union? We need to note this somehow. Imagine how it would be great to organize something like a pilgrimage, where programmers from all over the world could come to Khorezm and celebrate the birth of this concept. ”

And he said: “Sounds like a great idea!” He returned home and began work on organizing all this. He asked the Soviet Academy of Sciences to sponsor an international symposium on algorithms that would last two weeks and take place in the Khorezm region.

Even before I got to Khorezm, when I just got off the plane, I was met by 200 children who were carrying flowers, and then I was interviewed for local television. This was the first time that anyone showed such interest in their lands. The hospitality of the people in the Middle East is amazing. In fact, you know, the owners were so generous that I jokingly asked them to provide me with a kept woman. And I’m sure that they would have done so if I had not assured them that I was just joking. We could visit the peculiar city-museum of Khiva, where the creator of the Al-Khwarizmi algorithm was probably from.



I’m not sure, but in any case it is a kind of preserved city that shows the great heritage of this culture. Half of the people at this conference were from the USSR and the other half from different parts of the world. We could just discuss the significance of the algorithms. The opportunity to arrange this small meeting and see this corner of the world was one of the greatest achievements in my life.


D. Knut is dancing.

Surprisingly, in this village we met children of different nationalities: blondes, blue-eyed, some with a Korean pedigree. We went to cotton farms and harvested cotton. I got a hat that people in Khorezm wear. So now that I'm working on algorithms, I can be suitably dressed.

Why I chose Algorithm Analysis as a Research Area

Behind each written work, and I wrote a lot of them, there is some interesting story. The algorithm itself has become famous, but I myself have not used it for the past 20 years. However, he is in all textbooks and is an instructive example.

For example, it is good to use when you try to look through a long passage from a text to find a specific word. Suppose I am looking for the word the (* article in English) or something like that. Although it would be foolish to search for this word, let's look for dikran (* plant dikran).

Obviously, you stop at every place in the text and ask yourself, “Is this the letter D? Excellent. Next is the letter I? Good. Next is K? No, this is the word 'direction' (* distance from English). Then you move on and repeat this algorithm first. Is it D? No, we already found out that this is I. So we need to move even further. But it’s not so simple. There are more complex words. If we were looking for the word 'didymus' (* twin from English), where there are two letters D, then our algorithm would no longer work.

The professor at Berkeley, Steve Cook, has an amazing theorem on this subject. He claims that if we took a computer that was very limited in its capabilities and if we could write a program that would solve the problem, for this stupid computer, no matter how slowly this program works, then there is a quick way to write the same program for a normal computer.

In other words, we take a certain computer with limited capabilities and if it can solve the problem, then there is a quick way to do it on a normal computer. The only problem that should be solved with this computer is the ability to determine whether a set of letters is a palindrome and crank the same in a chain of palindromes.

I was just curious. In fact, nobody is interested in the concatenation of palindromes. According to Cook's theorem, if there is a way to solve this problem on this funny computer, then there is a quick way to recognize these palindrome connections on a regular computer. But I could not think of any good way to do this on a normal computer, it seemed to me that it would be much more complicated.

I was a pretty good programmer, but this theorem claimed that there was a way to do this, but I could not figure out how. This was the first time I was in a kind of deadlock and could not stop thinking about it. I spent the day and evening to write Cook's theory on the board in detail and finally find a quick way to bring this to life on the computer.

Suddenly I found a clue. Initially, the idea was to write a program that would reflect this general theorem, but it could also solve the problem of searching in the text. I mentioned this on a trip to Berkeley and met Vaughan Pratt there. He was the one who made the biggest contribution, I was just the one who wrote it down afterwards.

Then we learned that the same idea had visited Jim Morris a couple of months earlier, but people looked at his program, did not understand it, and therefore did not take it. In any case, I believe that this is an effective way to search in the text, which also gives a good idea of ​​the basics of computer science. This method has become famous and is associated with my name.

As I said, I wrote 160 works and behind each of them there is some interesting story.

Translation: Diana Sheremyova


A. P. Ershov among the leaders of the republican party and Soviet bodies of Uzbekistan in the cotton field.




Article “Scientific pilgrimage to the homeland of Al-Khwarizmi”

Preface (written jointly by A. P. Ershov and D. Knut; translation into Russian by A. P. Ershov.)

Donald Knuth article “Algorithms in modern mathematics and computational science” , translated into Russian G.S. Zeitin.



Materials from the Ershov archive: International Symposium "Algorithm in Contemporary Mathematics and its Applications"

Read more

• Donald Knuth: I sat on the back desks and bullied jokes, and the teachers humbled themselves and didn’t beat their asses often (1,2,3,7 / 97)
• Donald Knuth: “My Advice to the Young” (93/97) and “Feeling the need to assert oneself” (9/97)
• “Surreal numbers”: I worked for six days, and rested on the seventh (40,41,42 / 97)
• Donald Knuth: How The Art of Programming Was Created (33.38.39 / 97)
• Social Architecture: Strategies for the Success of Open Source Projects

---

Publishing support - Edison , a company that develops crowdsourcing platforms for promoting goods and writes designs applications for an interactive real estate database .