# Mathematical works of Vladimir A. Uspensky: a commentary (Enlgish and Russian texts)

Alexander Shen

► To cite this version:

Alexander Shen. Mathematical works of Vladimir A. Uspensky: a commentary (Enlgish and Russian texts). Vladimir A. Uspensky. Non-mathematical works collection (Russian version), 2020, 978-5-94282-675-8. lirmm-03059688

HAL Id: lirmm-03059688

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03059688

Submitted on 12 Dec 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Mathematical works of Vladimir A. Uspensky:
a commentary*

Alexander Shen†

**Abstract**

Vladimir Andreevich Uspensky [1930–2018] was one of the Soviet pioneers of the theory of computation and mathematical logic in general. This paper is the survey of his mathematical works and their influence. (His achievements in linguistics and his organizational role are outside the scope of this survey.)

**Harmonic functions**

The first paper of Uspensky [3] appeared when he was an undergraduate student. It suggests an elementary approach to harmonic functions that is based on the definition of a harmonic function on $\mathbb{R}^2$ as a function that has the mean value property. The main tool in the following observation: for fixed two points A, B the oriented angle $ACB$ is a harmonic function of $C$,<fnref n="1" /> and this function is a locally constant function on any circle that goes through A and B.

**Master thesis**

Uspensky’s thesis advisor was Andrei Kolmogorov; the thesis [4] was written and defended in 1952. It contains the description of the model of computation suggested by Kolmogorov and now known as *Kolmogorov–Uspensky machines*. It is shown that this model is equivalent to partial recursive functions (defined in terms of substitution, recursion and $\mu$-operator). Moreover, this model is used to define relative computability with respect to some function $f$. For that, the graph of $f$ is represented as an infinite graph (a *complex*) that is available to the graph transformation algorithm together with the input [definition (A) on p. 64]. This definition is compared with other definition of relative computability. For that, Uspensky reformulates the Turing–Post definition [84, 86], see definition (T) on p. 63, and shows that definitions (T) and (A) are equivalent. Moreover, Uspensky proves the equivalence with one more definition given in terms of the closure of the function $f$ (and basic functions) under substitution, recursion and $\mu$-operator.

The thesis advisor (Kolmogorov) writes in his opinion:

> This paper analyses (in more details than it was done before) the very notion of algorithmic computability.

(1) The author reproduces the only completely formal definition of algorithmic reducibility (p. 22) that he ascribes to Boris Trakhtenbrot: a function $\gamma$ is reducible

<footnote>* Vladimir Andreevich Uspensky was my teacher (and undegraduate and Ph.D advisor). Here I concentrate on his mathematical works; I hope to express my deep gratitude to him elsewere.</footnote>

<footnote>† LIRMM, University of Montpellier, CNRS, Montpellier, France. Supported by RaCAF-ANR-15-CE40-0016.</footnote>

<footnote n="1">¹This is easy to see, because both direction angles CA and CB satisfy the mean value property and the same is true for their difference.</footnote>
to another function $\delta$ if $\gamma$ belongs to the recursive closure of $\delta$. The author shows that in fact such a reduction can be performed *in some simple canonical way, using some fixed primitive recursive functions* $\tau(u)$ and $\omega(u)$ and some primitive recursive functions $h(u, v, w)$ and $\varphi(m)$ that depend on $\gamma$ and $\delta$; see theorem on p. 28. This is the main result of the paper from the purely mathematical viewpoint.

Trakhtenbrot's definition, on the other hand, needs some "justification" that shows that it corresponds to the intuitive notion of reduction: there is a "mechanical" way of obtaining $\gamma(x)$ assuming that the values $\delta(x)$ are somehow made "accessible" for each $x$. The general framework for such a justification were given by Post; the translation of the corresponding part of Post's paper [86] is reproduces in the thesis. Then the author gives a completely formal definition of reduction that corresponds to this idea (probably for the first time) and proves its equivalence to Trakhtenbrot's definition. This is also a very significant achievement of the author.

Also the paper contains a good survey of the definitions of algorithmic computability for function $y = \gamma(x)$ with numerical arguments and values. It is centered around the definition suggest by myself. The thesis provides the motivation for this definition and proves that it is equivalent to the previous ones. *In a sense this equivalence can be considered as a "justification" for the previous definitions since my definition makes especially clear the idea of an algorithmic computability; the algorithms that are used are models of the real computation devices, only the amount of "memory" is assumed to be unbounded.*

To understand the value of this paper, one should recall the historical context (now almost forgotten). Let us make few historical comments.

## Partial recursive functions

Ask an expert what is a partial recursive function. Most probably the answer would be: this is a function that can be obtained from basic functions (projection function, zero constant and successor function) using substitution, recursion and minimization ($\mu$-operator). This definition can be found in the classical text of Odifreddi [108, p. 127] and other sources (see, e.g., [100, 106] or Wikipedia article [113]).

However, the original definition was different. The traces of this old definition can be found in another classical textbook [70, Section 1.5] and in Wolfram MathWorld [114] site. This definition is equivalent (gives the same class of partial function), but it is different, and one should have this difference in mind while reading old papers.

Let us try to clarify the history. Recursive definitions were well known for a long time (recall the Fibonacci sequence). They were systematically used to define arithmetic functions in the paper of Skolem [72]. He realized that in this way one can define not only addition or multiplication (by the recurrent formula like $x+y' = (x+y)'$ or $x \cdot y' = x \cdot y + x$, where $x'$ is the successor of $x$), but also many other functions that appear in the elementary number theory. After these definitions are given, one could prove basic facts of number theory by induction.<fnref n="2" />

Skolem did not explicitly consider the class of functions that can be defined recursively in this way. However, in his 1925 talk Hilbert [73] says that "the elementary means that we have at our disposal for forming functions are *substitution* (that is, replacement of an argument by a new variable or function) and *recursion* (according to the schema of the derivation of the

<footnote n="2">²The goal was to show that many mathematical results can be proven by a simple and robust way, just by using recursive definitions and inductive arguments. Now the corresponding theory is known as primitive recursive arithmetic.</footnote>
function value for $n + 1$ from that for $n)$”. He then considers the sequence of functions

$$ \varphi_1(a, b) = a + b, \quad \varphi_2(a, b) = a \cdot b, \quad \varphi_3(a, b) = a^b, \\ \varphi_4(a, b) = [\text{bth term in the sequence } a, a^a, a^{(a^a)}, a^{a^{(a^a)}}, \dots] $$

that can be defined in general by the recurrent formula

$$ \varphi_1(a, b) = a + b, \quad \varphi_{n+1}(a, 1) = a, \quad \varphi_{n+1}(a, b+1) = \varphi_n(a, \varphi_{n+1}(a, b)), $$

and mentions Ackermann's result saying that the function $\varphi_n(a, b)$ “cannot be defined by substitutions and ordinary, step-wise recursions” (this result was later published in [74]). When stating this negative result, Hilbert implicitly considers the class of function that can be defined by “substitutions and ordinary, stepwise recursions” (even though this class is not defined explicitly and there is no name for the functions from this class.)

Such a definition (and name) appeared in the classical work of Gödel [75, p. 179]: a function is called recursive (rekursiv in German) if it can be obtained by a sequence of substitution and recursion operation (we construct $\varphi$ assuming that $\psi$ and $\mu$ are already constructed):

$$ \varphi(0, x_2, \dots, x_n) = \psi(x_2, \dots, x_n) \\ \varphi(k+1, x_2, \dots, x_n) = \mu(k, \varphi(k, x_2, \dots, x_n), x_2, \dots, x_n) $$

(scheme (2) p. 179). Gödel proves that these functions could be represented in a formal system, so for him this class of functions is more a tool than an object.

Gödel's definition does not cover more general recursive definition (like the one used by Ackermann). How can they be treated? Herbrand (in a letter to Gödel and in [76]) suggested that one could consider systems of functional equations that related the functions we define with the already defined ones. He writes in [76, p. 5, p. 624 of the English translation]:

We may also introduce any number of functions $f_i(x_1, \dots, x_{n_i})$ together with hypotheses such that

(a) The hypotheses contain no apparent variables;

(b) Considered intuitionistically,<fnref n="3" /> they make the actual computation of $f_i(x_1, \dots, x_{n_i})$ of the $f_i(x_1, \dots, x_{n_i})$ possible for every given set of integers, and it is possible to prove intuitionistically that we obtain a well-determined result.

The reference to intuitionism sounds a bit unclear; probably it means that it is not enough to have a functional equation or a system of equations for which we can prove (using arbitrarily powerful tools) that it has a unique solution. We require that the proof is constructive and provides a method to compute the values of the functions starting from the equations. Indeed, later Kalmar [89] gave an example of a system of functional equations that uniquely defines a non-computable function.

Gödel returns to Herbrand's suggestion (Herbrand died in mountains just after sending his paper [76] to the editors) in his Princeton's lectures. (The lecture notes circulated at that time and later were reprinted, see [76].) As before, he considers recursive functions, that can be obtained from basic functions by substitutions and “ordinary” recursions; however, in Section 9 he mentions the recursive definitions of more general type. The functions defined in this way are called “general recursive functions”. He says:

