From the letter by V. Uspensky to A. Ershov

July 1^st, 1979

Dear Andrei Petrovich!

… And now some information to ponder over. This information would not be so relevant in view of
the initial participants list, but now it is quite timely. The person in question is A.O. Slisenko.
Anatol A. Slisenko is a PhD and a senior research fellow of Leningrad department of the USSR AS
Steklov Mathematical Institute. One should think he is the best country’s specialist in complexity of
concrete computation (not in the spirit of general Blum acceleration theorems, but more like, say,
how to estimate an algorithm for matrix multiplication). In this capacity he carries great authority
with specialists here and abroad including potential symposium participants. If discussions of these
topics are planned in Urgench, his presence would be undoubtedly helpful – at least for competent
contacts with our guests. His home address is:…

I am somewhat concerned with the title of my presentation, initially (conventionally) named “Great
mathematical discoveries associated with the notion of algorithm”. Most probably one may consider
among the same theorems on various decidabilities and undecidabilities. And I even don’t intend to
mention such theorems (even the great example of a group with insoluble identity problem I reckon
irrelevant). Undecidability of the problem of Diophantine equations insolubility will be mentioned
only in connection with Diophantity of denumerable sets – the fact that is really fundamental (and
the fact that as a result the Gilbert problem was solved is rather incidental). Should not the talk be
named “What does the algorithm theory give?” or in some other way in order to not to hurt the
feelings of authors of great discoveries in the field of decidability and undecidability? I, for
example, intend to speak about applications of the notion of randomness, of computable operators –
and, generally, about things of conceptual nature (although I find difficulty in formulating what is
it). What do you think about all this and first of all about the title that can disorient the audience?