On Kolmogorov Machines and Related Issues

One contribution of the article was to formulate Kolmogorov-Uspensky thesis. In “To the Definition of an Algorithm” [Uspekhi Mat. Nauk 13:4 (1958), 3-28 (Russian)] Kolmogorov and Uspensky wrote that they just wanted to comprehend the notions of computable functions and algorithms, and to convince themselves that there is no way to extend the notion of computable function. In fact, they did more than that. It seems that their thesis was this:

every computation, performing only one restricted local action at a time, can be viewed as (not only being simulated by, but actually being) the computation of an appropriate KU machine (in the more general form).

Uspensky agreed [J. Symb. Logic 57 (1992), page 396]. Another contribution of the paper was a popularization of a beautiful theorem of Leonid Levin

Theorem. For every computable function F(w) = x from binary strings to binary strings, there exists a KU algorithm A such that A conclusively inverts F and (Time of A on x) = O(Time of B on x) for every KU algorithm B that conclusively inverts F.

which had been virtually unknown, partially because it appeared (without a proof) in his article “Universal Search Problems” [Problems of Information Transmission 9:3 (1973), 265-266] which is hard to read.

Reprinted in 1993 World Scientific book Current Trends in Theoretical Computer Science (opens in new tab) pages 225-23.