<footnote n="3">³This expression means: whether they are translated into ordinary language, considered as a property of integers and not as a mere symbol. [Herbrand's footnote]</footnote>
One may attempt to define this notion [general recursive function] as follows: if $\phi$ denotes an unknown function, and $\psi_1, \dots, \psi_k$ are known functions, and if the $\psi$'s and the $\phi$ are substituted in one another in the most general fashions and certain parts of the resulting expressions are equated, then if the resulting set of functional equations has one and only one solution for $\phi$, $\phi$ is a recursive function.”

(and mentions Herbrand's letter as a reference). Then he added some restrictions that clarify Herbrand's idea:

We shall make two restrictions on Herbrand's definition. The first is that the left-hand side of each of the given functional equations defining $\phi$ shall be of the form

$$ \phi(\psi_{i1}(x_1, \dots, x_n), \psi_{i2}(x_1, \dots, x_n), \dots, \psi_{il}(x_1, \dots, x_n)). $$

The second (as stated below) is equivalent to the condition that all possible sets of arguments $(n_1, \dots, n_l)$ of $\phi$ can be so arranged that the computation of the value of $\phi$ for any given set of arguments $(n_1, \dots, n_l)$ by means of the given equations requires a knowledge of the values of $\phi$ only for sets of arguments which precede $(n_1, \dots, n_l)$.

Gödel does not specify the ordering on the tuples (used as arguments), so the exact meaning of this definition is unclear. But later he specifies the derivation rules that allow to derive an equality from the other ones, and says:

Now our second restriction on Herbrand's definition of recursive function is that for each set of natural numbers $k_1, \dots, k_l$ there should be one and only one $m$ such that $\phi(k_1, \dots, k_l) = m$ is a derived equation.

In this way Gödel gives a quite formal definition of some class of functions called “general recursive functions” (usually translated to Russian as «общерекурсивные функции». However, as Kleene explains in [105], at the time of these lectures (1934) Gödel was not sure that this class of functions is general enough: ¡¡However, Gödel, according to a letter he wrote to Martin Davis on 15 February 1965, “was, at the time of [his 1934] lectures, not at all convinced that [this] concept of recursion comprises all possible recursions” ¡¡ [105, p. 48]. Davis writes in [99, p. 40]:

In the present article [Davis discussed [77]] Gödel shows how an idea of Herbrand's can be modified so as to give a general notion of recursive function $\langle\dots\rangle$ Gödel indicates (cf. footnote 3) that he believed that the class of functions obtainable by recursion of the most general kind were the same as those computable by a finite procedure. However, Dr. Gödel has stated in a letter that he was, at the time of these lectures, not at all convinced that his concept of recursion comprised all possible recursions; and that in fact the equivalence between his definition and Kleene's in Math. Ann. 112 [this is [80] in our list] is not quite trivial. So despite appearances to the contrary, footnote 3 of these lectures is not a statement of Church's thesis.

Footnote 3 [99, p. 44] discusses the claim that every primitive recursive function (obtained by substitutions and “ordinary recursions, see below) can be computed by a finitary process, and says that “The converse seems to be true, if, besides recursions according to the scheme (2) [primitive recursion], recursions of other forms (e.g., with respect to two variables simultaneously) are admitted. This cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle”.

Rósza Péter in [78] studies the “ordinary recursions” and proves, for example, that one may use several values of the function (for smaller arguments) in the recursive definition and still get
the same class of functions. She introduces the name “primitive Rekursion” for the “ordinary” recursions considered by her predecessors.

Then Kleene in [80] (1936) introduces the name “primitive recursive functions” («примитивно рекурсивные функции» in Russian) for functions that can be obtained by substitutions and primitive (=“ordinary”) recursion. At the same time, Kleene suggests to consider a bigger class of functions. He calls the functions from this class “general recursive function” (the title of his paper is *General recursive functions of natural numbers*). This class is defined following Herbrand and Gödel; Kleene considered different versions of derivation rules for equalities and shows that they lead to the same class of functions.

Kleene also introduces “ε-operator”. Namely, $εx[A(x)]$ is defined as the minimal $x$ such that $A(x)$ or $0$ if such an $x$ does not exists. This operator is used in Theorem IV that says that every general recursive function can be represented as $ψ(εy[R(x, y)])$, for some primitive recursive function $ψ$ and some primitive recursive predicate $R$ (this means that $R$ can be represented as $r = 0$ for some primitive recursive function $r$), such that for every $x$ there exists $y$ such that $R(x, y).^4$ The next Theorem V says that the reverse statement is also true: every function that can be presented in this way is a general recursive function (in the sense of Herbrand and Gödel). There this representation can be considered as an equivalent definition of the class of general recursive functions. Moreover, this definitions can be used to provide some numbering of all general recursive functions if we add an additional argument $e$ to $R$; not all values of $e$ lead to total functions. One could say that it this way we get a numbering of a family of partial functions, but in this paper Kleene does not considers this class (later called “partial recursive functions”).

Church (also in 1936) publishes his paper [79] where he defines some other class of functions with natural arguments and values in terms of some calculus (called λ-calculus) and claims that this class captures the intuitive idea of computability:

> The purpose of the present paper is to propose a definition of effective calculability³
> which is thought to correspond satisfactorily to the somewhat intuitive notion.

Here (³) is Church's footnote:

> As will appear, this definition of effective calculability can be stated in either of two equivalent forms, (1) that a function of positive integers shall be called effectively calculable if it is λ-definable in the sense of §2 below, (2) that a function of positive integers shall be called effectively calculable if it is recursive in the sense of §4 below. The notion of λ-definability is due jointly to the present author and S.C. Kleene <...> The notion of recursiveness in the sense of §4 is due jointly to Jacques Herbrand and Kurt Gödel <...> The proposal to identify these notions with the intuitive notion of effective calculability is first made in the present paper...

Church adds (a footnote in §7):

> The question of the relationship between effective calculability and recursiveness (which it is here proposed to answer by identifying the two notions) was raised by Gödel in conversation with the author. The corresponding question of the relationship between effective calculability and λ-definability had previously been proposed by the author independently.

It is clear from this footnote that for Church the suggestion to identify the intuitive notion of effective calculability with the formally defined class of functions (for which two equivalent

<footnote n="4">⁴Note that the clause in the definition of ε-operator that lets the value to be 0 when x does not exists, is not used in Theorem IV; so one can use the standard μ-operator instead. (For μ-operator the value is undefined if y does not exist.)</footnote>
definitions are given) is an important contribution. This suggested became known as *Church's thesis*.

Almost at the same time Turing publishes his paper [79] where he defines the model of computation now called *Turing machines*. Turing calls them *a-machines* ('a' for 'automatic'). Turing also constructs the universal machine that can simulate any Turing machine when equipped by a suitable problems. Turing uses this type of machines to define the notion of a computable real number (the digits in the positional representation can be computed by a machine), and also gives his proof of the undecidability of the Entscheidungsproblem (there is no algorithm that can tell whether a given first order formula is logically valid, i.e., true in all the interpretations of the language). Earlier similar results (for equivalent definitions of computability) were proven by Gödel and Kleene, as well as Church (see [99, p.109] for details).

In an Appendix (added August 28, 1936) Turing sketches the proof of equivalence between two definitions of computability of a sequence: in terms of *a*-machines and in terms of *λ*-calculus. Describing this result in the Introduction, he writes:

> In a recent paper Alonzo Church has introduced an idea of "effective calculability", which is equivalent to my "computability", but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem. The proof of equivalence between "computability" and "effective calculability" [i.e., λ-definability] is outlined in an appendix to the present paper.

Independently of Turing (and almost simultaneously) Post publishes his paper [81], where he introduces the notion of a "finite combinatory process" that is very similar to Turing machines. Some technical details are different; one should mention also that Post never speaks about a machine. He describes how a "problem solver or worker" follow "the set of directions" of a fixed type. Then Post writes:

> The writer expects the present formulation to turn out to be logically equivalent to recursiveness in the sense of the Gödel-Church development. Its purpose, however, is not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity. In the latter sense wider and wider formulations are contemplated. On the other hand, our aim will be to show that all such are logically equivalent to formulation 1 [the definition suggest by Post]. We offer this conclusion at the present moment as a working hypothesis. And to our mind such is Church's identification of effective calculability with recursiveness. (...) The success of the above program would, for us, change this hypothesis not so much to a definition or to an axiom but to a natural law.

In a footnote Post adds:

> Actually the work already done by Church and others carries this identification considerably beyond the working hypothesis stage. But to mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.<fnref n="5" />

It is clear that in 1936 the puzzle (as we know it now) was almost completely assembled: there are several definitions of computability that are shown to be equivalent (the classes of

<footnote n="5">⁵Probably now this “fundamental discovery” has lost its value and even may be its meaning: when speaking about the equivalence between the intuitive idea of algorithmic computability and a formal definition, we assume that this intuitive idea was developed independently of any model of computation or programming language. But now it would be almost impossible to find anyone who learned the intuitive notion of algorithm before having some programming experience.</footnote>
computable functions are the same); these definition are considered as reflecting the intuitive notion of an algorithm, and there are some intuitive arguments that support this thesis.

However, there are two points where the picture is different from the modern one. The first is more about terminology: none of the papers that define recursive functions defines this class using substitution, recursion and μ-operator though all the tools to prove the equivalence are ready and this equivalence is mentioned explicitly by Kleene in 1943 [85, p. 53, Corollary].

Second, more important difference is that all these papers consider only total functions (defined for all natural arguments). Partial functions appear only later, in Kleene's paper [83] (published in 1938) where the computable notation systems for ordinal are considered (and partial computable functions are essential). Kleene describes the process of derivation in the sense of Herbrand and Gödel and assumes that such a derivation exists only for one function value (for given arguments). Then he writes:

> If we omit the requirement that the computation process always terminate, we obtain a more general class of functions, each function of which is defined over a subset (possibly null or total) of the n-tuples of natural numbers, and possesses the property of effectiveness when defined. These functions we call partial recursive.

In this way the notion of a *partial recursive function* is introduced.<fnref n="6" /> Kleene considers substitutions and recursions (that can be naturally extended to partial functions), and then defines μ-operator for partial functions:

$$ \mu y[R(m, y) = 0] = n $$

for a partial function R if R(m, n) is defined and equals 0 while all previous values R(m, 0), ..., R(m, n-1) are defined and are not zeros. It is obvious that n with this property is unique; however, it may not exist, and in this case the μ-operator defines a non-total function (that is undefined on m). Kleene notes that the class of partial recursive functions defined in the language of Herbrand and Gödel is closed under all three operations (substitution, recursion and μ-operator). He notes also that for every n there exists a universal function Φ$_n(z, x)$ of n + 1 variables such that every partial recursive function of n variables x can be obtained from Φ$_n$ by fixing some value of the first argument z. This universal function Φ$_n$ can be represented as

$$ \Phi_n(z, \mathbf{x}) = S(z, \mu y T_n(z, \mathbf{x}, y)) $$

where S is some primitive recursive function and $T_n$ is a primitive recursive predicate (saying that some primitive recursive function equals 0). Informally speaking, z is a natural number that encodes a system of functional equations (in Herbrand-Gödel style) that defines some partial recursive function of n variables, and y is an encoding of a derivation that, starting with these equations, establishes the value of this partial recursive function on x. The predicate $T_n$ checks the correctness of this derivation, and the function S extracts the function value from it.<fnref n="7" /> This result is called “Kleene’s normal form theorem”; it implies that partial recursive function could be equivalently defined as functions that can be obtained by substitution, recursion, and μ-operator. One may also require additionally that the μ-operator is used only once (being applied to a primitive recursive functions). However, this way of defining partial recursive functions is not mentioned by Kleene.

The same framework and terminology is used in a later paper of Kleene [85] (1943, where he consider the arithmetical hierarchy) and in his classical book of 1952 [65] that remained a standard reference for logic and computability theory for a long time. Let us mention again

<footnote n="6">⁶The traditional Russian translation of this name is частично рекурсивная функция. It sounds even more strange than общерекурсивная функция for general recursive functions; one could think that the function is not completely recursive but only partially recursive.</footnote>

<footnote n="7">⁷Kleene provides z as the first argument to the function S but this is not necessary.</footnote>
a detail that may sound strange in our time: the statement of “Church’s thesis” (the equiva-
lence between the intuitive notion of computability and formal definitions) mentions only total
functions.

**Relative (oracle) computability**

One can define the notion of computability of a function relative to some other function (or set, if we identify sets with their characteristic functions). This definition was first considered in Turing’s Ph.D thesis (1939, see [84]); however, it was only a side remark and only reducibility to some specific set was considered. Turing writes:

Let us suppose that we supplied with some unspecified means of solving number-
theoretic problems; a kind of oracle as it were. We will not go any further into the
nature of this oracle than to say that it cannot be a machine. With the help of the
oracle we could form a new kind of machine (call them o-machines), having as one of
its fundamental processes that of solving a given number-theoretic problem. More
definitely these machines are to behave in this way. The moves of the machine are
determined as usual by a table except in the case of moves from a certain internal
configuration o. If the machine is in the internal configuration o and if the sequence
of symbols marked with *l* is then the well formed formula **A**, then the machine goes
into the internal **p** or **t** according as it is or is not true that **A** is dual. The decision
as to which is the case is referred to the oracle.

These machines may be described by tables of the same kind as used for the descrip-
tion of *a*-machines, there being no entries, however, for the internal configuration
*o*.

The definition of Turing reducibility for the general case was given by Post in his famous
article [86, Section 11] where he formulated *Post's problem* (asking whether there exists a
recursive enumerable non-recursive set X that it is not Turing-complete: not all recursively
enumerable sets are reducible to X). Formally speaking, Post considers the case when both
sets (the one being reduced and the other to which it is reduced) and recursively enumerable,
but the definition is the same for the general case of arbitrary sets of natural numbers. The
Post's definition follows the scheme sketched by Turing. Kleene in 1943 [85] suggests a different
approach: we define general recursive functions using Herbrand – Gödel derivations but extend
the list of “axioms” adding the full information about the values of some fixed total functions
$\psi_1, \dots, \psi_k$. The functions that are definable in this way are then called *general recursive*
*functions in* $\psi_1, \dots, \psi_k$:

A function $\phi$ which can be defined from given functions $\psi_1, \dots, \psi_k$ by a series of
applications of general recursive schemata we call *general recursive* in the given
functions; and in particular, a function $\phi$ definable ab initio by these means we call
*general recursive*.

However, Kleene does not develop this idea (which remains a side remark), and does not define
relative computability for the case of partial functions (only total functions are considered).
In 1952 book Kleene extends the definitions to partial functions and proves that the resulting
definition (in Herbrand – Gödel style) is equivalent to the definition of relative computability
given by Turing and Post [65, §69]. The oracle is assumed to be a total function (or a tuple
of total functions) but no other restrictions are imposed; recall that Post considered only
recursively enumerable sets as oracles.

A survey of different definitions of relative computability can be found in [109, Section 4.3, "History of Relative Computability").
Now we can explain what was the Uspensky's contribution in his master thesis [4]:<fnref n="8" />

* For the first time, the (now standard) definition of partial recursive functions in terms of substitutions, recursions, and $\mu$-operator was stated explicitly (with a reference to an "idea of Boris Trakhtenbrot" [4, p. 22]).

* It was shown (simultaneously with [65, §69] and in much more clear way) that this definition is equivalent to other definitions of (absolute and relative) computability.

* For the first time, a "machine-independent" definition of relative computability was given. Here machine independence means that the definition does not use any model of computation but only the class of computable functions. It was shown that this definition is equivalent to other definitions of relative computability.

* Finally, it was the first paper that presents the model of computation suggested by Kolmogorov (later it was published in a joint paper by Kolmogorov and Uspensky [16]), the definition of relative computability in terms of this model, and the proof of equivalence of this definition to other definitions of relative computability.

The third item in this list requires some clarifications. The Turing – Post definition of relative computability is a modification of the corresponding definition for (absolute) computability: we extend the class of Turing machines by allowing them to get “answers” from an oracle. Similarly, the Kleene’s definition of the relative computability modifies the definition of the computable (partial recursive) functions. So even if we have already agreed on the definition of (absolute) computability, we still may not left this definition behind when defining relative computability. Instead, in the latter definition we need to return to the model of computation and make some modifications (that allow some kind of “oracle access”).

On the other hand, Uspensky defines relative computability in terms of a dialog with an oracle, and this dialog should be computable in the sense that some (partial) functions that describe this dialog should be computable. These function should describe the dialog in the following sense: they specify the next question to the oracle (or output if no more questions are needed) given the input and the list of previous questions and oracle answers.

Now the "machine-independent" definitions of relative computability are quite standard. For example, one of them can be found in the classic textbook of Rogers [70, Section 9.2] (without any references to previous work). One can also note that Uspensky's definition has a technical advantage: unlike the definition from [70] it can be naturally generalized to a partial oracles $\psi$, and the class of functions that are obtained in this way is equal to the closure of the partial recursive functions and $\psi$ with respect to substitutions, recursions and $\mu$-operator. However, Uspensky did not consider this generalization and always assumes that oracle is a total function (though the proof could be easily adapted to the case of partial oracles).

## Gödel's incompleteness theory and theory of computability

The Gödel incompleteness theorem and the class of recursive functions appeared not only at the same time but also together like Siamese twins. The classical paper where Gödel proved incompleteness of Principia Mathematica and related systems [75] also introduced the notion of a recursive function (a primitive recursive function in modern terminology, see above), and this notion played an important technical role in the proof. Namely, several functions related to the encoding of formulas and proofs by natural numbers (their "Gö numbers") were defined

<footnote n="8">⁸Unfortunately this paper was not published, though both reports (by Kolmogorov, the thesis advisor, and by Petr Sergeevich Novikov, the reviewer) recommended its publication. So — alas — it hardly could play any role in the further developments.</footnote>
recursively, and this definition was used to embed these notion into the formal system (thus
making self-referential statements and formal reasoning about proofs possible).

On the other hand, the first definition of general recursive functions was given in terms of
a formal system (calculus of equalities) that goes back to Herbrand and Gödel.

One could that the separation of these Siamese twins was an important achievement both
in the theory of computation and in the proof theory. And historically it was not so simple
as it may seem now. The first step was done by Turing and Post that suggested models of
computation that do not refer to any calculus (formal theory). And then the general nature of
Gödel's incompleteness theorem was realized; this was done in 1940s by Kleene and (later, but
independently) Kolmogorov.

In 1943 Kleene noted [85] that Gödel's theorem essentially claims that the set of true formulas is not recursively enumerable.<fnref n="9" /> In 1950 he gave [87] a similar interpretation for the Rosser's version of incompleteness theorem: it corresponds to the existence of two inseparable enumerable sets. So all the crucial observations were made by Kleene before 1950. Still the exposition both in this 1950 paper and in the 1952 textbook [65] is intertwined with the language of primitive recursive function (it is enough to say that the exposition in [87] starts by "Let $T_1$ be the primitive recursive predicate so designated in a previous paper by the author"), and the embedding of the inseparable sets into a formal theory is not described explicitly.

Shortly after than (but most probably, independently) Kolmogorov also realized the connec-
tion between Gödel's incompleteness theorem and theory of algorithms. As Uspensky writes in
[51, p. 323],

> At December 2, 1952 Kolmogorov explained me main ideas relating Gödel's incompleteness theorem for general calculi to the existence of [enumerable] sets that are not recursive, and pairs of [enumerable] sets that can not be separated by a recursive set. The explanation was quite concise (maybe, five minutes) but then he gave me a short written note entitled "Gödel and recursive enumerability", so I could read and copy it. The note was written just for himself, and it was not easy for me to understand both the note and his oral comments. Then it became more clear, and on May 8, 1953 Kolmogorov submitted my short paper "Gödel's theorem and the theory of algorithms" to Soviet Math. Doklady. When Kolmogorov worked with his students, he made them feel that they are the authors (and he became a coauthor of his students much more rarely than he deserved it) (...). a paper "On the definition of an algorithm" was published in *Успехи математических наук*; in this paper my role was essentially technical.

Here Uspensky speaks about two papers [6, 16]. The second paper contains the detailed ex-
position of a model of computation based on graph transformations that appeared already in
Uspensky's master thesis [4] and is known as Kolmogorov – Uspensky machines (see above).
The first paper [6] explains (without any reference to primitive recursive functions) that Gödel's
incompleteness theory (formal arithmetic is incomplete and cannot be completed) is a corollary
of two facts: (1) there exist recursively inseparable enumerable sets; (2) this pair of inseparable
sets can be embedded into the formal arithmetic (in modern language, can be *m*-reduced to
the pair (provable formulas, refutable formulas). Moreover, for every enumerable set of addi-
tional axioms (that keeps the theory consistent) one can effectively point out a formula that
is neither provable nor refutable in this extended system, and this fact is a corollary of the
existence of two *effectively* inseparable sets.

Let me stress again that all these observations were made already by Kleene in [87]; it seems
that Kolmogorov and Uspensky did not see that paper at the time. Uspensky's paper [6] has

<footnote n="9">⁹Now people say “computably enumerable” instead of “recursively enumerable”. Since we do not consider other type of enumerations, we call these sets *enumerable* in the sequel.</footnote>
a reference to Kleene's 1943 paper [85]; however, when speaking about inseparable enumerable sets, Uspensky does not refer to Kleene's 1950 paper [87] where they were constructed and notes only that they were constructed by Novikov (and provides a reference to Trakhtenbrot's paper of 1953).

Generally speaking, there are two complementary views on Gödel's theorem. The original Gödel's argument is a version of the liar's paradox. This self-referential paradox notes that the statement "This statement is false" cannot be either true or false. If we consider instead the statement "This statement is not provable" (which can be, unlike the previous one, formulated in the language of arithmetic), we get a statement that is true and (therefore) not provable — or false and provable, but we assume that formal arithmetic is consistent. This reasoning does not rely on the theory of algorithms; however, to show that one can translate finitary arguments into the language of formal arithmetic one can use primitive recursive functions as a technical tool (following Gödel).

On the other hand, Gödel incompleteness theorem is a consequence of the existence of an
enumerable undecidable set (or, in a more symmetric version, of the existence of two recursively
inseparable enumerable sets). In this way self-referential nature of the argument is hidden. But
it is just moved to the proof of the existence of an undecidable enumerable set (or an inseparable
pair). Indeed, this proof uses "diagonal argument" that goes back to Cantor, and this diagonal
argument is of self-referential nature (the "diagonal" function appear when we apply a function
to its own number, or run a program on its own text).

Much later Uspensky published a popular exposition of the proof of Gödel’s theorem based
on the algorithms theory (together with the introduction to this theory) in [22]. The extended
version of this paper was published as a brochure [25] (in the series “Popular lectures in math-
ematics” published by Nauka publishing house in Moscow). This work is probably the most
accessible (and correct) non-technical exposition of Gödel’s incompleteness theorem in Russian
literature (at least if we consider its algorithmic side).

In addition to that, these publications [22, 25] suggest a way to explain theory of algo-
rithms that was quite unusual at the time (one may compare them to Rogers’ textbook [70]).
Usually the exposition started with a detailed analysis of some specific model of computation.
The choice of this model changed with time. Initially most expositions used partial recursive
functions; then Turing machine became the preferred model. In Russia Markov and his school
preferred the so-called normal algorithms. The analysis of this model required a lot of efforts
(and space). Only after that the readers can learn the basic facts like Post’s theorem (an enu-
merable set with enumerable complement is decidable), etc. Of course, the impatient reader
could skip the boring first part, but then all the considerations in the rest of the textbook
became baseless.

What can be done? Uspensky suggested the following approach used in [22] (and before in
his 1972/73 lectures, and may be even earlier). We consider the class of computable function
assuming that this class satisfies some properties (“axioms”). These properties include the
following ones:

* some specific functions (e.g., the pair numbering functions) are computable; some specific constructions (e.g., the conditional execution or loops) preserve computability;

* The *tracing axiom*: for every algorithm *A* there exist a decidable set *R* whose elements are called “traces”, and two computable functions *α* and *ω*. Informally, elements of *R* are traces of terminating runs of *A* on all possible inputs (that include all information about the computation); this set should be decidable since one can check that the trace is indeed a trace of *A*. The function *α* recovers the input from the trace; the function *ω* recovers the output. This is an informal explanation why this axiom is plausible; the formal requirement is only that *A(x) = y* if and only if there exists *r* ∈ *R* such that
$\alpha(r) = x$ and $\omega(r) = y$.

* The program axiom: there exists a decidable set $P$ (whose elements are called “programs” and an algorithm $U$ that can be used to apply an arbitrary program $p \in P$ to arbitrary input $x$ (so the input of $U$ is a pair $\langle p, x \rangle$). The axiom requires that every computable function $f$ has some program $p$ such that $U(p, x) = f(x)$ for every $x$. The last equality sign is understood as follows: either both sides are undefined or both sides are defined and equal.

After we agree with these axioms, we can prove results about computability without going into the technical details. On the other hand, it is quite clear what is missing in this picture to get a formally sound mathematical theory:

* We need to choose some model of computation.

* We need to be able to program (in this model) some constructions used in the proofs. In fact, they could be not so simple (recall the priority arguments, for example).

* We need to prove the tracing axiom and the program axiom for this model.

This looks like a good plan for the first introductory course in the theory of algorithms that postpones some things that could be postponed. The model of computation then could be introduced later when proving the undecidability of specific mathematical problems or defining the complexity classes. Still a psychological barrier remains: many people who are quite fluent in mathematics and can easily deal with complicated constructions still have a feeling of uncertainty when they touch the algorithms theory, but at least this barrier becomes more explicit.<fnref n="10" />

For the proof of incompleteness theorem we need one more axiom (that is not a consequence of the previous ones): the *arithmetization axiom* saying that every computable function can be expressed by an arithmetical formula. (Later this axiom can be proved for some specific computation model.)

If we use this machine-independent approach to the computability theory, we are not allowed to refer to a model of computation when speaking about (say) program transformations or oracle computations. Instead, we should provide all necessary definitions using only the class of computable functions. As we have said, the definition of relative computability that has this form appeared (for the first time) in the master thesis of Uspensky. Then it was done for enumeration reducibility. To deal with program transformations, Uspensky introduced the notion of a “main numbering” (see the next section for the enumeration reducibility and main numberings).

One can also note that this axiomatic approach to computability theory provide a formal justification for the following standard observation: most results of the computability theory can be “relativized”, i.e., remain true if we replace the class of computable functions by the class of A-computable function for some oracle A. Here A can be a set or a total function. Indeed, one could check that all axioms (except, of course, the arithmetization axiom) for this class. After that we know that all theorems (derived from the axioms) are true for this class.

<footnote n="10">¹⁰Nowadays the situation is a bit different; one should take into account that most of the people have a lot of programming experience when starting to learn computability. A modern version of Uspensky’s approach could be something like that: we start with a programming language that is familiar to the students, and add some library functions: (a) an interpreter for this language, i.e., a function that gets two inputs, a program string $p$ and some other string $y$, and simulates program $p$ on input $y$; this corresponds to the program axiom; (b) a step-by-step debugger that gets also the number $n$ of steps that should be simulated (a combination of the tracing axiom and program axiom). One can even add a library function without arguments that returns the program text, this would make the fixed point theorem obvious.</footnote>
Uspensky asked whether this observation fully explains the relativization mechanism, i.e., whether a statement that is true for A-computable functions for all oracles A, is a consequence of his axioms. It turned out that the (positive) answer is easy to get (after the question is stated), see [104].

## Computable mappings of sets and enumeration reducibility

The notion of reducibility introduces by Turing and Post (and considered in the master thesis of Uspensky, see above) can be called “decision reducibility”. If A is reducible to B, and B is decidable, then A is decidable. One may say that in this definition we “reduce the decision problem for A to the decision problem for B”.

In [9] Uspensky gives the definition of *enumeration reducibility* where we reduce the task “enumerate the set *A*” to the task “enumerate the set *B*”. This definition uses the notion of a computable operation on sets (introduced in the same paper). Let us describe this notion.

Let us consider the simple case when unary operation is applied to subsets of $\mathbb{N}$ and maps them also to subsets of $\mathbb{N}$. Consider the set $\mathcal{P}(\mathbb{N})$ of all subsets of $\mathbb{N}$ as a topological space. Namely, for each finite set $X \subset \mathbb{N}$ consider the family $\mathcal{O}(X)$ of all subsets of $\mathbb{N}$ that are supersets of $X$. The families $\mathcal{O}(X)$ and all their unions are considered as open in $\mathcal{P}(\mathbb{N})$. After the topology on $\mathcal{P}(X)$ is defined, we consider all mappings $F: \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ that are continuous with respect to this topology. It is easy to check that all continuous $F$ are monotone (if $U \subset V$, then $F(U) \subset F(V)$), and the value $F(U)$ is determined by the values $F(X)$ for finite subsets $X \subset U$ (is the union of $F(X)$ for all finite $X \subset U$. The values of $F$ on finite sets $X$ can be described by the set of pairs $\{\langle n, X \rangle \mid n \in F(X)\}$ (here $n$ is a natural number, and $X$ is a finite set of natural numbers.

Uspensky gives the following definition: a continuous mapping $F: \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ is a *computable operation* is the corresponding set of pairs (see above) is an *enumerable sets*. Note that pairs $\langle n, X \rangle$ are finite objects, so the notion of an *enumerable set of pairs* makes sense. Now the *enumeration reducibility* is defined: a set $A \subset \mathbb{N}$ is *enumeration reducible* to a set $B \subset \mathbb{N}$ if there exists a computable operation $F$ that maps $B$ to $A$. Uspensky notes that Turing reducibility can be described in terms of *enumeration reducibility*: a total function $\varphi$ is Turing reducible to a total function $\psi$ (i.e., computable with oracle $\psi$) if and only if the graph of $\varphi$ is *enumeration reducible* to the graph of $\psi$. We can also characterize the Turing reducibility for sets in the same way; for that we consider the graphs of characteristic functions of those sets. He says also that one can characterize partial recursive operators in the sense of Kleene [65], but here the terminology is confusing (see the discussion below).

Finally, in this paper ([9]) Uspensky notes that the definition of a computable operations in terms of topology (discussed above) is equivalent to two “machine-dependent” definitions. The corresponding notions are called “Kolmogorov operations” and “Post operations” by Uspensky (though they do not appear explicitly in the works of Kolmogorov and Post).

In another 1955 paper ([10], see also an exposition of its results with some extensions in [12]) Uspensky introduces the notion of a numbering (following Kolmogorov's talk given in 1954 at the seminar on recursive arithmetic, Moscow State University mathematics department), introduces the notion of a “main numbering” («главная нумерация» in Russian) and related the computable operations on *enumerable sets* (as defined in [9]) with algorithmic transformations of their numbers.

Let us explain Uspensky’s contribution in more detail. Assume that we want to consider computable transformations of *programs* for computable functions (or *enumerable sets*). Then it is not enough to know which functions are computable (or which sets are *enumerable*). We need also to make some assumptions on the “programming methods” (or languages, «способы программирования» in Russian that are used for establish the correspondence between pro-
grams and computable functions. Programs are usually strings (words), but one could identify
strings with natural numbers via some computable bijective numbering of strings. Then a
programming language (method) for computable functions defines a universal function of two
arguments: $U(n, x)$ is the output of the $n$th program on input $x$ (we assume that inputs and
outputs are also natural numbers). A programming language for enumerable set defines a uni-
versal set of pairs $(n, x)$ such that $x$ belongs to the $n$th enumerable sets. In a different (but
equivalent) language one may say that a programming method for computable functions (resp.
enumerable sets) is a *natural numbering* of the set of all computable functions (enumerable
sets), i.e., a (total) mapping of $\mathbb{N}$ onto the set of all computable functions (enumerable sets): a
number $n$ is mapped to a computable functions (enumerable set) that corresponds to the $n$th
program.

Not all programming methods (numbering) are equally good. A reasonable theory that de-
scribes the algorithmic transformations of programs needs some additional assumptions. These
assumptions essentially appeared in Kleene's work under the name of "s-m-n-theorem", but
appeared explicitly for the first time in [10] where Uspensky defines the notion of a *main num-
bering*. This definition consists of two requirements. First, to be main, a numbering should
be computable. This means that the corresponding universal function is a computable partial
function of two arguments (for the case of sets: the corresponding universal set of pairs is
enumerable). Second, any other computable numbering should be *reducible* to the main num-
bering.<fnref n="11" /> This means that for any other computable numbering of the same family there exists
a computable translation functions that transforms a number in this other numbering into a
number of the same function (set) in the main numbering.

Fix some main numbering for the family of enumerable sets. Then we may define computable
mappings of this family into itself. Here computability of a mapping *P* means that there exist
an algorithm that, given a number of some enumerable set *X*, returns (some) number for the set
*P*(*X*). In other words, we consider computable transformations of programs (or numbers) that
preserves the equivalence relation: if two program *p* and *p*′ are equivalent, i.e., are programs of
the same set, then they are transformed into two equivalent programs. Uspensky proved [10,
Section 6] that computable mappings of the family of enumerable sets are exactly computable
operations on the family of all sets, restricted to the subfamily of enumerable sets. He also
proved a similar statement for a subfamily of function graphs: every computable mapping of
the family of computable functions into itself is a restriction of a computable operation on the
family on all function graphs.

Let us describe the connections of this work of Uspensky to the other research of that time.<fnref n="12" />
Rice [88] considered *completely recursively enumerable* classes of enumerable set. A family *X*
of enumerable set is called completely recursively enumerable if the set of *all* programs for
all elements of *X* is enumerable. Rice formulated a conjecture [88, p.361]: every completely
recursively enumerable family is the family of all supersets of finite sets from some enumerable
family of finite sets. This conjecture becomes Theorem 5 in Uspensky paper [10, Theorem
5] (1955) and is a crucial point in the proofs of his results about computable transformations.

<footnote n="11">¹¹The definition of reducibility for numbering also was published in [9] with a reference to Kolmogorov’
seminar talk, also probably for the first time.</footnote>

<footnote n="12">¹²Unfortunately (see below the quote from Uspensky’s memoirs) all three publications of him [9, 10, 12] are short notes in the *Soviet Math. Doklady* [9, 10] and a resume of a talk in the Moscow Mathematical Society [12]; they contain only the statements of the theorems and lemmas used in the proofs. The full proofs were published in Uspensky’s PhD thesis [11]. Formally speaking, this thesis was publicly available (it can be ordered and accessed in few libraries in the USSR), but it hardly could influence the developments in the field. Probably the short notes [9, 10, 12] were not read outside the USSR, too. Later Uspensky wrote a monograph [18] that became his “habilitation text” (“докторская диссертация”); this book was translated into French. Unfortunately, it included only the definition of main numberings, but not the results on computable transformations and mappings.</footnote>
This conjecture also was proven in 1956 paper of Rice [92] where it is mentioned that the same result was obtained by McNaughton, Myhill and Shapiro (and there is a reference only to a short note of Myhill [90]). Also in the first (1953) paper of Rice it was shown that no non-trivial property of enumerable set can be decided if a program for this set is given (the generalization of this result appeared in [10] as a corollary to Theorem 5). So this statement is usually called “Rice theorem”, and the result about completely enumerable classes (Rice conjecture proven by Uspensky, McNaughton, Myhill and Shapiro) is usually called “Rice–Shapiro theorem” (see, e.g., Cutland’s book [106, Chapter 7, §2]). The connection between computable transformations of programs and computable operations on partial functions was proven (also in 1955) by Myhill and Sheperdson [91], so it is usually called “Myhill–Sheperdson theorem” (see, e.g., [106, Chapter 10, §2]). Since the Rice–Shapiro theorem is its special case, it is also sometimes called “Myhill–Sheperdson theorem” (see, e.g., [108, Theorem II.4.2 or Proposition II.5.19]).

It is hard to tell how the notion of enumeration reducibility was rediscovered. In Rogers’ textbook [70] is given without any references (to Uspensky or anybody else). In the 1971 paper “Enumeration reducibility and partial degrees” of Case [103] the references to Rogers’ book and Myhill paper [97] are given. However, Myhill’s paper (as well as Davis’ book [93] referenced by Myhill) does not consider enumeration reducibility (it considers only different definitions of relative computability for functions). Modern survey by Soskova [111] does not mention Uspensky’s works at all; it contains a reference to a paper of Friedberg and Rogers [95] that in its turn refers to notes of Rogers’ lectures at MIT in 1955–1956 (distributed in 1957) that were a starting point for his book [70]. One may guess that Rogers rediscovered the notion of enumeration reducibility and its name (that is close to the Russian name «сводимость по перечислимости» used by Uspensky).

The notion of a main numbering («главная нумерация» in Uspensky's terminology) was also rediscovered by Rogers (see [94]) under the name of “Gödel numbering”. Rogers starts with a “machine-dependent” definition: “A Gödel numbering is a numbering equivalent to the standard numbering” (p. 333); however, later he provides a machine-independent characterization (as the maximal element with respect to reducibility — as in the Uspensky definition, though without references to Uspensky). Nowadays the names “admissible numbering” (see, e.g., Soare’s book [112]) and “acceptable numbering” (see, e.g., [108, Definition II.5.2]) are used; in both cases a “machine-dependent” definition is given.

When comparing Uspensky’s work to the similar publications of others, one should have in mind that there are different (and often mixed) notions of reducibility for partial functions. Assume that $f$ and $g$ are two partial functions (with natural arguments and values). Consider the following three definitions of “$f$ is reducible to $g$” ($=f$ is computable relative to $g$); each of them is strictly stronger than the previous ones:

1. The graph of $f$ is enumeration reducible to the graph of $g$.

2. Consider (following Uspensky) the family $\mathcal{U}$ of all partial functions with natural arguments and values, and consider the following topology in $U$: the basic open sets are sets of all extensions of some finite partial functions. Call a continuous mapping $F: \mathcal{U} \to \mathcal{U}$ a *computable operation* if its restriction to finite functions has an enumerable graph, i.e., if the set of all pairs $\langle\langle x, y\rangle, u\rangle$, where $x$ and $y$ are natural numbers, $u$ is a finite partial function and $[F(u)](x) = y$, is enumerable. Then we require that there exists a computable operation that maps $g$ to $f$.

3. We may extend Trakhtenbrot’s definition (see the discussion of Uspensky’s master thesis above) to partial function and require that $f$ belongs to the closure of the family of all partial recursive functions with $g$ added under substitution, recursion and $\mu$-operation. (This requirement appears, for example, in [100].)
The third condition in this list can be equivalently reformulated in the oracle computations language. This reformulation repeats the definition from Uspensky's master thesis but allows partial functions (that were not considered by Uspensky). Namely, an algorithm, given $x$, computes $f(x)$; it is allowed to ask questions about $g(y)$ for arbitrary $y$ — but it should be done sequentially and as soon as it asks for $g(y)$ that is undefined, the computation hangs without providing any result (so $f(x)$ remains undefined for the corresponding $x$). The second requirement also can be reformulated in terms of oracle computations if we allow asking questions about several values $g(y)$ in parallel (the computations continues while waiting for the oracle's answers; it is required that the result of the computation does not depend on delays before the oracle answers are provided).

To see why each requirement is stronger than the previous one, we may consider two examples. The first example separates the first two requirements.

Let $f$ be an arbitrary total function with natural arguments and values. Let $g$ be a partial function whose values are all zeros, and whose domain is the set of all numbers of pairs $\langle n, f(n) \rangle$ for all $n$. (We assume that some computable numbering of pairs is fixed.) Then the first requirement is true for these $f$ and $g$ while the second one is false unless $f$ is computable itself (a computable mapping that maps $g$ to $f$ should map the zero function to $f$, since the zero function extends $g$). This example is mentioned in the Uspensky's footnote to the Russian translation of Rogers' book [70, p.362] with a reference to D.G. Skordev; the original argument of Rogers is much more complicated.

The second example [108, Proposition II.3.20, with a reference to Sasso's 1971 thesis] shows that the third property is stronger than the second one. Let $g$ be an arbitrary partial function with natural arguments that has only zero values. Construct another partial function $f$, also with zero values, in the following way: the value $f(n)$ is defined (and equals 0) if and only if at least of the one values $g(2n)$ and $g(2n+1)$ is defined. Then the second requirement is satisfied for sure: for input $n$ we ask in parallel what are the values $g(2n)$ and $g(2n+1)$; as soon as one of the answers is given, we return 0. However, if we have to ask the oracle sequentially, this argument does not work: if we first ask for $g(2n)$ and $g(2n)$ is undefined, then $f(n)$ is undefined even if $g(2n+1)$ is defined. (Of course, this is only an explanation why the previous construction is no more valid; to show that indeed the third requirement may be false we need a simple diagonal argument.)

The first requirement corresponds to the notion that is called “partial recursive operators” in Rogers' book [70, §9.8]. The second requirement corresponds to what is called “recursive operators” in the same book.

Myhill and Sheperdson [70, §9.8] consider “partial recursive functionals” and refer to The sis I*† from Kleene's book [65, p. 332]. However, this Thesis (see the top of p. 332) does not use the name “partial recursive functional” that does not appear on p. 332 at all. The subject index refers to page 326 for “partial recursive functional”, but this page does not mention such a notion. It defines the notion of a partial function $\varphi$ that is partial recursive relative to par tial functions $\psi_1, \dots, \psi_k$ that corresponds to our first requirement (enumeration reducibility of graphs) and mentions some “scheme” $F$ but does not say whether this scheme $F$ should define a function for all possible $\psi_1, \dots, \psi_k$ or only for the specific functions. (The numberings of all functions that are computable with an oracle are considered only for the case when the oracle is total.) Still Myhill and Sheperdson clarify the situation and say that for their result they need partial recursive functionals that are defined (and produce functions) for all arguments that are functions, so essentially they consider the second requirement (as well as Uspensky in his 1955 papers).

Odifreddi in [108, Definition II.3.6] defines partial recursive functionals with reference to Kleene [65]; however, he uses the third version of the definition (a composition of substitutions, recursions and $\mu$-operators applied to partial recursive functions and input functions) — one
that does not appear in [65]. He uses the names “effectively continuous functional” or “recursive operator” for the second requirement and the name “partial recursive operator” for the first one. He uses topological notions in his definitions (as Uspensky did).

Let us summarize the contribution of Uspensky's papers [9, 10, 12]:

* the historically first definition of enumeration reducibility;

* the definition of a numbering and reducibility of numbering was published for the first time (with reference to Kolmogorov's talk);

* the analysis of the properties of numberings of computable functions and enumerable sets needed for the results about program transformation; the definition of main numberings (later rediscovered by Rogers);

* the proof of Rice's conjecture about completely recursive enumerable classes of enumerable sets (and similar results for functions, including the undecidability of all non-trivial properties of computable functions);

* the definition of a computable operation (in topological terms) and the proof that algorithmic transformations of programs for computable functions or enumerable sets can be described as restrictions of computable operations on functions or sets.

As we have said, these achievements were unavailable to the international community and the corresponding results were independently obtained by other researchers (at the same time or a bit later). Let us note, to avoid possible misunderstanding, that Uspensky does *not* consider algorithms that are defined on all programs of *total* functions and give the same results for equivalent programs. The corresponding work of Kreisel, Lacombe and Shoenfild (1959, see [96]) later generalized by Tseitin [98] to constructive metric spaces, have no intersections with Uspensky's work.

In the following quote from Uspensky's memoirs ([63, p. 905–907, 912]) he recalls his 1955 results and the Third All-Union Mathematical Congress (1956) where these results were presented:

> In the survey talk (June, 26) “On algorithmic reductions” I spoke about four kinds of reductions and relations between them. These four notions are the following: First, *computability reduction* where the task “compute *f*” for some function *f* is reduced to the task “compute *g*” for some other function *g*. Second, the *decidability reduction*: the task “construct a decision procedure for *A*”, where *A* is some set, is reduced for the same task for some other set *B*. Third, the *enumerability reduction*: the task “enumerate *A*” for some set *A* is reduced to the same problem for some other set *B*. Finally, this is *reduction of mass problems* that reduces one mass problem to another one (...). The notion of mass problems was introduced by Yury Medvedev, who was Kolmogorov’s student, who defined also the corresponding reductions. (...)

Another talk of mine (July, 2) was named “The notion of a program and computable operators”, and a short communication (July, 3) “Computable operations, computable operators and effectively continuous functions” was closely related to that talk.

In the last communication I formulated (without proof, of course) the result which now I consider as my main mathematical achievement and still remember the cir-
cumstances when it came to my min; it was called “Theorem 3”<fnref n="13" /> (see below). This
result was the core of my Ph.D. thesis that was defended in October 1955. I never
published the proof of this result, except for the thesis itself; this thesis is available
(or at least *was* available) in the math department library. Why? Mostly due to
my laziness (shame on me). Another reason, may be less embarrassing, but stupid,
was my desire to present this result in the most general form (but one cannot reach
the limits of generalization). 〈...〉

**Theorem 3.** Let $g$ be a function with natural arguments and values. Assume that this function has the following property: if $m$ and $n$ are programs of the same computable $s$-ary function, then $g(m)$ and $g(n)$ are programs of the same unary function. Then there exists a computable operator $V$ such that for every function $\theta$ with program $n$ the value $V(\theta)$ is a function with program $g(n)$.

**A philosophical comment:** a semiotic interpretation of Theorem 3 goes as follows: a “well-behaved” computable transformation of names is accompanied by a computable transformation of named objects.

**Constructivism and classical mathematics**

The idea of a constructive interpretation of mathematical statements (and, more general, logical connective) goes back to Brouwer and his “intuitionistic” school; later it was developed in a different way by Andrei Markov, jr., and his students under the name of “constructivism”. In particular, the constructive interpretation of the statement “for every $x$ there exists $y$ such that...” is that there exist a way to get this “existing” $y$ for every value of $x$.

Usually this constructive approach was combined with the change in the understanding
of logical connectives (that makes the excluded middle law invalid). Still there is another
possibility that initially was not very popular: consider the “effective” versions of classical
notions and results as a part of usual (“classical”, “non-constructive”) mathematics that uses
standard mathematical tools. Many people thought that if we are studying algorithms, this
should be done in some “constructive” or “finitistic” way. Uspensky stressed that this is
not the only option and one can study constructive notions inside the classical universum of
mathematics.

Here are two examples that he considered. The first is the notion of a computable real number. There are different construction of real numbers (Dedekind cuts, fundamental sequences, common points of intervals of decreasing lengths, decimal expansions, etc.). For each of the constructions one can consider its effective version. For example, we can consider Dedekind cuts such that there exists an algorithm that says for a rational number whether it belongs to the left or right part. For a fundamental sequence $x_n$ of rational numbers one may require this sequence to be computable (given $n$, one can compute $x_n$), and also require the existence of a computable modulus of convergence (an algorithm that, given rational $\varepsilon > 0$, computes some $N$ such that $|x_k - x_l| < \varepsilon$ for all $k, l > N$). For an infinite decimal fraction one may require the computability of the function $n \mapsto (\text{nth digit})$, and so on.

Each of these definitions leads to some subset of $\mathbb{R}$ that consists of the numbers that have
effective representations in the corresponding sense. One can ask (still working in the framework
of classical mathematics) whether these definitions lead to the same subset of to different ones.

<footnote n="13">¹³Theorem 3 was interesting for me from the semiotic viewpoint, even if I did not know the word “semiotics” at that time. I remember how I was walking along Moscow streets thinking about this question only. The insight came when I was at my mother-in-law apartment (on Big Spasoglinitschevskii lane in Moscow). My son was not born yet, my wife and her mother went to their jobs in the morning, there was no phone in the apartment (and, of course, no mobiles!). Suddenly I’ve understood how it works. [Uspensky’s footnote]</footnote>
It is not difficult to see that they define the same subset (in different ways), and the elements of this subset can be called computable real numbers (following Turing [82]).

This example can be used to illustrate the difference with Markov-style constructivism. For constructivists there are no such things as “real numbers” in the usual sense, so they cannot consider the set of computable real numbers as a subset of the set of all real numbers. For the $a$ (computable) real number is a pair of algorithms: one, given $n$, computes $x_n$, and the other computes the modulus of convergence. Note that not all definitions mentioned above are equally good. For example, the definition with decimal fractions has problems: we cannot define addition, i.e., there is no algorithm that transforms two constructive real numbers (i.e., the algorithms for their representations) into their sum (i.e., the corresponding algorithm).

However, as Uspensky notes, the same problem can be analyzed in the framework of classical mathematics. For that, we consider numberings of computable reals that correspond to different definitions. We may ask then whether these numberings are equivalent (whether one can algorithmically transform the number of a computable real in one numbering into a number of the same real in another numbering). And here the same problem with decimal fractions reappears — and the other positional systems also have this problem. In [18] Uspensky provides necessary and sufficient conditions for the reducibility of two numberings of computable reals (with different bases).

Another example studied by Uspensky [19]: the effective versions of the notion of an infinite set of natural numbers. We may say that a set $X$ is infinite if for every natural $n$ the set $X$ contains at least $n$ different elements. Or: $X$ is infinite if it differs from any finite set $X$: for every finite $F$ there exists some number that belongs to the symmetric difference $F \Delta X$. Both definitions lead to natural effective versions. In the first case we require that there is an algorithm that, given $n$, produces a list of $n$ different elements of $X$. In the second case we require that there is an algorithm that, given a finite set $X$, produces some element of $F \Delta X$. It is easy to see that these two effective definitions are equivalent (and we may even modify the second definition requiring only that the algorithm gives an element of $X \setminus F$ for finite subsets $F$ of $X$). Using the terminology from Post's paper [86] all these properties are equivalent to non-immunity of $X$ (i.e., to the existence of an enumerable infinite subset of $X$).

On the other hand, not all definitions of infinity lead to equivalent effective versions. For example, we may say that $x$ is infinite if for every $n$ there exists an initial segment $[0, N]$ that contains at least $n$ elements if $X$. The effective version of this definition would be: there exists an algorithm that for every $n$ computes some $N$ with this property. This is a weaker property of “effective infiniteness”: as Uspensky noted in [15] (answering the question of Kolmogorov; A.V. Kuznetsov and Yu.T. Medvedev independently answered the same question), this requirement means that the set is not hyperimmune in the sense of Post [86].

One may also note (though this has no relation to Uspensky's work) that the basic definition in algorithmic randomness, the definition of randomness given by Martin-Löf in 1966 [101] is also an effective version of the definition of a null set (a set of Lebesgue measure 0). This classical definition says that a set $X \subset [0, 1]$ is a null set if for every $\varepsilon > 0$ there exists a covering of $X$ by intervals whose total measure does not exceed $\varepsilon$. For obvious reason we may consider only rational values of $\varepsilon$ and only interval with rational endpoints. Then both $\varepsilon$ and the intervals are constructive objects, and one may consider the effective version of the definition and require that an algorithm gets $\varepsilon > 0$ and enumerates the intervals with required properties. This is exactly what Martin-Löf suggested.

Many topics in algorithmic randomness can be interpreted as effectivization of classical notion and results. For example, the Solovay's criterion of Martin-Löf randomness is (as Alexander Bufetov noted) the effective version of the Borel–Cantelli lemma. It turns out that its standard proof (that considers tails of a convergent series) cannot be effectivized and some other argument (also natural and simple) is need, see [59] for details. Another instructive example
of this type is a proof of an effective version of an ergodic theorem given by Vladimir Vyugin (a student of Uspensky) [110].

## Algorithmic information theory

It is strange that Uspensky, being a student of Kolmogorov and his colleague at the Mathematics Department of the Moscow State University, was not involved in the research initiated by Kolmogorov in 1960s when he introduced the notion of algorithmic complexity of finite objects (now known also as Kolmogorov complexity). I have asked him about that but it still remains a kind a mystery for me. As Uspensky told me, he came into this field only when preparing (with Alexei L. Semenov) the talk for the Urgench conference [24, 26]. In this talk Uspensky and Semenov suggested a general scheme for defining different versions of complexity (or algorithmic entropy, as Uspensky preferred to name them) known at the time: plain, prefix, monotone, decision entropies, as well as conditional versions of entropy. Initially (see [107]) this approach used the notions of $f_0$-spaces and their continuous mappings. In a sense this can be considered as an extension of the topological approach to computability suggested by Uspensky long ago. However, this was definitely an overkill, and Uspensky and Semenov [24, 26] suggested a much more simple version of this scheme that used only the “compatibility relation” on objects and descriptions that is enough to cover most of the cases. Later this simplified scheme was explained in [39, 41]; a detailed exposition from the topological viewpoint (but without $f_0$-spaces) can be found in [59].

The different notions of randomness are discussed also in a survey [35] and in a monograph [59]. In 2005 Uspensky gave a talk at the “Modern mathematics” school for undergraduates devoted to algorithmic randomness. A brochure based on this talk was published in 2006 [49] and was reprinted as a part of a monograph [59].

One of the questions asked by Uspensky, Semenov and An. Muchnik [44] remains open. They asked whether the Martin-Lö randomness is equivalent to the absence of a computable strategy in non-monotone games (“non-predictability”). See [50, 59] for more details.

## Popular science

There are different ideas about “popular science” (in French one says “vulgarization”, and it sounds embarrassing though partially correct). One may tell stories about life and fate of great scientists. One can try to retell stories found in other popular science books adding more funny jokes. All this may be a good thing, but Uspensky’s approach was different. During all his life he tried to explain faithfully the real scientific achievements. These explanation could be easily accessible or technically difficult (depending on the audience); still it was always a serious and honest explanation of a material that can be explained with a clear indication of what remains without proof (or clarification). And he never was afraid of explaining basic and “well known” things: as Aristotle wrote in *Poetics*, “subjects that are known are known only to a few”.

While being a student, Uspensky (with a senior coauthor, Evgeny B. Dynkin) wrote a book [4] that was based on the materials of mathematical circles in Moscow. Uspensky first was a participant of these circles, and later one of the teachers there. The book covers several topics (graphs’ coloring, the basics of number theory and probability theory). These topics are presented as a sequence of problems (as it was done in the circles’ meetings), and the solutions of these problems are provided. This was not the first problem book based on the materials of mathematical circles, but and important new idea was that these problems, taken together, form a coherent exposition of some mathematical theory. This book for a long time was very hard to find (before it was reprinted in 2004 and before its appearance on the Internet).

Several popular brochures written by Uspensky were based on his lectures for high school
students (in particular, for the participants of the mathematical olympiads) and appeared in
the series "Popular lectures on mathematics". Some of them were not related to his own math-
ematical specialty: he wrote a brochure about applications of mechanics to mathematics [17]
and about Pascal's triangle [20]. The latter includes also a philosophical discussion: what is a
combinatorial problem and why do we fix the list of operations that are allowed in the answer
for such a problem (e.g., including factorials but not the notation for binomial coefficients).

Two other brochures in this series written by Uspensky ("The Post machine" [23] and "The Gödel incompleteness theorem") are covering topics from mathematical logic and algorithms' theory. The first is quite elementary and is based on the lessons given by Uspensky to elementary school students. The other one (as we have mentioned) is based on the article published in *Russian Mathematical Surveys* and assumes significant mathematical culture (but still is accessible to competent high school students). One more popular exposition [27] written by Uspensky was devoted to the non-standard analysis where the tools from mathematical logic are used to proved a mathematically correct approach to infinitesimals. The extended version of this brochure was published few years later [31].

Like Josef Knecht (from Hesse's *Das Glasperlenspiel*) Uspensky switched to more and more basic things when becoming older. He started to preach mathematics among humanities students (and researchers). This preaching started in 1960 when he developed and implemented the mathematics curriculum for the Division of Theoretical and Applied Linguistics of the Philology Department of the Moscow State University. However, during the two last decades of his life he addressed to a much wider audience. Several of his lectures during the summer school on mathematics and linguistics (in Dubna, a town near Moscow) were videotaped (thanks to Vitaly Arnold) and are available (see the references in http://www.mathnet.ru/php/person.phtml?optionlang=rus&personid=20219). They give some idea about Uspensky's approach to teaching, but one could fully appreciate it only during university courses (first of all, a non-obligatory ones, «спецкурсы» in Russian). Uspensky always was preaching mathematics, not preaching "about mathematics". He explained simple things, but seriously and with proofs. One of his last books [56] is even called "Very simple examples of mathematical proofs" (probably not a good name from the advertising viewpoint). The other book [45] was named "What is an axiomatic approach?", and it also contains a lot of examples, including "school geometry" — not the part that is taught in high school but the axiomatic part that is omitted. For example, this book explains how one can derive from the axioms that for every line there is a point that does not belong to this line.

The materials from these two books were included in a collection of Uspensky's paper
named "Mathematics' Apology"[54], together with the some other (more general) essays about
mathematics. And strangely his preaching was successful — at least if we interpret success
in the same sense as for Saint Anthony of Padua's preaching to the fish: in 2010 Uspensky
got the "Enlightenment" award established by Dmitry Borisovich Zimin, Russian engineer and
philanthropist, the founder and main sponsor of the *Dynasty* foundation.

In addition to his own books, Uspensky organized the translation and publication of many
classical textbooks: he translated (following the suggestion of Kolmogorov) R. Peter's book
on recursive functions [64], was the editor for the translations of monographs of Kleene [65],
Rogers [70], Davis [71] (the latter translation probably was the first Russian-language book
about non-standard analysis), Church's logic textbook [67], the first volume of the "Elements
of mathematics" by Bourbaki [68], and Ashby's book on cybernetics [66].
References

Uspensky's papers in the Internet:

[1] Uspensky's page at mathnet.ru: http://www.mathnet.ru/rus/person20219

[2] Uspensky's page at the Logic and Theory of Algorithms Division of the Mathematical Department of Moscow Lomonosov State University:
http://lpcs.math.msu.su/~uspensky/

Publications

[3] A geometric approach to proving main properties of harmonic functions
[Геометрический вывод основных свойств гармонических функций, in Russian]
*Успехи математических наук*, 1949, vol. IV, issue 2(30), p. 201–205,
http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1949_UMN_Geometr_vyvod.pdf,
http://mi.mathnet.ru/umn8612

[4] *A general definition of algorithmic computability and algorithmic reducibility. Общее определение алгоритмической вычислимости и алгоритмической сводимости, in Russian*.
Master thesis (advisor A. Kolmogorov) Moscow State Lomonosov University,
Math. Department механико-математический факультет. A typescript. 90 pp.
http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1952_Diploma.pdf
https://archive.org/details/uspensky-1952-master-thesis-and-reviews

[5] E.B. Dynkin, V.A. Uspensky, *Mathematical Conversations: Multicolor Problems, Problems in the Theory of Numbers, and Random Walks*. [Е. Б. Дынкин, В. А. Успенский, *Математические беседы. Задачи о многоцветной раскраске*. Задачи из теории чисел. *Случайные блуждания*, in Russian] (Mathematical circles' library, vol. 6. [Библиотека математического кружка, вып. 6]). Moscow, Leningrad: State Publisher of Technical and Theoretical Books. [Москва–Ленинград: Государственное издательство технико-теоретической литературы], 1952.
http://ilib.mccme.ru/djvu/bib-mat-kr/besedy.htm,
http://www.math.ru/lib/book/djvu/bib-mat-kr/besedy.djvu. 2d ed.: Nauka [Наука,] 2004. English translation published by D.C. Heath, Boston in 1963 (in three brochures) and later was published as one book: E.B. Dynkin, V.A. Uspenskii, *Mathematical Conversations: Multicolor Problems, Problems in the Theory of Numbers, and Random Walks*, Dover books in mathematics, Dover Publications, 2006, ISBN 0-486-45351-0.

[6] On the notion of algorithmic reducibility. [О понятии алгоритмической сводимости, in Russian] A summary of a talk given at the meeting of Moscow Mathematical Society, March 17, 1953. *Успехи математических наук*, vol. VIII, issue 4(56), 1953, July–August, p. 176, see http://mi.mathnet.ru/umn8234

[7] Gödel' theorem and the theory of algorithms [Теорема Гёделя и теория алгоритмов, in Russian]. A summary of a talk given at the meeting of Moscow Mathematical Society, March 24, 1953. *Успехи математических наук*, vol. VIII, issue 4(56), 1953, July–August, p. 176–178, see http://mi.mathnet.ru/umn8234

[8] Gödel' theorem and the theory of algorithms [Теорема Гёделя и теория алгоритмов, in Russian], *Доклады Академии наук СССР*, vol. 91, issue 4, p. 737–740 (1953), https://istina.msu.ru/publications/article/92662634/,
https://archive.org/details/uspensky-1953-dan-091-4-godel-algorithms.
English translation: Gödel's theorem and the theory of algorithms, *American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences*, vol. 23 (1963), 103–107, DOI10.1090/trans2/023/06

[9] On computable operations [О вычислимых операциях, in Russian], *Доклады Академии наук СССР*, vol. 103, issue 5 (1955), p. 773–776,
https://istina.msu.ru/publications/article/92662640/, https://archive.org/details/uspensky-1955-dan-103-5-computable-operations

[10] Systems of enumerable sets and their numberings [Системы перечислимых множеств и их нумерации, in Russian], *Доклады Академии наук СССР*, vol. 105, issue 6 (1955), p. 1155–1158, https://istina.msu.ru/publications/article/92662649/, https://archive.org/details/uspensky-1955-dan-105-6-enumerable-sets-numerations.

[11] On computable operations [О вычислимых операциях, in Russian], Ph.D thesis, Moscow State Lomonosov University, Mathematics Department, October 1955.

[12] Computable operations and the notion of a program. [Вычислимые операции и понятие программы, in Russian]. A summary of a talk given at the meeting of Moscow Mathematical Society, February 28, 1956, *Успехи математических наук*, vol. XI, issue 4(70), 1956, July–August, p. 172–176, http://mi.mathnet.ru/umn7861

[13] Third All-Union Mathematical Congress. Plenary talk "On algorithmic reducibility". [«Об алгоритмической сводимости», in Russian], June 26, 1955. Talk "The notion of a program and computable operators" [«Понятие программы и вычислимые операторы», in Russian], July 2, 1955. Short talk "Computable operations, computable operators and constructively continuous function" [«Вычислимые операции, вычислимые операторы и конструктивно-непрерывные функции», in Russian], July 3, 1955. The resumes of the talks is published: Proceedings of the Third All-Union Mathematical Congress [Труды третьего всесоюзного Математического съезда, in Russian]. Moscow: Academy of Science Publications, 1956. Vol. 2, p. 66–69 (plenary talk), vol. 1, p. 186 (talk), vol. 1, p. 185 (short talk).

[14] On the uniform continuity theorem. [К теореме о равномерной непрерывности, in Russian]. *Успехи математических наук*, vol. XII, issue 1(73), 1957, January–February, p. 100–142, http://mi.mathnet.ru/umn7524

[15] Some remarks on [recursively] enumerable sets [Несколько замечаний о перечислимых множествах, in Russian]. *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 3, Heft 12, S. 157–170 (1957), https://onlinelibrary.wiley.com/toc/15213870/1957/3/12, https://istina.msu.ru/publications/article/92666188/, https://archive.org/details/uspensky-1957-zml-zamechanie-perechisl-mnozhestv.
English translation: Some remarks on recursively enumerable sets, *American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences*, vol. 23 (1963), 89–101, DOI10.1090/trans2/023/05

[16] A.N. Kolmogorov, V.A.Uspensky, On the definition of an algorithm [К определению алгоритма, in Russian]. *Успехи математических наук*, vol. XIII, issue 4(82), 1958, July–August, p. 3–28, http://mi.mathnet.ru/umn7453. English translation (Elliott Mendelson): Kolmogorov A.N., Uspenskij V.A., On the definition of an algorithm, *American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences*, vol. 29 (1963), 217–245, DOI10.1090/trans2/029/07
[17] *Some application of mechanics to mathematics* [Некоторые приложения механики к математике, in Russian] (Popular mathematics lectures [Популярные лекции по математике], issue 27). Moscow, State Physics and Mathematics Publishers [Государственное издательство физико-математической литературы], 1958. 48 pp., https://math.ru/lib/plm/27

[18] On the relations between different systems of constructive real numbers [К вопросу о соотношении между различными системами конструктивных действительных чисел, in Russian], *Communication of High Education Institutions* [Известия высших учебных заведений, mathematics, 1960, issue 2(15), p. 199-208, http://mi.mathnet.ru/ivm2028

[19] *Lectures on computable functions* [Лекции о вычислимых функциях]. Moscow State Physics and Mathematics Publishers [Государственное издательство физико-математической литературы], 1960. 492 pp., https://archive.org/details/uspenskij-1960ru. French translation: Ouspenski V.A., *Leçons sur les fonctions calculables*. Paris, Hermann, 1966. 412 p.

[20] *Pascal's Triangle* [Треугольник Паскаля, in Russian]. (Popular mathematics lectures [Популярные лекции по математике], issue 43). Moscow, Nauka Publishers, Physics and Mathematics Division [Наука, главная редакция физико-математической литературы], 1966. 35 pp. Second extended edition: 1979. 48 pp. http://www.math.ru/lib/book/plm/v43.djvu

[21] Reductions of computable and potentially computable numberings [О сводимости вычислимых и потенциально вычислимых нумераций, in Russian] *Математические заметки*, vol. 6, issue 1 (1969), p. 3-9, http://mi.mathnet.ru/mz6891/ English translation: V.A. Uspenskii, *Reduction of computable and potentially computable numerations*, *Mathematical Notes of the Academy of Sciences of the USSR*, 1969, vol. 6, no. 1, 461-464, DOI10.1007/BF01450246, https://istina.msu.ru/publications/article/92645436/

[22] An elementary exposition of Gödel's incompleteness theorem [Теорема Гёделя о неполноте в элементарном изложении, in Russian]. *Успехи математических наук*, vol. XXIX, issue 1(175), p. 3-47 (1974, January-February), http://mi.mathnet.ru/umn4322. English translation: (E. Lichfield): Uspenskii V.A., *An elementary exposition of Gödel's incompleteness theorem*, *Russian Mathematical Surveys*, vol. 29 (1974), no. 1, 63-106, DOI10.1070/RM1974v029n01ABEH001280, full text available at https://istina.msu.ru/publications/article/92645484/

[23] *Post's machine* [Машина Поста, in Russian]. (Popular mathematics lectures [Популярные лекции по математике], issue 54). Moscow, Nauka Publishers, Physics and Mathematics Division [Наука, главная редакция физико-математической литературы], 1979. 96 pp., http://www.math.ru/lib/book/plm/v54.djvu

[24] Uspensky V.A., Semenov A.L., What are the gains of the theory of algorithms: Basic developments connected with the concept of algorithm and with its application in mathematics, *Algorithms in Modern Mathematics and Computer Science, Proceedings, Urgench, Uzbek SSR, September 16-22, 1979*. Edited by A.P. Ershov and D. Knuth, Lecture Notes in Computer Science, 122, Springer, 1981, p. 100-234, https://archive.org/details/uspensky-semenov-urgench

[25] *Gödel's incompleteness theorem* [Теорема Гёделя о неполноте, in Russian]. (Popular mathematics lectures [Популярные лекции по математике], issue 57). Moscow, Nauka
Publishers, Physics and Mathematics Division [Наука, главная редакция
физико-математической литературы], 1982,
http://www.math.ru/lib/book/plm/v57.djvu. English translation by N. Kolblitz was
published in1987 (Mir Publisher) and later in *Theoretical Computer Science*, **130** (1994),
239–319, https://www.sciencedirect.com/science/article/pii/0304397594902224

[26] Uspensky V.A., Semenov A.L. Theory of algorithms: main discoveries and applications. [Успенский В.А., Семёнов А.Л., Теория алгоритмов: основные открытия и приложения, in Russian]. Published in the proceedings volume: *Algorithms in modern mathematics and its applications. The proceedings of the international symposium, Urgench, Uzbek SSR, September 16-22, 1979*. [Алгоритмы в современной математике и её приложениях. Материалы международного симпозиума, Ургенч, УзССР, 16-22 сентября 1979 г.] Edited by A.P. Ershov, D. Knuth, Part I, p. 99-342, https://archive.org/details/uspensky-semenov-urgench-rus

[27] *Nonstandard, or non-Archimedean, analysis*. [Нестандартный, или неархимедов, анализ, in Russian]. Moscow, Знание publishers, 1983. 61 pp.
https://archive.org/details/uspensky-nonstandard-znanie

[28] Uspensky V.A., Kanovei V.G., Luzin's problems on constituents and their fate [Проблемы Лузина о конституантах и их судьба, in Russian]. *Вестник Московского университета. Серия 1: Математика, механика*, 1983, issue 6, p. 73–87,
https://istina.msu.ru/publications/article/93856782/. English translation: Uspenskii V.A., Kanovei V.G., Luzin's problems on constituents and their fate, *Moscow University Mathematics Bulletin*, vol. 38, no. 6 (1983), 86–102. (Allerton Press, inc.)

[29] Luzin's contribution to the descriptive theory of sets and functions: concepts, problems, predictions [Вклад Н.Н. Лузина в дескриптивную теорию множеств и функций: понятия, проблемы, предсказания, in Russian]. *Успехи математических наук*, vol. 40, issue 3(243), p. 85–116, http://mi.mathnet.ru/umn2648. English translation: Uspenskii V.A., Luzin's contribution to the descriptive theory of sets and functions: concepts, problems, predictions, *Russian Mathematical Surveys*, vol. 40, no. 3 (1985), 97–134, available at https://istina.msu.ru/publications/article/92645592/

[30] A.L. Semenov, V.A. Uspensky, Mathematical logic in computer science and computer applications [Математическая логика в вычислительных науках и вычислительной практике, in Russian] *Вестник Академии наук СССР*, **56**(7), 93–103 (1986)

[31] *What is nonstandard analysis?* [Что такое нестандартный анализ?, in Russian]. Moscow, Nauka Publishers, Physics and Mathematics Division [Наука, главная редакция физико-математической литературы], 1987. 128 pp., https://archive.org/details/chto-takoe-nestandartny-analiz-djvu

[32] V.A. Uspensky, A.L. Semenov, Theory of algorithms: main discoveries and applications. [В. А. Успенский, А. Л. Семёнов, Теория алгоритмов: основные открытия и приложения, in Russian], Moscow, Nauka Publishers, Physics and Mathematics Division [Наука, главная редакция физико-математической литературы], 1987. (Programmer's library, vol. 49 [Серия «Библиотечка программиста», выпуск 49].) 288 pp., https://archive.org/details/uspensky-semenov-1987-algoritmy. English translation: Vladimir Uspensky, Alexei Semenov, *Algorithms: Main Ideas and Applications*, Kluwer Academic Publishers, 1993, https://doi.org/10.1007/978-94-015-8232-2
[33] A.N. Kolmogorov, V.A. Uspensky, Algorithms and randomness [Алгоритмы и случайность, in Russian], *Теория вероятностей и её применения*, vol. XXXII, issue 3, 1987 (July, August, September), p. 425–455, http://mi.mathnet.ru/tvp1437. English translation: Kolmogorov A.N., Uspenskii V.A., Algorithms and randomness, *Theory of Probability and Its Applications*, SIAM Publishers, vol. 32, no. 3, 389–412.
http://dx.doi.org/10.1137/1132060,
https://istina.msu.ru/publications/article/92647240/

[34] V.A. Uspensky, V.G. Kanovei, M.Ya. Suslin's contribution to set-theoretic mathematics [Вклад М.Я. Суслина в теоретико-множественную математику, in Russian]. *Вестник Московского университета. Серия 1: Математика, механика*, 1988, issue 5, p. 8–12,
https://istina.msu.ru/publications/article/93856823/. English translation: Uspenskii V.A., Kanovei V.G., M.Ya. Suslin's contribution to set-theoretic mathematics, *Moscow University Mathematics Bulletin*, vol. 43, no. 5 (1988), 29–40. (Allerton Press, inc.)

[35] V.A. Uspensky, A.L. Semenov, A. Shen, Can an individual sequence of zeros and ones be random? [Может ли (индивидуальная) последовательность нулей и единиц быть случайной?, in Russian]. *Успехи математических наук*, vol. 45, issue 1(271), p. 105–162 (1990, January–February), http://mi.mathnet.ru/umn4692. English translation: V.A. Uspensky, A.L. Semenov, A. Shen, Can an individual sequence of zeros and ones be random? *Russian mathematical surveys*, vol. 45, issue 1, 121–189 (1990),
https://archive.org/details/uspensky-semenov-shen-1990

[36] V.A. Uspensky, V.E. Plisko, Diagnostic propositional formulas [Диагностические пропозициональные формулы, in Russian]. *Вестник Московского университета. Серия 1: Математика, механика*, 1991, issue 3, p. 7–12, available at
https://istina.msu.ru/publications/article/92717778/

[37] V.A. Uspensky, N.K. Vereshchagin, V.E. Plisko, *An introductory course of mathematical logic* [Вводный курс математической логики], Moscow State Lomonosov University Publishers, 1991. 2nd edition: Moscow, Физматлит, 2004,
https://archive.org/details/uspensky-vereshchagin-plisko

[38] *Complexity and Entropy: An Introduction to the Theory of Kolmogorov Complexity*. In: *Kolmogorov Complexity and Computational Complexity*, Osamu Watanabe, editor. Springer, 1992, ISBN 3-540-55840-3, p. 85–102,
https://archive.org/details/uspensky-1992-watanabe-book

[39] Kolmogorov and mathematical logic, *The Journal of Symbolic Logic*, volume 57, number 2, June 1992, 385–412, https://doi.org/10.2307/2275276,
https://archive.org/details/uspensky-1992-jsl-kolmogorov-mathematical-logic

[40] Vladimir A. Uspensky and Valery Ye. Plisko, Review: Raymond M. Smullyan, Gödel's incompleteness theorems, *The Journal of Symbolic Logic*, volume 60, issue 4 (1995), 1320–1324, https://projecteuclid.org/euclid.jsl/1183744885

[41] V.A. Uspensky, A. Shen, *Relations Between Varieties of Kolmogorov Complexities*, *Mathematical Systems Theory*, **29**, 271–292 (1996),
https://link.springer.com/article/10.1007/BF01201280,
lpcs.math.msu.su/~uspensky/bib/Uspensky_1996_MST_Shen_RelationsBetween_varieties_of
[42] Kolmogorov complexity: recent research in Moscow. In W.Penczek, A.Szalas (eds.), *Proceedings of the 21st International Symposium on Mathematical Foundations of Computer Science 1996 (MFCS96), Cracow, Poland, September 2-6, 1996* (Lecture Notes in Computer Science, v. 1113), 1996, p. 156-166,
https://link.springer.com/chapter/10.1007/3-540-61550-4_145,
http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1996_LNCS_Kolmogorov_Complexity_Received

[43] Mathematical logic in the former Soviet Union: brief history and current trends, *Logic and Scientific Methods*, M.L. Dalla Chiare et al., editors, Kluwer Academic Publishers,
https://www.springer.com/us/book/9780792343837, 457-483.

[44] Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky, Mathematical metaphysics of randomness, *Theoretical Computer Science*, **207**, 263-317 (1998),
https://www.sciencedirect.com/science/article/pii/S0304397598000693 (full text available),
http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1998_TCS_Muchnik_Semenov_Math_metaph

[45] *What is an axiomatic method?* [Что такое аксиоматический метод? Izhevsk, Udmurt university [Ижевск: издательский дом «Удмуртский университет»], 2000. 100 pp. ISBN 5-7029-0337-4.

[46] Why Kolmogorov complexity? In: E.Goles and C.Martinez (eds.), *Complex systems* (Series: Nonlinear Phenomena and Complex Systems, Vol. 6), Kluwer Academic Publishers, 2001, p. 201-260. ISBN 0-7923-6830-4,
https://link.springer.com/chapter/10.1007/978-94-010-0920-1_5

[47] *Non-Mathematical Works, with an Appendix: Semiotic Letters of A.N. Kolmogorov to the author and his friends*, [Труды по нематематике с приложением семиотических посланий А. Н. Колмогорова к автору и его друзьям., in Russian] Moscow, ОГИ, 2002. 1409 pp., ISBN 5-94282-086-4,
http://www.math.ru/lib/book/pdf/shen/usp/usp-all.pdf

[48] B. Durand, V. Kanovei, V.A. Uspensky, N.K. Vereshchagin. Do stronger definitions of randomness exist? *Theoretical Computer Science*, v. 290, No. 3, p. 1987-1996 (2001), available as
https://www.sciencedirect.com/science/article/pii/S0304397502000403

[49] V.G. Kanovei, V.A. Uspensky, On the equivalence of the two versions of the Continuum Hypothesis, [Об эквивалентности двух форм континуум-гипотезы, in Russian].
*Вестник Московского университета. Серия 1: Математика, механика*, 2005, issue 3, p. 62-64, https://istina.msu.ru/publications/article/100287822/

[50] Four algorithmic faces of randomness, [Четыре алгоритмических лица случайности, in Russian]. *Математическое просвещение*, ser. 3, issue 10, Moscow, MCCME, 2006, p. 71-108, http://mi.mathnet.ru/mp188. Included as an appendix in the book [59].

[51] Kolmogorov as I remember him [Колмогоров, каким я его помню, in Russian]. In: *Kolmogorov in the memories of his students* [Колмогоров в воспоминаниях учеников, in Russian], edited by A.N. Shiryaev and N.G. Khimchenko, Moscow, MCCME, 2006, 272-371.

[52] V.G. Kanovei, V.A. Uspensky, On the uniqueness of nonstandard extensions [О единственности нестандартных расширений, in Russian]. *Вестник Московского*
университета. Серия 1: Математика, механика, 2006, issue 5, p. 3–10, available at
https://istina.msu.ru/publications/article/100285758/

[53] V.G. Kanovei, T. Linton, V.A. Uspensky, A game approach to the Lebesgue measure, [Игровой подход к мере Лебега, in Russian] *Математический сборник*, vol. 199, issue 11 (2008), 21–44, http://mi.mathnet.ru/msb3948 English translation: V.G.Kanovei, Tom Linton and Vladimir A. Uspensky, Lebesgue measure and gambling, *Sbornik: Mathematics*, volume 199, no. 11, p. 1597, http://dx.doi.org/10.1070/SM2008v199n11ABEH003974

[54] Mathematics' apology [Апология математики, in Russian]. Saint-Petersbourg, Амфора, 2009. 554 pp.

[55] On the history of Goldbach’s problem [К истории проблемы Гольдбаха, in Russian]. In: *Историко-математические исследования. Вторая серия*. РАН, Институт естествознания и техники им. С. И. Вавилова. Vol. 13(48). Moscow, Янус-К, 2009, ISBN 978-5-8037-0449-2, p. 273–283.

[56] *Basic examples of mathematical proofs* [Простейшие примеры математических доказательств, in Russian]. (jjМатематическое просвещениеjj series, issue 34). Moscow, MCCME, 2009. 56 pp. ISBN 978-5-94057-492-7.
http://www.math.ru/lib/book/pdf/mp-seria/034_uspensky.pdf

[57] V.A. Uspensky, V.V. Vyugin, The emergence of algorithmic information theory in Russia [Становление алгоритмической теории информации в России, in Russian]. *Информационные процессы*, vol. 10, issue 2, p. 145–158.

[58] Gödel’s theorem and four ways to it, [Теорема Гёделя и четыре дороги, ведущие к ней, in Russian]. *Математическое просвещение*, ser. 3, issue 15, Moscow, MCCME, 2011, p. 35–75, http://mi.mathnet.ru/mp309

[59] N.K. Vereshchagin, V.A. Uspensky, A. Shen, *Kolmogorov complexity and algorithmic randomness* [Колмогоровская сложность и алгоритмическая случайность, in Russian]. Moscow, MCCME, 2013. 575 pp. (English version: A. Shen, V. Uspensky, N. Vereshchagin, *Kolmogorov complexity and algorithmic randomness*, American Mathematical Society, 2017.)

[60] [V.A. Uspensky, M.S. Gelfand], Mathematics is a part of humanities [Математика—это гуманитарная наука (интервью с В. А. Успенским ведёт М. С. Гельфанд)]. In the book: *Математические прогулки. Сборник интервью*, Moscow, Паулсен, 2017. ISBN 978-5-98797-057-7, p. 198–207. [The English translation of the book: *Mathematical Walks. A Collection of Interviews*, ISBN: 978-5-98797-167-3, Moscow, Paulsen, 2017.]

[61] Vladimir Uspenskiy and Alexander Shen, *Algorithms and Geometric Constructions, Computability in Europe, 2018*, Lecture Notes in Computer Science, v. 10936, Springer, p. 410–420 (2018), see also arXiv:1805:12579

[62] *Non-Mathematical Works. Second extended and corrected edition. In five parts. Part 5. Memories and observations.* [Труды по нематематике. Второе издание, исправленное и дополненное. В пяти книгах. Книга пятая. Воспоминания и наблюдения., in Russian]. Moscow, Объединённое гуманитарное издательство. Фонд «Математические этюды». 2018. 1118 pp.

[63] Third Mathematical Congress. In: [62, p. 897–905]. Commentaries. Ibidem, p. 905–912.
Publications translated or edited by Uspensky

[64] R. Peter, Recursive functions [P. Петер, *Рекурсивные функции*, in Russian], translated from German by V.A. Uspensky, edited by A.N. Kolmogorov, with a preface written by A.N. Kolmogorov. Moscow, Издательство иностранной литературы, 1954. (Original book: *Rekursive Funktionen*, von Rósza Péter, Budapest, 1951.)

[65] S. Kleene, Introduction to metamathematics [Стефен К. Клини, *Введение в математематику*, in Russian], translated from English by A.S. Esenin-Volpin, edited by V.A. Uspensky. Moscow, Издательство иностранной литературы, 1957. (Original book: Stephen Cole Kleene, *Introduction to metamathematics*, D. van Nostrand company, New York, Toronto, 1952.)

[66] W. Ross Ahsby, *An introduction to cybernetics* [У. Росс Эшби, *Введение в кибернетику*, in Russian]. Translated from English by D.G. Lakhuti. Edited by V.A. Uspensky. With a preface written by A.N. Kolmogorov. Moscow, Издательство иностранной литературы, 1959. 428 pp. (Original book: *An introduction to cybernetics*, by W. Ross Ashby, London, Chapman&Hall Ltd., 1956.)

[67] A. Church, Introduction to mathematical logic, volume I. [А. Чёрч, *Введение в математическую логику*, I, in Russian]. Translated from English by V.S. Chernyavsky. Edited by V.A. Uspensky. Moscow, Издательство иностранной литературы, 1960. (Original book: *Introduction to mathematical logic* by Alonzo Church. Volume I. Princeton University Press, 1956.)

[68] N. Bourbaki, *Elements of Mathematics. Part 1. Fundamental structures of analysis. Book 1. Set theory* [Н. Бурбаки, *Начала математики. Первая часть. Основные структуры анализа. Книга первая. Теория множеств*, in Russian]. Translated from French by G.N. Povarov and Yu.A. Shikhanovich. Edited by V.A. Uspensky. With a preface written by V.A. Uspensky. Moscow, Мир, 1965. (Original book: *Éléments de mathématique par N. Bourbaki, XVII, XX, XXII, I. Première partie. Les structures fondamentales de l'analyse. Livre I. Théorie des ensembles*. Hermann, 1956–1960.)

[69] Mathematics in the modern world [Математика в современном мире, in Russian], a collection of translations of papers from Scientific American special issue Mathematics in the modern world, Scientific American, 1964. Translated from English by N.G. Rychkova. Edited by V.A. Uspensky. With a preface written by V.A. Uspensky. Moscow, Мир, 1967.

[70] H. Rogers, Theory of recursive functions and effective computability [Х. Роджерс, *Теория рекурсивных функций и эффективная вычислимость*, in Russian], translated from English by V.A. Dushsky, M.I. Kanovich, E.Yu. Nogina. Edited by V.A. Uspensky. Moscow, Мир, 1972. (Original book: Hartley Rogers, Jr., *Theory of recursive functions and effective computability*, McGraw-Hill Book Company, 1967. A preliminary version with the same name. Volume I. Mimeographed. Technology Store, Cambridge, Mass., 1957.)

[71] M. Davis, *Applied nonstandard analysis* [М. Дэвис, *Прикладной нестандартный анализ*, in Russian]. Translated from English by S.F. Soprunov. Edited by V.A. Uspensky. With a preface written by V.A. Uspensky. Moscow, Мир, 1980. (Original book: Martin Davis, *Applied nonstandard analysis*, Wiley&Sons, 1977.)
## Other references

[72] Th. Skolem, *Begründung der elementaren Arithmetik durch dir rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich* (Videnskapsselskapets Scrifter, I. Mat.-naturv. Klasse, 1923, No. 6), Kristiania, 1923. (English translation: The foundations of elementary arithmetic established by means of the recursive mode of thought without the use of apparent variables ranging over infinite domains. In [102, p. 302–333].)

[73] David Hilbert, *Über das Unendliche, Mathematische Annalen*, Bd. 95, S. 161–190 (1926). (English translation: On the Infinite, [102, p. 367–392].)

[74] Wilhelm Ackermann in Göttingen, Zum Hilbertschen Aufbau der reellen Zahlen, *Mathematische Annalen*, Bd. 99, 118–133 (1928). (English translation: On Hilbert’s construction of the real numbers, [102, p. 493–507].)

[75] Kurt Gödel in Wien, *Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik*, 38, 173–198 (1931). (English translation: On formally undecidable propositions of *Principia Mathematica* and related systems I, [102, p. 596–616] or [99, p. 4–38].)

[76] J. Herbrand à Paris, Sur la non-contradiction de l'Arithmétique, *Journal für die reine und angewandte Mathematik*, Bd. 166, S. 1–8 (1932), http://www.digizeitschriften.de/dms/img/?PID=PPN243919689_0166%7Clog4 (English translation: On the consistency of arithmetic [102, p. 618–628].)

[77] Kurt Gödel, *On undecidable propositions of formal mathematical systems*, Lecture notes, Institute for Advanced Study (Princeton), Spring 1934. Reprinted in [99, p. 39-74]

[78] Rósza Péter, *Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktionen, Mathematische Annalen*, Bd. 110, n. 1, S. 612–632 (1935), https://doi.org/10.1007/BF01448046, https://link.springer.com/article/10.1007%2FBF01448046

[79] Alonzo Church, An unsolvable problem of elementary number theory, *American Journal of Mathematics*, vol. 58, no. 2 (April 1936), 345–363. Reprinted in [99, p. 88–107]

[80] S.C. Kleene, General recursive functions of natural numbers, *Mathematische Annalen*, Bd. 112, S. 727–742 (1936), https://eudml.org/doc/159849. Reprinted in [99, p. 236–253].

[81] Emil L. Post. Finite combinatory processes. Formulation I. *The Journal of Symbolic Logic*, vol. 1 (1936), p. 103–105.

[82] A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem, *Proceedings of the London Mathematical Society*, ser. 2, vol. 42 (1936–7), p. 230–265; Correction in the next volume of the same journal: vol. 43 (1937), p. 544–546. Reprinted in [99, p. 116–154].

[83] S.C. Kleene, On notations for ordinal numbers, *Journal for Symbolic Logic*, 3, 150–155 (1938), https://www.jstor.org/stable/2267778

[84] A.M. Turing, Systems of logic based on ordinals, *Proc. London Math. Soc.* (2), vol. 45 (1939), pp. 161–228, https://doi.org/10.1112/plms/s2-45.1.161. (Reprinted [99, p. 154–222]. Turing’s Princeton Ph.D. thesis (with the same name) available as http://www.dcc.fc.up.pt/~acm/turing-phd.pdf)
[85] S.C. Kleene, Recursive predicates and quantifiers, *Transactions of the American Mathematical Society*, **53**, number 1, 41–73 (1943), https://doi.org/10.1090/S0002-9947-1943-0007371-8. Reprinted in [99, p.254–287].

[86] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, *Bulletin of the American Mathematical Society*, **5**, 284–316 (1944).
https://projecteuclid.org/download/pdf_1/euclid.bams/1183505800. Reprinted in [99, p.304–337].

[87] S.C. Kleene, A symmetric form of Gödel's theorem (Presented to the American Mathematical Society, October 29, 1949. Communicated by Prof. L.E.J. Brouwer at the meeting of April 29, 1950). Koninklijke Nederlandse Akademie van Wetenschappen, Volume 53, deel 6 (1950), 800–802,
http://www.dwc.knaw.nl/DL/publications/PU00018825.pdf

[88] H.G. Rice, Classes of recursively enumerable sets and their decision problems, *Transactions of the American Mathematical Society*, vol. 74 (1953), p. 358–366.

[89] Lászlo Kalmár in Szeged, Ungarn, Über ein Problem, betreffend die definition des Begriffes der allgemein-rekursiven Funktion, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 1, S. 93–95 (1955),
https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19550010204

[90] John Myhill, A fixed point theorem in recursion theory, abstract, Eighteenth Meeting of the Association of Symbolic Logic, *The Journal of Symbolic Logic*, volume 20, no.2 (June 1955), p. 205.

[91] J. Myhill in Berkeley, California (USA), J.C. Sheperdson in Bristol, England, Effective operations in partial recursive functions, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 1, S. 310–317 (1955),
https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19550010407

[92] H.G. Rice, On completely recursive enumerable classes and their key arrays, *The Journal of Symbolic Logic*, volume 21, number 3, Sept. 1956, p. 304–308. (Received September 14, 1955) https://www.jstor.org/stable/2269105

[93] Martin Davis, *Computability and Unsolvability*, McGraw-Hill Book Company, 1958.

[94] Hartley Rogers, Jr. Gödel numberings of partial recursive functions, *Journal of Symbolic Logic*, Volume 23, Number 3, Sept. 1958, p. 331–341 (Received July 7, 1958),
https://www.jstor.org/stable/2964292

[95] Richard M. Friedberg, Hartley Rogers jr., Reducibility and Completeness for Sets of Integers, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 5, S. 117–125 (1959), https://doi.org/10.1002/malq.19590050703

[96] Kreisel, G., Lacombe, D., Shoenfield, J.R., *Partial recursive functionals and effective operations*, in *Constructivity in Mathematics*, A. Heyting, editor, North Holland, 1959, p. 195–207.

[97] John Myhill, Note on degrees of partial functions, *Proceedings of the American Mathematical Society*, **12** (1961), p. 519–521,
https://doi.org/10.1090/S0002-9939-1961-0125794-X
[98] G.S. Tseitin, Algorithmic operators in constructive metric spaces. [Алгорифмические операторы в конструктивных метрических пространствах, in Russian]. Proceedings of Moscow Steklov Institute, LVII, Problems in constructive mathematics, 2. (Constructive analysis) [Труды математического института имени В. А. Стеклова, LVII, Проблемы конструктивного направления в математике, 2 (Конструктивный математический анализ)], a collection of papers. Edited by N.A. Shanin. Moscow, Leningrad, Academy of Science Publishers, Издательство Академии наук СССР, Москва, Ленинград, 1962, p. 295–361.

[99] *Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions*, a collection compiled by Martin Davis, Raven Press, Hewlett, New York, 1965.

[100] A.I. Maltsev, *Algorithms and recursive functions* [Алгоритмы и рекурсивные функции, in Russian], Moscow, Наука, 1965. (2nd edition, 1986)

[101] Per Martin-Löf, The definition of random sequences, *Information and Control*, volume 9, issue 6, December 1966, p. 602–619,
https://doi.org/10.1016/S0019-9958(66)80018-9

[102] *From Frege to Gödel. A Source Book in Mathematical Logic, 1879-1931*, a collection of papers compiled by Jean van Heijenoort, Harvard University Press, Cambridge, Massachusetts, 1967.

[103] John Case, Enumeration reducibility and partial degrees, *Annals of mathematical logic*, vol. 2, no. 4 (1971), 419–439. (Received 9 September 1969),
https://www.sciencedirect.com/science/article/pii/0003484371900039

[104] A. Shen, Axiomatic approach to the theory of algorithms and relativized computability,
[Аксиоматический подход к теории алгоритмов и относительная вычислимость, in
Russian], *Вестник Московского университета. Серия 1: Математика, механика*,
1980, issue 2, p. 27–29. (English translation made by the author is available
as https://hal-lirmm.ccsd.cnrs.fr/lirmm-01923123.)

[105] Stephen C. Kleene, The theory of recursive functions, approaching its centennial. (Elementarrekursiontheorie vom höheren Standpunkte aus.) *Bulletin of the American Mathematical Society*, volume 4, number 1, July 1981, 43–61.

[106] Nigel Cutland, *An introduction to recursive function theory*, Cambridge University Press, 1980. Russian translation by Albert A. Muchnik, edited by S.Yu. Maslov: Н. Катленд, *Вычислимость. Введение в теорию рекурсивных функций*. М.:Мир, 1983.

[107] A. Shen, Algorithmic versions of the notion of entropy [Алгоритмические варианты понятия энтропии, in Russian], *Доклады Академии наук*, 1984, vol. 276, issue 3, p. 563–566. (English translation: Soviet Math. Doklady, **29**(3), 1984, 569–573.)

[108] Piergiorgio Odifreddi, *Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers* (Studies in logic and the foundations of mathematics, volume 125), Elsevier, 1989. xix+668 pages.

[109] Robert I. Soare, Computability and Recursion, *Bulletin of Symbolic Logic*, **2**(3), 284–321 (1996). See also http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

[110] V.V. Vyugin, Ergodic theorems for individual random sequences, *Theoretical Computer Science*, volume 207, issue 2, November 6, 1998, p. 343–361,
https://doi.org/10.1016/S0304-3975(98)00072-3.
[111] Mariya I. Soskova, The Turing Universe in the Context of Enumeration Reducibility. In: Bonizzoni P., Brattka V., Löwe B. (eds), *The Nature of Computation. Logic, Algorithms, Applications*. CiE 2013. Lecture Notes in Computer Science, vol 7921. Springer, Berlin, Heidelberg, p. 371–382, https://doi.org/10.1007/978-3-642-39053-1_44

[112] Robert I. Soare, *Turing Computability. Theory and Applications*. Springer, 2016, ISBN 978-3-642-31932-7, https://doi.org/10.1007/978-3-642-31933-4

[113] Wikipedia pages: *Primitive recursive function*, https://en.wikipedia.org/wiki/Primitive_recursive_function and *µ-recursive function*, https://en.wikipedia.org/wiki/%CE%9C-recursive_function. (Version of November 5, 2018)

[114] Szudzik, Matthew. *Recursive Function*. From MathWorld — A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/RecursiveFunction.html. (Accessed November 5, 2018)
# Математические работы Владимира Андреевича Успенского: комментарии*

Александр Шень†

## Аннотация

Мой учитель Владимир Андреевич Успенский (1930–2018) был одним из пионеров теории вычислений и в целом математической логики в СССР. В этом обзоре предпринимается попытка описать его математические работы и их роль в развитии теории алгоритмов и математической логики в СССР. (Его организационная деятельность и достижения в лингвистике выходят за рамки этого обзора.)

## Гармонические функции

Первая (студенческая) работа Успенского [3] предлагает элементарное изложение основных свойств гармонических функций (с минимальным использованием сведений из анализа—определением считается утверждение теоремы о среднем). Изложение основано на таком наблюдении: угол, под которым виден фиксированный отрезок из переменной точки, является гармонической функцией этой точки в том смысле, что для него верна теорема о среднем,<fnref n="1" /> и функция эта является ступенчатой на окружности, проходящей через концы отрезка.

## Дипломная работа

В дипломной работе Успенского [4] излагается модель вычислений, предложенная А. Н. Колмогоровым и известная теперь как «машины Колмогорова—Успенского». Доказывается, что эта модель эквивалентна частично рекурсивным функциям, определённым с помощью подстановки, рекурсии и минимизации (то есть даёт тот же класс вычислимых функций). Кроме того, в рамках этой модели вводится понятие вычислимости относительно некоторой функции $f$: график функции $f$ представляется в виде бесконечного графа (комплекса), доступного алгоритму вместе со входом [определение (А) на с. 64]. Это определение относительной вычислимости сравнивается с другими. Для этого Успенский переформулирует определение Тьюринга–Поста (машины с оракулом [84, 86]) в терминах вычислимого протокола взаимодействия с оракулом [определение (Т) на с. 63], и доказывает, что полученное определение эквивалентно

<footnote>* Владимир Андреевич Успенский был моим учителем (и научным руководителем на старших курсах и в аспирантуре, как это формально называется на мехмате МГУ). В этом обзоре говорится прежде всего о его математических работах; надеюсь выразить свою благодарность за всё остальное в отдельном тексте.</footnote>

<footnote>† LIRMM, University of Montpellier, CNRS, Montpellier, France. Грант RaCAF-ANR-15-CE40-0016</footnote>

<footnote n="1">¹ Это следует из того, что среднее направление из фиксированной точки на переменную точку окружности совпадает с направлением на её центр.</footnote>
определению с бесконечным графом, кодирующим оракул (А). Кроме того, в работе до-
казано, что эти определения относительной вычислимости эквивалентны определению
в терминах замыкания относительно операций подстановки, рекурсии и минимизации
[определение (R) на с. 64]. Колмогоров (научный руководитель) пишет в своём отзыве:

В ней [дипломной работе] подвергается более полному, чем до сих пор дела-
лось, анализу само понятие алгоритмической вычислимости.

(1) Автор приводит только одно, предлагавшееся до него, формально без-
укоризненное определение алгорифмической [в этом предложении Колмо-
горов пишет «алгорифмической» через «ф», как это делал А. А. Марков]
сводимости, которое он на с. 22 приписывает Б. А. Трахтенброту: функция
γ сводится к функции δ, если γ принадлежит рекурсивному замыканию
δ. Автор показывает, что в действительности такая сводимость может быть
всегда осуществлена очень простым каноническим образом при помощи раз
навсегда заданных примитивно-рекурсивных функций τ(u) и ω(u) и зави-
сящих от пары γ, δ примитивно рекурсивных функций h(u, v, w) и ϕ(m).
См. об этом теорему на стр. 28. Это основной новый с чисто математи-
ческой точки зрения результат работы.

Определение сводимости по Трахтенброту нуждается в известном «оправ-
дании» его соответствия интуитивной идее сводимости в смысле существо-
вания «механического» способа получения при любом х значения γ(x) в
предположении, что получение значений δ(x) сделано каким-то способом
«доступным» для любого х. Общие контуры возможной формализации этой
идеи были намечены Поустом [так Колмогоров пишет фамилию Поста (Emil
Post)]. В дипломной работе полностью воспроизведён перевод соответству-
ющего места статьи Поуста [имеется в виду статья [86]]. Автор дипломной
работы, по-видимому впервые, даёт соответствующее этой идее определ-
ление сводимости с полной отчётливостью и показывает его эквивалент-
ность определению Трахтенброта. Это тоже весьма существенное достиже-
ние автора дипломной работы.

(2) Кроме того в работе содержится хороший обзор различных предлагав-
шихся ранее определений алгоритмической вычислимости числовой функ-
ции у = γ(x). В центре изложения помещено определение, предложенное
мною, интерес которого на мой взгляд убедительно аргументирован авто-
ром дипломной работы. Доказана равносильность этого определения преж-
де предлагавшимся. В известном смысле слова этот результат можно
рассматривать как «обоснование» прежних определений, так как в моём
определении становится особенно ясной основная идея алгоритмической
вычислимости, которая отличается от вычислимости обыкновенным ре-
альным счётным механизмом только неограниченным объёмом «запоми-
нающего устройства» механизма.

Чтобы оценить содержание работы, важно представлять себе исторический кон-
текст. Сейчас этот контекст почти забыт, и о нём надо сказать несколько слов.

Частично рекурсивные функции

Если спросить, что такое частично рекурсивная функция (partial recursive function),
большинство современных специалистов ответят, что это функция, которая может быть
получена из базовых функций (проекция, нулевая функция и функция прибавления единицы) с помощью операций подстановки, рекурсии и минимизации (μ-оператора). Это определение можно найти в классической книге Одифредди [108, с. 127], в других учебниках [100, 106] и в википедии [113].

Но раньше определение было другим, и следы этого старого определения сохранились в другом классическом учебнике [70, раздел 1.5] и в справочном ресурсе Wolfram MathWorld [114]. Хотя это определение и эквивалентно приведённому выше (задаёт тот же класс функций), но разницу между ними важно иметь в виду при чтении старых работ.

История вопроса здесь такова. Рекуррентные определения были известны давно (достаточно вспомнить о Фибоначчи), но их систематическое использование для построения арифметики появилось в работе Сколема 1923 года [72]. Он понял, что таким образом можно определить не только простые функции, скажем, сложение и умножение (чтобы прибавить следующее за $y$ число к $x$, надо прибавить $y$ к $x$ и взять следующее число; чтобы умножить $x$ на следующее за $y$ число, надо умножить $x$ на $y$ и прибавить $x$), но и много других функций, встречающихся в элементарной теории чисел. После этого базовые результаты этой теории можно доказать по индукции, исходя из рекурсивных определений.<fnref n="2" />

Сколем не рассматривал явно класса всех функций, которые можно получить с помощью такого рода рекурсивных определений. Но уже в докладе 1925 года Гильберт [73] говорит об определениях функций «с помощью подстановок и рекурсий» и различает «обычные, пошаговые рекурсии», где значение функции на каком-то числе определяется через её значение на предыдущем числе, и более сложные схемы. В качестве примера такой более сложной схемы он приводит последовательность функций

$$ 
\begin{aligned}
\varphi_1(a, b) &= a + b, \quad \varphi_2(a, b) = a \cdot b, \quad \varphi_3(a, b) = a^b, \\
\varphi_4(a, b) &= [b\text{-й член в последовательности } a, a^a, a^{(a^a)}, a^{a^{(a^a)}}, \dots]
\end{aligned}
$$

и так далее, которую можно задать рекурсивно равенствами

$$ \varphi_1(a, b) = a + b, \quad \varphi_{n+1}(a, 1) = a, \quad \varphi_{n+1}(a, b+1) = \varphi_n(a, \varphi_{n+1}(a, b)), $$

и упоминает результат Аккермана о том, что функцию $\varphi_n(a, b)$ как функцию от трёх переменных $n, a, b$ нельзя задать «обычными» рекурсиями (этот результат опубликован позже в [74]). Упоминание этого отрицательного результата Гильбертом означает, что у Гильберта было уже понятие о классе функций, которые можно получить «обычными» рекурсиями (и подстановками), хотя не было специального названия для функций этого класса и не было явно дано его определение.

Такое название и такое определение появились в знаменитой работе Гёделя [75, с. 179]: функция называется рекурсивной (rekursiv по-немецки), если она получается последовательным применением нескольких операций подстановки и операции рекурсии такого вида (построение функции $\varphi$, если $\psi$ и $\mu$ уже построены ранее):

$$ 
\begin{aligned}
\varphi(0, x_2, \dots, x_n) &= \psi(x_2, \dots, x_n) \\
\varphi(k+1, x_2, \dots, x_n) &= \mu(k, \varphi(k, x_2, \dots, x_n), x_2, \dots, x_n)
\end{aligned}
$$

<footnote n="2">²Мотивацией этой работы было — показать, что многие математические результаты можно обосновать простым и надёжным способом, индуктивно доказывая равенства между рекурсивно определёнными функциями. Теперь соответствующую теорию называют примитивно рекурсивной арифметикой.</footnote>
( scheme 2) on c. 179). Geдель использует представление этих функций в формальной системе для «арифметизации» утверждений о выводимости, так что для него они являются не предметом исследования, а средством.

Но как быть с более общими видами рекурсии (например, из упомянутого результата Аккермана)? Эрбран предложил (в письме Гёделю, а также в работе [76]) рассматривать системы функциональных уравнений (связывающих определяемые функции с построенными ранее), которые однозначно определяют новые функции. В его статье это формулируется так [76, с. 5, с. 624 английского перевода]:

Мы можем также ввести произвольное количество функций $f_i(x_1, \dots, x_{n_i})$ вместе с утверждениями о них, если:

(а) эти утверждения не содержат связанных переменных;

(б) рассматриваемые с интуиционистской точки зрения, то есть как утверждения о натуральных числах, а не просто как символы, эти утверждения позволяют вычислить значение $f_i(x_1, \dots, x_{n_i})$ для любого набора числовых аргументов, и можно интуиционистски доказать, что результат однозначно определён.

Смысл этой оговорки про «интуиционистскую точку зрения», видимо, в том, что нас не устроит само по себе функциональное уравнение, про которое из каких-то общих соображений можно доказать, что его решение существует и единственно; нужно, чтобы это доказательство было в каком-то смысле конструктивно и давало способ вычисления значений интересующих нас функций, исходя из задающих их равенств. (И действительно, впоследствии Кальмар [89] привёл пример системы функциональных уравнений, однозначно задающей невычислимую функцию.)

Гёдель возвращается к предложению Эрбрана (погибшего в горах сразу после отправки в редакцию статьи [76]) в своих лекциях в Принстоне (записки которых были размножены ещё тогда, а позднее перепечатаны, см. [77]). Он по-прежнему называет «рекурсивными» функции, которые получаются из базовых с помощью подстановок и «обычных» рекурсий, но в разделе 9 говорит о рекурсивных определениях более обще-го вида и задаваемых ими функциях, называя их “general recursive functions”. Гёдель воспроизводит предложение Эрбрана так:

One may attempt to define this notion [general recursive function] as follows: if $\phi$ denotes an unknown function, and $\psi_1, \dots, \psi_k$ are known functions, and if the $\psi$'s and the $\phi$ are substituted in one another in the most general fashions and certain parts of the resulting expressions are equated, then if the resulting set of functional equations has one and only one solution for $\phi$, $\phi$ is a recursive function.”

(В примечании к этому определению Гёдель ссылается на письмо Эрбрана.) Далее он добавляет ограничения, уточняющие замысел Эрбрана:

We shall make two restrictions on Herbrand's definition. The first is that the left-hand side of each of the given functional equations defining $\phi$ shall be of the form

$$ \phi(\psi_{i1}(x_1, \dots, x_n), \psi_{i2}(x_1, \dots, x_n), \dots, \psi_{il}(x_1, \dots, x_n)). $$

The second (as stated below) is equivalent to the condition that all possible sets of arguments $(n_1, \dots, n_l)$ of $\phi$ can be so arranged that the computation of the value of $\phi$ for any given set of arguments $(n_1, \dots, n_l)$ by means of the given
equations requires a knowledge of the values of $\phi$ only for sets of arguments which precede $(n_1, \dots, n_l)$.

Гёдель не уточняет порядок на наборах аргументов, так что точный смысл этого не очень ясен. Но дальше описываются конкретные правила вывода одних равенств из других и говорится:

> Now our second restriction on Herbrand's definition of recursive function is that for each set of natural numbers $k_1, \dots, k_l$ there should be one and only one $m$ such that $\phi(k_1, \dots, k_l) = m$ is a derived equation.

Тем самым даётся вполне точное определение некоторого класса функций, названных "general recursive functions"; по-русски обычно переводят этот термин (немного загадочно) как «общерекурсивные функции». Однако, как пишет Клини в [105], в момент чтения лекций (1934) сам Гёдель ещё не был уверен в том, что этот класс функций достаточно широк: «However, Gödel, according to a letter he wrote to Martin Davis on 15 February 1965, "was, at the time of [his 1934] lectures, not at all convinced that [this] concept of recursion comprises all possible recursions"» [105, p. 48]. В [99, p. 40] про это говорится так:

> In the present article [речь идёт о [77]] Gödel shows how an idea of Herbrand's can be modified so as to give a general notion of recursive function ($\dots$) Gödel indicates (cf. footnote 3) that he believed that the class of functions obtainable by recursion of the most general kind were the same as those computable by a finite procedure. However, Dr. Gödel has stated in a letter that he was, at the time of these lectures, not at all convinced that his concept of recursion comprised all possible recursions; and that in fact the equivalence between his definition and Kleene's in Math. Ann. 112 [речь идёт о [80]] is not quite trivial. So despite appearances to the contrary, footnote 3 of these lectures is not a statement of Church's thesis.

Footnote 3 [99, p. 44] относится к утверждению о том, что всякая примитивно рекурсивная функция может быть вычислена с помощью конечной процедуры, и говорит "The converse seems to be true, if, besides recursions according to the scheme (2) [примитивная рекурсия], recursions of other forms (e.g., with respect to two variables simultaneously) are admitted. This cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle".

Роза Петер в [78] изучает возможности «обычных рекурсий» (например, доказывает, что разрешение использовать несколько значений функции в меньших точках сводится к схеме с одним предшественником) и вводит термин "primitive Recursion" для этих самых «обычных рекурсий».

Следуя ей, Клини в 1936 году [80] вводит термин "primitive recursive functions" (примитивно рекурсивные функции) для тех функций, которые получаются с помощью подстановок и примитивных рекурсий и которые Гёдель в [75] называл просто «рекурсивными». Одновременно Клини предлагает рассмотреть более общий класс функций, элементы которого он называет "general recursive functions" (его статья так и называется, *General recursive functions of natural numbers*). Этот класс определяется в духе Эрбрана и Гёделя, при этом рассматриваются разные правила вывода одних равенств из других, которые, однако (как доказывает Клини), задают один и тот же класс функций.
Клини также вводит ε-оператор $εx[A(x)]$ как наименьшее число, удовлетворяющее условию $A(x)$, если таковое существует; в противном случае берётся нуль. Этот оператор фигурирует в теореме IV, которая утверждает, что всякая общерекурсивная функция может быть представлена в виде $ψ(εy[R(x, y)])$, где ψ—некоторая примитивно рекурсивная функция, а *R* — примитивно рекурсивный предикат (это означает, что предикат *R* записывается как равенство нулю некоторой примитивно рекурсивной функции), причём для всякого х существует у, при котором $R(x, y)$.<fnref n="3" /> Теорема V утверждает, что верно и обратное: всякая функция, представимая в указанном виде, рекурсивна в смысле определений в духе Эрбрана и Гёделя. Тем самым такое представление может рассматривать как эквивалентное определение понятия рекурсивной функции. Кроме того, из этого можно извлечь некоторый способ нумерации всех рекурсивных функций, введя дополнительный параметр *ε* в примитивно рекурсивный предикат *R* (хотя не при всех *ε* получается всюду определённая функция; можно было бы сказать, что нумеруются частичные функции, но пока Клини их не рассматривает).

В том же (1936) году Чёрч публикует статью [79], в которой приводит другое определение некоторого класса числовых функций (в терминах так называемого λ-исчисления) как формализацию интуитивной идеи вычислимости:

> The purpose of the present paper is to propose a definition of effective calculability<fnref n="3" />
> which is thought to correspond satisfactorily to the somewhat intuitive notion.

В подстрочном примечании (³) Чёрч пишет:

> As will appear, this definition of effective calculability can be stated in either
> of two equivalent forms, (1) that a function of positive integers shall be called
> effectively calculable if it is λ-definable in the sense of §2 below, (2) that a
> function of positive integers shall be called effectively calculable if it is recursive
> in the sense of §4 below. The notion of λ-definability is due jointly to the present
> author and S.C. Kleene (...). The notion of recursiveness in the sense of §4 is
> due jointly to Jacques Herbrand and Kurt Gödel (...). The proposal to identify
> these notions with the intuitive notion of effective calculability is first made in
> the present paper...

и добавляет (примечание в §7):

> The question of the relationship between effective calculability and recursiveness
> (which it is here proposed to answer by identifying the two notions) was raised
> by Gödel in conversation with the author. The corresponding question of the
> relationship between effective calculability and λ-definability had previously
> been proposed by the author independently.

Видно, что Чёрч считает важным делом отождествление интуитивного понятия вычислимости с принадлежностью к точно определённому классу функций (для которого есть два эквивалентных определения). Это отождествление и назвали потом тезисом Чёрча.

Почти в то же время Тьюринг публикует свою работу [82], в которой он определяет машины, называемые теперь машинами Тьюринга (сам Тьюринг употребляет термин *a-machine*, от слова 'automatic'), и строит универсальную машину (которая

<footnote n="3">³Та часть в определения ε-оператора, где результат полагается равным нулю, когда искомого у не существует, при этом роли не играет. Таким образом, здесь можно заменить ε-оператор на стандартный μ-оператор, в котором значение считается неопределённым в случае отсутствия искомого у.</footnote>
может моделировать любую машину, будучи снабжена подходящей программой). В терминах этих машин Тьюринг определяет класс вычислимых действительных чисел (те, знаки которых могут вычисляться машиной) и даёт своё доказательство неразрешимости Entscheidungsproblem (нет алгоритма, который распознаёт общезначимость формул языка первого порядка; ранее это—для эквивалентных определений вычислимости—доказали Гёдель и Клини, а также Чёрч, см. подробнее в [99, р.109]).

В приложении (Appendix), добавленном 28 августа 1936 года, Тьюринг намечает доказательство эквивалентности вычислимости последовательности с помощью предложенных им машин и λ-определимости. Описывая этот результат во введении к работе, он пишет:

> In a recent paper Alonzo Church has introduced an idea of “effective calculability”, which is equivalent to my “computability”, but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem. The proof of equivalence between “computability” and “effective calculability” [имеется в виду λ-определимость] is outlined in an appendix to the present paper.

Независимо от Тьюринга и почти одновременно с ним Пост публикует работу [81], где описывает своё определение «финитного комбинаторного процесса», отличающееся от машин Тьюринга лишь техническими деталями, а также тем, что он не говорит о машине, а описывает, как “problem solver or worker” следует указаниям (the set of directions) определённого вида. Далее Пост замечает:

> The writer expects the present formulation to turn out to be logically equivalent to recursiveness in the sense of the Gödel–Church development. Its purpose, however, is not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity. In the latter sense wider and wider formulations are contemplated. On the other hand, our aim will be to show that all such are logically equivalent to formulation 1 [предложенный Постом вариант определения]. We offer this conclusion at the present moment as a working hypothesis. And to our mind such is Church’s identification of effective calculability with recursiveness. (...) The success of the above program would, for us, change this hypothesis not so much to a definition or to an axiom but to a natural law.

И добавляет в примечании:

> Actually the work already done by Church and others carries this identification considerably beyond the working hypothesis stage. But to mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.<fnref n="4" />

Видно, что к 1936 году уже сложилась почти что современная картина: есть несколько эквивалентных (задающих один и тот же класс функций) определений вычислимости, есть понимание, что они отражают интуитивную идею алгоритма и вряд ли что-то упущено (и даже есть некоторые интуитивные объяснения, почему это так).

<footnote n="4">⁴Сейчас, пожалуй, это фундаментальное открытие (fundamental discovery) уже практически утрачило смысл: чтобы говорить о соответствии интуитивной идеи вычислимости (идеи алгоритма в неформальном смысле этого слова) и формально определённого класса алгоритмов, нужно, чтобы эта интуитивная идея была сформирована независимо от программистского опыта — а где теперь найти людей, которые бы познакомились с идеей алгоритма, не имея уже программистского опыта?</footnote>
Но есть два отличия от современной картины: одно скорее терминологическое, а другое более принципиальное. Терминологическое состоит в том, что ни в одной из работ, говорящих о рекурсивных функциях, они не определяются как функции, получаемых с помощью подстановки, рекурсии и μ-оператора, хотя все ингредиенты для доказательства эквивалентности этого определения другим есть и сама эквивалентность явно упоминается Клини в 1943 году [85, р. 53, Corollary].

Во вторых, во всех этих работах говорится о **всюду определённых функциях** (опредёлённых на всех натуральных числах). **Частичные функции** появляются чуть позже, в другой работе Клини [83], где строятся вычислимые системы обозначений для ординалов (тут без частичных функций уже не обойтись). Описав процесс вывода утверждения о значении функции из равенств в духе Эрбрана и Гёделя и предположив, что он даёт не более одного ответа для искомого значения, он пишет:

> If we omit the requirement that the computation process always terminate, we obtain a more general class of functions, each function of which is defined over a subset (possibly null or total) of the *n*-tuples of natural numbers, and possesses the property of effectiveness when defined. These functions we call partial recursive.

Таким образом впервые появляется понятие **частично рекурсивной функции** (partial recursive function).<fnref n="5" /> Клини рассматривает (естественным образом обобщаемые на частичные функции) операции подстановки и рекурсии, а также определяет действие μ-оператора для случая частичной функции:

$$ \mu y[R(m, y) = 0] = n $$

для частичной функции *R*, если *R(m, n)* определено и равно нулю, а все предыдущие значения *R(m, 0), ..., R(m, n - 1)* определены и не равны нулю. (Очевидно, что такое *n* единственно, если существует; если же нет, то определяемая с помощью μ-оператора функция не определена на *m*.) Как отмечает Клини, все три операции (подстановка, рекурсия и μ-оператор) не выводят из класса частично рекурсивных функций (определённых по Эрбрану и Гёделю). Он отмечает также, что для класса частично рекурсивных функций от любого числа (*n*) переменных существует универсальная функция Φ<sub>n</sub>(z, x) от *n* + 1 переменной. (Универсальность означает, что фиксацией первого аргумента *z* из Φ<sub>n</sub> можно получить любую частично рекурсивную функцию от *n* переменных.) Эта универсальная функция может быть представлена в виде

$$ \Phi_n(z, \mathbf{x}) = S(z, \mu y T_n(z, \mathbf{x}, y)) $$

где *S* — некоторая примитивно рекурсивная функция, а *T*<sub>*n*</sub> — некоторый примитивно рекурсивный предикат (задаваемый условием обращения в нуль некоторой примитивно рекурсивной функции). В этом представлении, неформально говоря, *z* кодирует (в виде натурального числа) систему равенств, задающих частично рекурсивную (в смысле Эрбрана и Гёделя) функцию от *n* переменных, а *y* является протоколом вывода из этой системы равенств утверждения о значении функции на входе **x**. Предикат *T*<sub>*n*</sub> проверяет корректность этого вывода, а функция *S* извлекает из этого вывода установленное значение функции.<fnref n="6" /> Из этого результата (который называют «теоремой Клини

<footnote n="5">⁵Русский термин тут, пожалуй, ещё более странный, чем слово «общерекурсивные» для всюду определённых вычислимых функций: создаётся впечатление, что функция лишь отчасти рекурсивна. Английский термин лучше, потому что в нём слово 'partial' относится к слову 'function'.</footnote>

<footnote n="6">⁶В формулировке Клини есть ещё первый аргумент *z* у функции *S*, но его можно было бы и опустить.</footnote>
о нормальной форме») уже вытекает, что можно эквивалентно определить частично
рекурсивные функции с помощью подстановки, рекурсии и μ-оператора (и даже допол-
нительно потребовать, чтобы μ-оператор применялся только один раз к примитивно
рекурсивной функции). Но такой вариант определения Клини по-прежнему не упоми-
нает.

Примерно эта же система понятий, терминология и способ изложения используются
в более поздней статье Клини [85], посвящённой в основном арифметической иерархии,
и в его же учебнике 1952 года [65], ставшем на многие десятилетия классическим. От-
метим, помимо сказанного выше, ещё одну непривычную для нас вещь: формулировка
«тезиса Чёрча» (отождествление интуитивной идеи вычислимой функции с точно опре-
делённым классом функций) относится только к всюду определённым функциям.

Относительная вычислимость (вычислимость с оракулом)

Можно определить относительную вычислимость одной функции относительно другой
(или относительно некоторого множества, которое можно отождествить с его харак-
теристической функцией). Впервые обсуждаемое определение сводимости предложил
Тьюринг в своей диссертации (1939, см. [84]), но это было там побочной темой и рас-
сматривалось лишь в некотором частном случае (сводимость к некоторому конкретно-
му множеству). Он пишет:

Let us suppose that we supplied with some unspecified means of solving number-
theoretic problems; a kind of oracle as it were. We will not go any further into the
nature of this oracle than to say that it cannot be a machine. With the help of
the oracle we could form a new kind of machine (call them o-machines), having
as one of its fundamental processes that of solving a given number-theoretic
problem. More definitely these machines are to behave in this way. The moves of
the machine are determined as usual by a table except in the case of moves from
a certain internal configuration o. If the machine is in the internal configuration
o and if the sequence of symbols marked with l is then the well formed formula
A, then the machine goes into the internal p or t according as it is or is not true
that A is dual. The decision as to which is the case is referred to the oracle.

These machines may be described by tables of the same kind as used for the
description of *a*-machines, there being no entries, however, for the internal
configuration *o*.

Общее определение сводимости по Тьюрингу предложил Пост в своей знаменитой статье [86, раздел 11] — той самой, в которой он сформулировал проблему Поста о существовании перечислимого неразрешимого множества, не являющегося полным (к которому сводятся не все перечислимые множества). Формально говоря, Пост в своём определении ограничивается сводимостью одного перечислимого множества к другому, но реально требование перечислимости в его тексте не используется. Определение Поста следует схеме Тьюринга и использует машины с оракулом. Клини в статье 1943 года [85] предлагает другой вариант определения: к определению общерекурсивных функций с помощью выводов в исчислении равенств можно добавить равенства, выражающие таблицу значений для произвольных (всюду определённых) функций ψ₁, ..., ψₖ, и назвать те функции, которые можно определить таким способом, общерекурсивными относительно ψ₁, ..., ψₖ:

A function $\phi$ which can be defined from given functions $\psi_1, \dots, \psi_k$ by a series of
applications of general recursive schemata we call *general recursive* in the given
functions; and in particular, a function $\phi$ definable ab initio by these means we
call *general recursive*.

Но это описание дальше не развивается и не используется, оставаясь лишь пояснением
к даваемому дальше определению, и для частично рекурсивных функций (в отличие
от общерекурсивных) относительная вычислимость не рассматривается. В книге 1952
года Клини говорит и о частичных функциях и их вычислимости и доказывает, что
такое определение относительной вычислимости (с выводами в исчислении равенств
по Эрбрану и Гёделю) эквивалентно определению Тьюринга-Поста [65, §69]. При этом
оракул должен быть всюду определённой функцией (или набором таких функций). Но,
в отличие от статьи Поста, где рассматривались лишь перечислимые множества в каче-
стве оракулов, эта функция может быть произвольной всюду определённой функцией.

Обзор различных определений относительной вычислимости можно найти в [109,
Section 4.3, "History of Relative Computability").

Теперь мы можем указать, в чём была новизна работы Успенского:<fnref n="7" />

* впервые было явно указано (со ссылкой на Трахтенброта—видимо, на неопубли-
кованное сообщение) простое определение частичной рекурсивности, абсолютной
и относительной, с помощью операций подстановки, рекурсии и минимизации ($\mu$-
оператора);

* была доказана (одновременно с книгой Клини [65] и гораздо более отчётливо)
эквивалентность этого определения с другими определениями вычислимости (аб-
солютной и относительной);

* было дано (впервые) определение относительной вычислимости, не связанное ни
с какой конкретной вычислительной моделью, а использующее лишь класс вы-
числимых функций, и доказана эквивалентность этого определения другим опре-
делениям относительной вычислимости;

* наконец, в дипломной работе Успенского была впервые изложена конструкция
машин Колмогорова (позже опубликованная в совместной статье Колмогорова и
Успенского [16]), дано определение относительной вычислимости в терминах этой
модели и доказана эквивалентность этого определения другим.

Третий пункт этого перечня требует некоторых пояснений. Определение Тьюри-
nga-Поста для относительной вычислимости является модификацией соответствую-
го определения для абсолютной вычислимости: мы расширяем класс машин Тьюринга,
дополнительно разрешая получать ответы от оракула. Аналогичным образом опреде-
ление Клини для относительной вычислимости модифицирует определение частично
рекурсивной функции. Таким образом, даже если мы договорились, какие функции
мы считаем (абсолютно) вычислимыми, нам нельзя ещё забыть про конкретную мо-
дель вычислений и не возвращаться к ней: определяя относительную вычислимость,
надо снова вспомнить о модели и её модифицировать. В отличие от этой ситуации,
в определении из работы Успенского относительная вычислимость определяется с по-
мощью алгоритмов диалога с оракулом, то есть требуется вычислимость некоторых
(частичных) функций, задающих этот диалог (функций, указывающих следующий во-
прос к оракулу при известном входе, предыдущих вопросах и ответах на них). Таким

<footnote n="7">⁷К сожалению, дипломная работа не была опубликована, несмотря на рекомендации в отзывах, так что вряд ли повлияла на дальнейшее развитие событий, но тем не менее.</footnote>
образом, для понимания смысла этого определения достаточно знать, какие функции считаются вычислимыми.

Впоследствии такого рода («машинно-независимые») определения относительной вычислимости были даны другими авторами. Например, одно из них можно найти в учебнике Роджерса [70, раздел 9.2] (без ссылки на каких бы то ни было предшественников). Можно ещё отметить, что определение Успенского имеет то преимущество, что оно (в отличие от определения из книги Роджерса) естественно распространяется на произвольные частичные оракулы и при этом сохраняется эквивалентность с принадлежностью частично рекурсивному замыканию функции, использованной как оракул. Но сам Успенский этого не делает, рассматривая только функции с перечислимой областью определения (хотя доказательство для общего случая не требует существенных изменений).

## Теорема Гёделя и теория алгоритмов

Теорема Гёделя и теория вычислимых функций появились не только одновременно, но и вместе, как сиамские близнецы. В классической статье Гёделя, где доказан его результат о неполноте формальных теорий, одновременно было введено понятие рекурсивной функции (то, что теперь называется «примитивно рекурсивными» функциями, см. выше), и это понятие было важным техническим средством в доказательстве. А именно, различные функции, связанные с кодированием формул и выводов натуральными числами (их «гёделевыми номерами», как раньше говорили), были определены рекурсивно, и это определение использовалось для погружения рассуждений о выводах в формальную систему.

С другой стороны, определение общерекурсивных функций было дано в терминах формальной системы (исчисления равенств), восходящей к Эрбрану и Гёделю.

Можно, пожалуй, сказать, что одним из первых достижений и в области теории вычислений, и в области теории доказательств, было разделение этих «сиамских близнецов», и было это не таким простым делом, как сейчас кажется. Сначала Тьюринг и Пост предложили модель вычислений (машины Тьюринга–Поста), позволившую определить вычислимость безо всякого упоминания формальных теорий и выводов в них. Общая природа теоремы Гёделя и её связи с теорией алгоритмов были осознаны в 1940-е годы, видимо, в первую очередь Клини и Колмогоровым.

В статье Клини 1943 года [85] была указано, что теорема Гёделя по существу означает неперечислимость множества истинных формул, а в статье 1950 года [87] аналогичная интерпретация была дана для теоремы Гёделя в форме Россера и указано, что она соответствует построению пары эффективно неотделимых перечислимых множества. Но хотя по существу все необходимые наблюдения были уже сделаны, по форме изложение Клини и в этой статье 1950 года, и в классическом учебнике 1952 года [65] остаётся ещё тесно связанным с языком теории примитивно рекурсивных функций (достаточно сказать, что изложение в [87] начинается словами “Let $T_1$ be the primitive recursive predicate so designated in a previous paper by the author”), и процедура погружения неотделимых множеств в формальную теорию скорее подразумевается, чем явно описана.

Примерно в то же время, и, вероятно, независимо к пониманию соотношения между теоремой Гёделя и теорией алгоритмов пришёл Колмогоров. Как рассказывает Успенский в [51, с. 323],

> 2 декабря 1952 г. Колмогоров изложил мне весьма кратко, в течение пяти минут, — но зато дал списать с заготовленной им бумажки, озаглавленной
«Гёдель и рекурсивная перечислимость», — основополагающие идеи о связи теоремы Гёделя о неполноте аксиоматических систем (для самых общих исчислений) с существованием множеств, не являющихся рекурсивными, и пар множеств, не являющихся рекурсивно отделимыми. Бумажка была написана им «для себя», и разобраться в ней, а тем более в его сопутствующих устных комментариях, мне было тогда непросто. Потом всё как-то выстроилось, и 8 мая 1953 г. Колмогоров представил в «Доклады АН СССР» мою заметку «Теорема Гёделя и теория алгоритмов», написанную на основе его идей. Высокое искусство Колмогорова как учителя состояло в умении создать у ученика впечатление, что именно он, ученик, полноценный автор статьи. Колмогоров во много раз реже, чем имел на это все права, выступал в роли соавтора своих учеников (...). В 1958 г. в «Успехах математических наук» под двумя нашими фамилиями вышла статья «К определению алгоритма», в которой мне принадлежит, по существу, лишь черновая работа.

(Статьи, о которых идёт речь: [6, 16]. Вторая из них содержит изложение вычислительной модели с преобразованием графов, которая фигурировала уже в дипломной работе Успенского.)

В статье Успенского 1953 года [6] было отчётливо указано, уже без всякого упоминания о примитивно рекурсивных функциях, что теорема Гёделя о том, что достаточно богатая формальная система (скажем, формальная арифметика) неполна и не может быть пополнена, следует из того, что существуют перечислимые неотделимые множества и что эта пара множеств погружается в формальную систему — как сейчас сказали бы, сводится к паре (доказуемые формулы, опровержимые формулы). А эффективная непополнимость (тот факт, что по расширению формальной системы дополнительными аксиомами можно алгоритмически указать формулу, которая остаётся недоказуемой и неопровержимой) следует из существования эффективно неотделимых перечислимых множеств. Но, повторим ещё раз, всё это по существу уже было в работе Клини [87], о которой Колмогоров и Успенский, судя по всему, тогда не знали. Успенский ссылается на работу Клини 1943 года [85], говоря о рекурсивных функциях, но говоря о существовании перечислимых неотделимых множеств, не ссылается на [87], где они построены, а говорит лишь, что они были построены Новиковым (не указывая никакой публикации Новикова, а лишь давая ссылку на работу Трахтенброта 1953 года).

Говоря о ситуации в целом, можно сказать, что есть два взаимно дополнительных взгляда на теорему Гёделя. С одной стороны, она является реализацией парадокса лежащего (в одном из вариантов он говорит, что утверждение «Это утверждение ложно» не может быть ни ложным, ни истинным): если вместо этого сделать утверждение «Это утверждение недоказуемо», то оно будет истинным (и потому неопровержимым), но недоказуемым. Это объяснение не ссылается на теорию алгоритмов, хотя для обоснования возможности записать неформальные рассуждения в формальной арифметике можно, следуя Гёделю, использовать примитивно рекурсивные функции как техническое средство. С другой стороны, теорема Гёделя является следствием существования неразрешимых перечислимых множеств (или, в симметричном варианте, существования неотделимых перечислимых множеств), и в таком изложении никакой «самоприменимости» не заметно. Но, конечно, она никуда не делась, переместившись в конструкцию неразрешимого перечислимого множества (или неотделимых множеств). Эта конструкция следует идее «диагонального аргумента» Кантора, которая, в свою очередь, является формой проявления самоприменимости («диагональ» состоит из результатов применения вычислимой функции к своему номеру, или алгоритма к его собственному тексту).
Впоследствии Успенский опубликовал подробное изложение доказательства теоремы Гёделя с помощью средств теории алгоритмов (а также изложение начал этой теории) сначала в виде статьи [22], а затем (в расширенном виде) брошюры [25] в серии «Популярные лекции по математике». Это изложение до сих пор остаётся, пожалуй, наиболее доступным и корректным изложением теоремы Гёделя для неспециалистов (по крайней мере если говорить о её алгоритмическом аспекте).

Помимо этого, в [22, 25] была намечена (совсем не очевидная в то время, достаточно сравнить с тем же учебником Роджерса [70]) схема изложения теории алгоритмов. Традиционно (в том числе и в книге самого Успенского [18]) изложение теории алгоритмов начиналось с подробного разбора какой-то вычислительной модели (сначала в этом качестве были популярны рекурсивные функции, потом машины Тьюринга; Марков использовал для этого нормальные алгорифмы), и это занимало достаточно много места и времени. Лишь после этого оставшиеся слушатели (читатели) знакомились с простейшими фактами вроде теоремы Поста (перечислимое множество с перечисляемым дополнением разрешимо), и т.п. Конечно, можно было пропустить первую часть, с построением конкретной вычислительной модели, и начинать прямо со второй, рассуждая как в анекдоте о беспроволочном телеграфе («представьте себе длинную кошку, которую в одном городе дёргают за хвост, а в другом она мяукает — это проволочный телеграф, — а теперь то же самое, но без кошки»), тогда рассуждения становились простыми и наглядными, но беспочвенными.

Выход, предложенный Успенским в [22] (а до этого использованный в его лекциях 1972/3 года, но, вероятно, и в предыдущие годы), состоял в следующем: мы рассуждаем о классе вычислимых функций, приняв на веру (в качестве «аксиом») некоторые свойства этого класса, отчётливо сформулированные, но оставленные без доказательства. Помимо вычислимости конкретных функций (а также сохранения вычислимости при конкретных построениях одних функций из других), Успенский выделяет два таких свойства, называя их «аксиомой протокола» и «аксиомой программы».

**Аксиома протокола** утверждает, что для всякого алгоритма А существует разрешимое множество *R*, элементы которого называются «протоколами», и две вычислимые функции $\alpha$ и $\omega$. Неформально говоря, элементы *R* являются протоколами (программисты сказали бы: «логами») вычисления алгоритма А, то есть записями всех последовательных шагов его работы на некотором входе, в тех случаях, когда эта работа завершается и даёт какой-то результат. Функция $\alpha$ выделяет из протокола исходное данное (вход), а $\omega$ — результат работы (выход). Формально же требуется выполнение такого свойства: выход алгоритма А на входе *x* равен *y* тогда и только тогда, когда существует $r \in R$, для которого $\alpha(r) = x$ и $\omega(r) = y$.

**Аксиома программы** утверждает, что есть некоторое разрешимое множество *P*, элементы которого называются «программами», и алгоритм *U* применения произвольной программы $p \in P$ к произвольному входу *x* (таким образом, входом алгоритма *U* является пара $(p, x)$). При этом любая вычислимая функция *f* задаётся некоторой программой *p* в том смысле, что $U(p, x) = f(x)$ для всех *x*. Последнее равенство понимается так: обе его части одновременно определены или одновременно не определены, и равны в том случае, когда определены.

Приняв эти аксиомы, можно развивать теорию алгоритмов, не вдаваясь в технические детали модели вычислений. Вместе с тем остаётся совершенно понятно, чего недостаёт в этих рассуждениях: мы должны указать конкретную модель вычисления, научиться в ней программировать те конструкции, которые использованы в доказательствах (и которые не так уж и просты, достаточно вспомнить, скажем, метод приоритета), а также проверить выполнение аксиом протокола и программы для этой мо-
дели вычислений. Конечно, и после этого некоторый психологический барьер остаётся (многим людям, которые легко ориентируются в достаточно сложных математических конструкциях, теория вычислимости всё же кажется чем-то странным), но по крайней мере он становится более явным и отчётливо видным.<fnref n="8" />

Для доказательства теоремы Гёделя нужна и третья аксиома, не следующая из этих двух— что всякую вычислимую функцию можно выразить арифметической формулой (и тут снова приходится обращаться к конкретной модели вычислений).

Заметим, что при таком «машинно-независимом» изложении теории вычислимости мы не имеем права вновь возвращаться к вычислительной модели, рассуждая, скажем, о преобразованиях программ или о вычислениях с оракулом, а должны давать все необходимые определения, ссылаясь только на понятие вычислимой функции. Как мы уже говорили, такое определение для относительной вычислимости было (впервые) дано Успенским в дипломной работе, затем это было сделано для сводимости по перечислимости, а также для «способов программирования» (формализацией которых стало введённое Успенским понятие главной нумерации). Об этих двух последних достижениях Успенского мы говорим в следующем разделе.

Ещё можно отметить, что эта аксиоматизация теории алгоритмов позволяет строго обосновать известное наблюдение о том, что большинство результатов теории алгоритмов «релятивизуются», то есть сохраняют силу, если вычислимые функции заменить функциями, вычислимыми с некоторым фиксированным оракулом (в качестве которого можно взять множество или всюду определённую функцию). В самом деле, достаточно проверить, что для этого релятивизованного класса (функций, вычислимых с данным оракулом) выполнены все аксиомы теории алгоритмов (кроме свойства арифметичности, естественно), и потому выполнены и все теоремы, выводимые из этих аксиом. Успенский поставил вопрос, полностью ли объясняет это наблюдение возможность релятивизации, то есть верно ли, что всякое утверждение, выполненное для всех классов вычислимых с некоторым оракулом функций, является следствием указанных им аксиом. Оказалось, что когда этот вопрос поставлен, получить на него (положительный) ответ уже несложно [104].

## Вычислимые отображения множеств и сводимость по перечислимости

Понятие сводимости, введённое Тьюрингом и Постом и рассмотренное в дипломной работе Успенского (см. выше), можно назвать «сводимостью по разрешимости»: сводимость множества А к множеству В гарантирует, что если В разрешимо, то и А разрешимо. Можно сказать, что в этом определении мы «сводим задачу разрешения множества А к задаче разрешения множества В». В работе [9] Успенский предлагает определение сводимости по перечислимости, в котором речь идёт о сведении задачи перечисления множеств А к задаче перечисления другого множества В. Это опре-

<footnote n="8">⁸Сейчас ситуация с методической точки зрения изменилась, прежде всего потому, что большинство приступающих к изучению теории вычислимых функций уже имеют программистский опыт. Возможно, современная реализация педагогических идей Успенского состояла бы в том, что мы предлагаем слушателям представить себе знакомый им язык программирования, к которому добавлены библиотечные функции интерпретатора этого же языка (аргументами которого являются строка, понимаемая как программа, и вход; это соответствует аксиоме программы), а также пошагового отладчика (который комбинирует аксиому программы с аксиомой протокола; на вход ему подаются текст программы, вход и число шагов работы отлаживаемой программы). Если к этому добавить ещё и функцию (без аргументов), выдающую текст текущей исполняемой программы, это облегчит и доказательство теоремы о неподвижной точке, сделав её самоочевидной.</footnote>
деление использует введённой в этой же работе понятие вычислимой операции над множествами.

В простейшем случае (одноместная операция, аргументами и значениями которой являются подмножества натурального ряда) вычислимые операции определяются так. Введём на множестве $P(\mathbb{N})$ всех подмножеств натурального ряда топологию. Для каждого конечного множества $X \subset \mathbb{N}$ рассмотрим семейство $O(X)$ всех его надмножеств, и будем считать открытыми в $P(\mathbb{N})$ все такие семейства и все их объединения. Теперь рассмотрим все непрерывные в смысле этой топологии отображения $F: P(\mathbb{N}) \to P(\mathbb{N})$. Легко проверить, что все такие отображения монотонны (если $U \subset V$, то $F(U) \subset F(V)$), и значение $F$ на любом множестве $U$ определяется значениями $F$ на конечных подмножествах $U$ (надо объединить $F(X)$ для всех конечных $X \subset U$). Значения $F$ на конечных множествах можно описать множеством пар $\{\langle n, X \rangle \mid n \in F(X)\}$ (здесь $n$—натуральное число, а $X$—конечное множество натуральных чисел). Непрерывное отображение $F: P(\mathbb{N}) \to P(\mathbb{N})$ Успенский называет вычислимой операцией, если соответствующее ему множество пар перечислимо (заметим, что эти пары являются конечными объектами, так что можно говорить о перечислимости их множества). После этого определяется сводимость по перечислимости: множество А сводится по перечислимости к множеству В, если существует вычислимая операция F, переводящая В к А. Отмечается, что сводимость по Тьюрингу можно определить в терминах сводимости по перечислимости: всюду определённая функция $\varphi$ вычислима по Тьюрингу с оракулом для всюду определённой функции $\psi$ тогда и только тогда, когда график $\varphi$ сводится по перечислимости к графику $\psi$. Отсюда же получается и критерий сводимости множеств (переходом к их характеристикским функциям). Указывается, что в этих же терминах можно получить определить и понятие частично рекурсивного оператора в смысле Клини ([65], см. обсуждение ниже).

Наконец, в этой же работе указывается эквивалентность предложенного определения вычислимой операции с двумя «машинно-зависимыми» определениями. Соответствующие понятия Успенский называет «операциями Колмогорова» и «операциями Поста» (хотя в явном виде они в публикациях Колмогорова и Поста не встречаются).

В другой работе 1955 года ([10], см. также изложение результатов этой работы с некоторыми добавлениями в [12]) вводится (со ссылкой на доклад Колмогорова на семинаре по рекурсивной арифметике в 1954 году) понятие нумерации, определяется понятие главной нумерации системы перечислимых множеств и устанавливается связь вычислимых операций на перечислимых множествах в смысле [9] с алгоритмическими преобразованиями номеров.

Более подробно. Пусть мы хотим говорить об алгоритмических преобразованиях программ вычислимых функций (или перечислимых множеств). Тогда нам мало знать, какие функции вычислимы (какие множества перечислимы), но нужно ещё и оговорить класс «способов программирования», используемых для записи их программ. Программы являются обычно словами в некотором алфавите, но их можно отождествить с натуральными числами (при какой-то естественной нумерации слов). Тогда способ программирования вычислимых функций превращается в универсальную функцию двух аргументов: $U(n, x)$ есть результат применения программы с номером $n$ в входу $x$, который мы тоже считаем натуральным числом. Способ программирования перечислимых множеств тогда становится универсальным множеством пар $\langle n, x \rangle$, для которых $x$ принадлежит перечислимому множеству, программа которого имеет номер $n$. На другом (но эквивалентном) языке можно сказать, что способ программирования вычислимых функций (перечислимых множеств) представляет собой натуральную нумерацию множества вычислимы функций (перечислимых множеств), то есть отображение всего на-
турального ряда на множество вычислимых функций (соответственно перечислимых множеств): числу $n$ ставится в соответствие вычислимая функция (перечислимое множество), программа которого имеет номер $n$.

Если не накладывать на способы программирования (нумерации) никаких ограничений, то оказывается, что не все они одинаково хороши. Разумная теория, описывающая алгоритмические преобразования программ, требует некоторых дополнительных ограничений. По существу они встречались в классических работах Клини (s-m-n-теорема), но явно впервые были сформулированы в [10]. А именно, требуется, чтобы нумерация была главной. Определение главной нумерации включает в себя два требования. Во-первых, нумерация должна быть вычислимой: это значит, что соответствующая универсальная функция является вычислимой (частичной) функцией двух аргументов (вариант для множеств: соответствующее универсальное множество пар должно быть перечислимым множеством пар). Во-вторых, к этой нумерации должна сводиться любая другая вычислимая нумерация.<fnref n="9" /> Это требование означает, что для любой другой вычислимой нумерации того же множества существует (всюду определённая) вычислимая функция, преобразующая номера в этой второй нумерации в номера в первой (главной).

Используя понятие главной нумерации для перечислимых множеств, можно рассмотреть вычислимые отображения семейства перечислимых множеств в себя. Вычислимость означает, что есть алгоритм, который по (любой) программе перечислимого множества даёт (какую-то) программу его образа. Другими словами, мы рассматриваем всюду определённые преобразования программ, которых сохраняют эквивалентность (эквивалентные программы, то есть программы, задающие одно и то же множество, преобразуются в эквивалентные программы). Успенский доказывает [10, раздел 6], что вычислимые отображения семейства перечислимых множеств в себя в точности представляют собой ограничения вычислимых операций (на семействе всех множеств) на класс перечислимых множеств. Аналогичное утверждение делается и для подсемейства униформных множеств пар (графиков функций): вычислимые отображения семейства вычислимых функций в себя представляют собой ограничения вычислимых операций, отображающих семейство униформных множеств в себя.

Опишем связи этих работ Успенского с работами других авторов того же периода.<fnref n="10" /> Райс [88] рассмотрел вполне перечислимые классы перечислимых множеств, то есть такие классы перечислимых множеств, для которых множество всех программ всех множеств этого класса перечислимо, и сформулировал гипотезу о том, что всякий такой класс состоит из всех надмножеств множеств из некоторого перечислимого семейства конечных множеств. Эта гипотеза приводится в [10] как теорема 5 и является ключевым шагом в доказательстве упомянутых результатов о вычислимых отображениях. Она также доказана в статье самого Райса 1956 года [92], где говорится, что

<footnote n="9">⁹Определение сводимости нумераций также опубликовано в [10] со ссылкой на доклад Колмогорова (видимо, впервые).</footnote>

<footnote n="10">¹⁰К сожалению (см. ниже отрывок из воспоминаний Успенского), все три публикации Успенского [9, 10, 12] представляют собой краткие заметки в Докладах Академии наук СССР (первые две) и резюме доклада в Московском математическом обществе (третья), где приводятся только формулировки теорем и лемм, используемых в их доказательствах. Сами доказательства были опубликованы в кандидатской диссертации Успенского [11], которая хотя формально и была доступна (ее можно было заказать и получить в нескольких библиотеках в СССР), но вряд ли повлияла на дальнейшее развитие области. Да и статьи с кратким изложением [9, 10, 12], видимо, остались неизвестными вне СССР. Позже книга Успенского [18] (учебник по теории вычислимых функций, который стал докторской диссертацией Успенского) была переведена на французский язык—к сожалению, в неё вошло лишь определение главной нумерации, но не результаты о вычислимых операциях и отображениях.</footnote>
независимо тот же результат получили МакНотон, Майхилл и Шапиро (ссылки на их
работы не приводятся, кроме ссылки на краткую заметку Майхилла [90]). Кроме того,
уже в первой статье Райса [88] доказано, что никакое нетривиальное свойство перечис-
лимых множеств нельзя алгоритмически распознать по его номерам (обобщение этого
результата сформулировано как следствие теоремы 5 в [10]). Это утверждение поэто-
му в англоязычной литературе называют обычно «теоремой Райса», а утверждение о
строении вполне перечислимых классов перечислимых множеств (и аналогичный ре-
зультат о вполне перечислимых классах вычислимых функций) называют «теоремой
Райса–Шапиро» (см., например, [106, глава 7, §2]). Результат о связи вычислимых
отображений класса вычислимых функций в себя и вычислимых операций на классе
функций (под названием “partial recursive functionals”) был доказан также Майхиллом
и Шепердсоном [91] в том же 1955 году, когда были опубликованы статьи Успенско-
го [9, 10] и потому в англоязычной литературе называется «теоремой Майхилла–Ше-
пердсона» (см., например, [106, глава 10, §2]. (Его частным случаем является теорема
Райса–Шапиро, поэтому она иногда тоже называется теоремой Майхилла–Шепердсо-
на, см., например, [108, Theorem II.4.2 или Proposition II.5.19].)

Трудно сказать, как было переоткрыто понятие сводимости по перечислимости; в
книге Роджерса 1967 года [70] соответствующее определение (“enumeration reducibility”)
приводится без каких бы то ни было ссылок на Успенского или кого-либо ещё. В ста-
тье [103] (“Enumeration reducibility and partial degrees”, 1971 года) даны ссылки на книгу
Роджерса и статью Майхилла [97], но в статье Майхилла (как и в книге Дэвиса [93], на
которую он ссылается) сводимость по перечислимости не определяется, а рассматрива-
ются различные варианты относительной вычислимости для функций. В современном
обзоре [111] работы Успенского вообще не упоминаются, а даётся ссылка на работу
Фридберга и Роджерса 1959 года [95], которая в свою очередь ссылается на записки
лекций Роджерса в МІТ 1955–56 годов, опубликованные (размноженные) в 1957 году, из
которых потом вышла книга [70]. Видимо, Роджерс чуть позже Успенского независимо
пришёл к тому же понятию (и с тем же названием).

Понятие главной нумерации также было переоткрыто Роджерсом (см. [94]). Род-
жерс называет это понятие “Gödel numbering”. Сначала он даёт «машинно-зависимое»
определение: “A Gödel numbering is a numbering equivalent to the standard numbering”
(с. 333), но потом приводит и машинно-независимую характеризацию (как максималь-
ый элемент относительно сводимости, как у Успенского—хотя и без ссылки на него).
В современной литературе иногда употребляется также термин “admissible numbering”,
см., например, недавнюю книгу Соара [112], а также “acceptable numbering” [108,
Definition II.5.2]; в обоих случаях приводится «машинно-зависимое» определение.

Сравнивая работы Успенского с другими публикациями на близкие темы, нужно
иметь в виду, что с определениями сводимости (относительной вычислимости) для
частичных функций имеется путаница, как терминологическая, так и по существу. Есть
три разных понятия вычислимости одной частичной функции относительно другой.
Пусть *f* и *g* — две частичные функции (с натуральными аргументами и значениями).
Сводимость *f* к *g* (вычислимость *f* относительно *g*) можно понимать в трёх смыслах
(каждый следующий сильнее предыдущего).

1. График *f* сводится по перечислимости к графику *g*.

2. Рассмотрим, следуя Успенскому, семейство $\mathcal{U}$ всех частичных функций из $\mathbb{N}$ в $\mathbb{N}$ с топологией, в которой базовыми открытыми множествами являются семейства всех продолжений некоторой конечной функции. Непрерывное отображение $F: \mathcal{U} \to \mathcal{U}$ мы будем называть вычислимой операцией, если его ограничение на
конечные функции имеет перечислимый график, то есть если множество всех пар $\langle\langle x, y\rangle, u\rangle$, где $x$ и $y$ — натуральные числа, а $u$ — конечная частичная функция из $\mathbb{N}$ в $\mathbb{N}$, и при этом $[F(u)](x) = y$, перечислимо. Теперь вычислимость $f$ относительно $g$ можно понимать как существование вычислимой операции, переводящей $g$ в $f$.

3. Можно распространить определение Трахтенброта (см. обсуждение дипломной работы выше) на частичные функции и говорить, что частичная функция $f$ вычислима относительно частичной функции $g$, если $f$ принадлежит частично рекурсивному замыканию множества частично рекурсивных функций, к которому добавлена функция $g$. (Это определение, например, приводится в [100].)

Третье определение имеет эквивалентную переформулировку в терминах машины с оракулом. Эта переформулировка по существу повторяет определение из дипломной работы Успенского, но для частичных функций. А именно, значение $f(x)$ вычисляется алгоритмом, который получает на вход $x$ и может запрашивать значения функции $g$ в произвольных точках, но как только одно из запрошенных значений $g$ окажется неопределённым, вычисление «авertsает» (прерывается без результата) и $f(x)$ остаётся неопределённым. Второй вариант определения можно тоже переформулировать в терминах машин, дополнительно разрешив параллельные запросы нескольких значений функции $g$; каждый из этих запросов не останавливает вычисление, которое продолжается и получает информацию о запрошенных значениях, если они определены, через какое-то время. При этом требуется, чтобы результат вычисления не зависел от того, через какое время поступят запрошенные значения.

Эти три определения различаются: каждое следующее сильнее предыдущего (более ограничительно). Разницу между этими определениями можно пояснить двумя примерами. Первый пример, разделяющий первый и второй варианты определения, таков. Пусть $f$ — произвольная всюду определённая функция, а $g$ — функция, принимающая только нулевые значения, и область определения функции $g$ состоит из всех номеров пар $\langle n, f(n) \rangle$ (для какой-то вычислимой нумерации пар). Тогда $f$ сводится к $g$ в смысле первого определения, но не обязательно сводится в смысле второго. (Это рассуждение приведено в примечании Успенского на с. 362 русского перевода книги Роджерса [70] со ссылкой на Д. Г. Скордева; приведённое Роджерсом рассуждение существенно сложнее.)

Второй пример [108, Proposition II.3.20, ссылка на диссертацию Sasso 1971 года] показывает разницу между вторым и третьим определениями. Пусть $g$ — произвольная частичная функция натурального аргумента, принимающая только нулевые значения. Построим другую частичную функцию $f$, которая тоже принимает только нулевые значения, при этом $f(n)$ определено (и равно нулю) тогда и только тогда, когда хода бы одно из значений $g(2n)$ и $g(2n + 1)$ определено. Тогда функция $f$ вычислима относительно $g$ в смысле второго определения, но не обязательно вычислима в смысле третьего. (В терминах машин: если разрешено параллельно запрашивать $g(2n)$ и $g(2n + 1)$, ожидая, пока один из этих запросов будет удовлетворён, то вычислить $f$ легко, но если можно лишь запрашивать их последовательно, то ничего не выйдет, потому что неудовлетворённый первый запрос помешает перейти ко второму. Конечно, это лишь неформальное пояснение, для доказательства различия нужно строить соответствующий пример функции $g$ диагональным методом, и это легко сделать.)

Первое определение соответствует тому, что в книге Роджерса [70, §9.8] названо «частичнорекурсивными операторами» (partial recursive operators). Второе соответствует тому, что названо там же «рекурсивными операторами» (recursive operators).
Майхилл и Шепердсон [91] говорят о “partial recursive functionals”, ссылаясь на Thesis I*† на с. 332 книги Клини [65], но этот тезис (начало страницы 332) не использует термин “partial recursive functional” и вообще этот термин на с. 332 не встречается. Предметный указатель этой книги [65] отсылает к с. 326 по слову “partial recursive functional”, но и эта страница не содержит соответствующего упоминания. Правда, на этой странице даётся определение частичной рекурсивности частичной функции $\varphi$ относительно частичных функций $\psi_1, \dots, \psi_k$, соответствующее сводимости графиков по перечислительности (первый вариант из приведённых выше трёх). и говорится о « scheme» F, но какие требования предъявляются к этой схеме (должна ли она давать функцию только в применении к функциям $\psi_1, \dots, \psi_k$, или к любым k функциям), из текста не ясно. (А нумерации класса вычислимых с данным оракулом функций рассматриваются только для случая, когда оракул представляет собой множество или всюду определённую функцию.) Но Майхилл и Шепердсон уточняют, что в их результате речь идёт от частично рекурсивных функционалах, определённых (и дающих функции) для всех функций в качестве аргументов, что эквивалентно второму определению, как и должно быть.

Одифредди [108, Definition II.3.6] определяет частично рекурсивные функционалы со ссылкой на Клини [65], но следует третьему варианту определения (композиция операций подстановки, минимизации и рекурсии, применённых к частично рекурсивным функциям и аргументам), который в [65] не встречается. Понятие, соответствующее второму варианту определения, он называет “effectively continuous functional” или “recursive operator”, а первому—“partial recursive operator”.

Возвращаясь к работам Успенского [9, 10, 12], можно отметить следующие достижения:

* впервые было дано определение сводимости по перечислимости;

* впервые было опубликовано (восходящее к Колмогорову) определение нумерации и сводимости нумераций;

* были проанализированы свойства нумераций вычислимых функций и перечислимых множеств, необходимые для рассуждений о номерах программ, введено понятие главной нумерации (впоследствии переоткрытое Роджерсом);

* была доказана (до того, как это сделал сам Райс) гипотеза Райса об описании вполне перечислимых классов перечислимых множеств; получены также аналогичные результаты для вычислимых функций (вместо перечислимых множеств); в частности, доказана невозможность распознавания нетривиальных свойств вычислимых функций по их номерам в главной нумерации;

* было дано определение вычислимой операции в терминах топологического подхада (вычислимость как некоторый специальный случай непрерывности) и доказано (одновременно с Майхиллом и Шепердсоном), что ограничения вычислимых операцией на вычислимые функции можно эквивалентно описать как алгоритмические преобразования программ, а также доказана аналогичная теорема для операций над перечислимыми множествами.

Во избежание недоразумений отметим, что Успенский не рассматривает алгоритмы, определённые на всех программах **всюду определённых** функций и дающие одинаковые значения на эквивалентных программах: эти работы Крайзеля, Лакомба, Шёновилда [96] (позднее обобщённые Цейтиным [98] на конструктивные метрические программа) никак не пересекаются с работами Успенского.
Приведём отрывок из воспоминаний Успенского [63, с. 905–907, 912], где он пишет о своих результатах 1955 года и об их представлении на Третьем всесоюзном математическом съезде (1956):

В сделанном 26 июня обзорном докладе «Об алгоритмической сводимости» я рассказывал о четырёх видах сводимости и связях между ними. Это сводимость по вычислимости, состоящая в сведении вычисления одной функции к вычислению другой. Это сводимость по разрешимости, состоящая в сведении задачи построения разрешающего алгоритма для одного множества к задаче построения разрешающего алгоритма для другого множества. Это сводимость по перечислимости, состоящая в сведении перечисления одного множества к перечислению другого. Это сводимость проблем, состоящая в сведении решения одной проблемы к решению другой. (...) [Говоря о понятии сводимости проблем, Успенский указывает на его источник:] В 1955 году интересную разновидность проблем ввёл ученик Колмогорова Ю. Т. Медведев; он же определил понятие сводимости для таких проблем. (...)

Наименование моего доклада 2 июля было «Понятие программы и вычислимые операторы», а сообщения 3 июля — «Вычислимые операции, вычисляемые операторы и конструктивно-непрерывные функции». Доклад и сообщение были тесно связаны тематически.

В сообщении 3 июля был изложен (разумеется, без доказательства) результат, который я считаю своим главным математическим результатом; я помню обстоятельства его получения<fnref n="11" />—теорема 3 (см. ниже). Он составил основу моей кандидатской диссертации, защищённой в октябре 1955 года. Доказательства этого результата, кроме текста диссертации, хранящейся—или только уже хранившейся—в библиотеке мехмата, я так никогда и не опубликовал. Основная причина, как ни стыдно в этом признаться, банальная лень. Дополнительная причина, не столь постыдная, но глупая, это преследовавшее [в тексте: преследующее] меня, пока я не повзрослел, желание изложить всё в максимально общем виде, но достичь предела в обобщении нереально. (...)

**Теорема 3.** Пусть функция $g$ с натуральными аргументами и значениями обладает следующим свойством. Если $t$ и $n$ служат программами одной и той же вычислимой функции от $s$ аргументов, то $g(m) + g(n)$ также служат программами одной и той же функции от одного аргумента. Тогда существует вычислимый оператор $V$ со следующим свойством. Для всякой функции $\theta$ с программой $n$ значением $V(\theta)$ оператора $V$ на функции $\theta$ является функция с программой $g(n)$.

**Философский комментарий.** Семиотический смысл теоремы 3 таков: «хорошее» вычислимое преобразование имён сопровождается вычислимым преобразованием соответствующих объектов.

<footnote n="11">¹¹Теорема 3 интересовала меня с семиотической точки зрения, (...). хотя слова ‘семиотика’ я тогда, скорее всего, ещё не знал. Помню, как я бродил по улицам и думал только об этом. Озарение пришло, когда в течение некоторого времени я проводил дневные часы в квартире моей тёщи в Большом Спасоглинищевском переулке. Сын ещё не родился, жена и тёща уходили на работу, телефона в квартире не было, мобильные телефоны ещё не были изобретены. Вот в этой обстановке меня внезапно осенило.» [Примечание В. А. Успенского]</footnote>
Конструктивность в классической математике

Идея о том, что можно понимать математические утверждения конструктивно, была известна давно («интуиционизм» Брауэра и его последователей и позже «конструктивизм» Маркова и его учеников). В частности, утверждения вида «для всех x существует такой у, что...» при конструктивном понимании предполагают, что существует некоторый способ получения этого самого «существующего» у по любому данному значению х.

Обычно вместе с этим предлагали изменить и саму логику, понимая конструктивно,
в частности, связку «или» и не пользуясь законом исключённого третьего. Другое (на
первый взгляд, напрашивающееся) предложение, а именно, рассматривать «эффектив-
ные» аналоги классических определений и результатов внутри обычной («неконструк-
тивной») математики, удивительным образом сначала было менее популярно, и часто
считалось, что если уж мы рассуждаем об алгоритмах, то это почему-то обязывает нас
рассуждать «конструктивно», «финитно» и т.п. В отличие от этой традиции, Успенский
систематически пропагандировал «классический» подход к алгоритмическим поняти-
ям. Вот два примера из его работ.

Есть разные конструкции действительных чисел (сечения Дедекинда, фундаментальные последовательности, вложенные отрезки, бесконечные десятичные дроби). Для каждой из них можно рассмотреть её эффективный вариант. Скажем, для сечений Дедекинда можно требовать существования алгоритма, который по рациональному числу говорит, в каком из двух множеств сечения оно лежит. Для фундаментальной последовательности рациональных чисел естественно требовать существования алгоритма, вычисляющего её члены, а также «регулятора сходимости» — алгоритма, находящего по (рациональному) ε > 0 то место, начиная с которого члены последовательности отличаются менее чем на ε. Для бесконечной десятичной дроби естественно требовать существования алгоритма, который по n указывает n-ю цифру дроби, и так далее.

В каждом из этих случаев возникает некоторое подмножество множества действи-
тельных чисел (соответствующее тем числам, для которых имеются такие эффектив-
ные представления). Можно поставить, оставаясь в рамках «классической математи-
ки», вопрос о том, дают ли перечисленные варианты определений одно и то же подмно-
жество или разные. Нетрудно убедиться, что одно и то же, и его элементы называют
вычислимыми действительными числами.

Здесь хорошо видна разница с конструктивистским подходом (скажем, в смысле
школы А. А. Маркова). Для конструктивистов никаких «обычных действительных чи-
сел» не существует, и множество конструктивных действительных чисел не является
подмножеством никакого большего множества. Вместо этого конструктивным действи-
тельным числом называется пара алгоритмов (один вычисляет члены последовательно-
сти, другой является регулятором сходимости), и рассуждать о таких парах предлага-
ется в рамках конструктивной логики. При этом не все варианты определения действи-
тельных чисел равнозначны с точки зрения их конструктивизации. Скажем, подход с
десятичными дробями неудачный — потому, например, что для так определённых кон-
структивных действительных чисел нельзя конструктивно определить сложение (как
преобразование, которое по алгоритмам для двух дробей давало бы алгоритм для их
суммы).

Но этот же дефект, замечает Успенский, можно проанализировать и в рамках клас-
сической математики. Будем интересоваться не только тем, один и тот же класс дей-
ствительных чисел возникает в рамках разных определений или разные, но также и
более тонким вопросом: эквивалентны ли нумерации множества вычислимых действительных чисел, которые получаются из этих определений (можно ли по номеру вычислимого действительного числа в одной нумерации алгоритмически получить номер того же числа в другой). И тут возникает та же самая проблема с десятичными дробями (и с дробями в любых системах счисления). Подробно этот вопрос разобран в [18], где даны необходимые и достаточные условия, при которых переход от одного основания к другому (в позиционной записи) эффективен.

Другой пример, разобранный Успенским в [19]—эффективизация определения бесконечного множества. Можно определить бесконечность множества X так: для всякого n в множестве X есть не менее n элементов. Или так: для всякого конечного множества F есть число, которое отличает F от X, то есть принадлежит симметрической разности $F \Delta X$. Оба эти определения можно эффективизировать, потребовав существования соответствующих алгоритмов. В первом случае речь идёт об алгоритме, который по n указывает список из n элементов множества X; во втором случае речь идёт об алгоритме, который применим к любому конечному множеству F и даёт какой-то элемент разности $F \Delta X$. Можно проверить, что эти свойства (существование того и другого алгоритма) эквивалентны (и даже можно без нарушения эквивалентности требовать, чтобы по F давался элемент разности $X \setminus F$). В терминологии Поста [86] оба эти свойства равносильны тому, что множество X не является иммунным (содержит бесконечное перечислимое подмножество).

Не все естественные определения бесконечности приводят к эквивалентным эффективизациям. Скажем, можно сказать, что множество X бесконечно, если для всякого n можно указать начальный отрезок [0, N] натурального ряда, содержащий по крайней мере n элементов множества X. Эффективный вариант этого определения требует, чтобы существовал алгоритм, указывающий N по n. Это более слабое определение эффективной бесконечности, которое, как доказал Успенский в [15], равносильно тому, что множество не является гипериммунным в смысле Поста [86]. (Параллельно и независимо, отвечая на вопрос Колмогорова, это же доказали А. В. Кузнецов и Ю. Т. Медведев.)

Интересно отметить, хотя это и не имеет отношения к работам Успенского, что важнейшее достижение алгоритмической теории случайности, а именно, определение случайности по Мартин-Лёфу, данное им в 1966 году [101], тоже можно рассматривать как естественную эффективизацию классического (во всех смыслах этого слова) определения нулевого множества (множества нулевой меры в смысле Лебега). В этом классическом определении (скажем, для подмножеств отрезка) говорится, что множество $X \subset [0, 1]$ является нулевым, если для всякого $\varepsilon > 0$ существует покрытие множества X интервалами с суммой длин не больше $\varepsilon$. По очевидным причинам можно ограничиться рациональными значениями $\varepsilon$ и интервалами с рациональными концами. Тогда они будут конструктивными объектами и можно эффективизировать определение, потребовав, чтобы существовал алгоритм, который, получив на вход $\varepsilon$, перечисляет интервалы покрытия с требуемыми свойствами. Это и предложил Мартин-Лёф.

Можно добавить, что многие вопросы и результаты алгоритмической теории случайности можно интерпретировать как вопросы об эффективизации классических понятий и теорем. Скажем, критерий Соловея случайности по Мартин-Лёфу, как заметил Александр Буфетов, является эффективным вариантом классической леммы Бореля—Кантелли. При этом интересно, что стандартное её доказательство (хвосты сходящегося ряда могут быть сколь угодно малы) не эффективизируется, и приходится использовать другое (тоже естественное и несложное, см. подробности в [59]). Другой поучительный пример того же рода—обнаруженное В. В. Вьюгиным (учеником Успенского) доказательство эффективного варианта эргодической теоремы [110].