ON KOLMOGOROV MACHINES AND RELATED ISSUES
Yuri G. Gurevich · WORLD SCIENTIFIC eBooks · 1993
I felt honored and uncertain when Grzegorsz Rozenberg, the president of EATCS, proposed that I write a continuing column on logic in computer science in this Bulletin. Writing essays wasn’t my favorite subject in high school. After some hesitation, I decided to give it a try. I’ll need all the help I can get from you: criticism, comments, queries, suggestions, etc. Andrei Nikolayevich Kolmogorov died a few months ago. In recent years he chaired the Department of Mathematical Logic at the Moscow State University. In a later article or articles, I hope to discuss Kolmogorov’s ideas on randomness and information complexity; here let me take up the issue of Kolmogorov machines and their close relatives, Schönhage machines. I believe, we are a bit too faithful to the Turing model. It is often easier to explain oneself in a dialog. To this end, allow me to introduce my imaginary student Quizani. • Quizani: I think you should introduce yourself too. Don’t assume everyone knows you. • Author: All right. I grew up in the Soviet Union and started my career in the Ural University as an algebraist and self-taught logician. In 1973, I emigrated to Israel where I did logic and taught at Ben-Gurion