Strong and weak reducibility of algorithmic problems 1

Abstract

Keywords

M-problems Ex-problems weak reducibility weak degrees

Introduction

The abstract (arithmetical) analysis of algorithmic problems was initiated by S. Kleene and E. Post [2,8]. E. Post introduced the concept of degree of unsolvability of a problem, while Kleene and Post investigated in [2] the class of degrees of unsolvability of arithmetical (in the sense of Gödel) sets. Papers along the same line were published subsequently.

The traditional algorithmic problems of algebra, number theory, topology, and mathematical logic were problems of solvability. This explains the predominant interest shown first in problems of solvability of arithmetic (i.e., problems of solvability of sets of natural numbers). Subsequently, however, in logic and its applications, problems arose connected to separability, enumerability, and isomorphism of sets [5,6,10,12].

The definition of an algorithmic problem in abstract algorithm theory was formulated by Y.T. Medvedev, in which all the previously known cases and many others were treated [5]. The problem of constructing an arithmetical function2

I.e., a function defined on the natural numbers $N$ and assuming values from $N$ , which includes also 0.

satisfying certain conditions is called a Medvedev problem (M-problem). To each M-problem P there corresponds a family of functions satisfying the conditions of the problem. Conversely, any family of functions A defines some M-problem

P (A)

. The functions contained in the family corresponding to an M-problem P are called the solution functions of the M-problem P.

To each M-problem there corresponds a certain degree of difficulty (an exact definition of degrees of difficulty is given below). It is possible to define in a natural fashion conjunction, disjunction, and other operations of propositional calculus on the degrees of difficulty. As was established by Y.T. Medvedev, the calculus of M-problems is an interpretation of constructive propositional calculus. This is to be expected, since the calculus of M-problems is an elaboration of A.N. Kolmogorov’s calculus of problems (see [3]). The definition of reducibility of a family of functions (M-problems), which is basic in the calculus of M-problems, has a constructive character.

Definition 1.

An M-problem $P (A)$ (family A) is reducible to an M-problem $P (B)$ (family B), if there exists a general method of transformation of any solution of the M-problem $P (B)$ into a solution of the M-problem $P (A)$ , or more accurately, if there exists a partial recursive operator T, which transforms each function f from the family B into some function g (which depends on f) from the family A, $g = T [f]$ . The reducibility of the family A (M-problem $P (A)$ to $P (B)$ ) to B is denoted by $A ⩽ B$ ( $P (A) ⩽ P (B)$ ). The family of functions A (the M-problem $P (A)$ )3

The definitions presented here apply equally well to families of functions and to the M-problems which they define.

is called solvable, if it contains at least one general recursive function. The M-problems (families) A and B are called equivalent (

A \approx B

) if they are reducible to each other.

The class of M-problems equivalent to an M-problem A is called the degree of difficulty of the M-problem A and is denoted by $a = | A |$ . The degrees of difficulty form a partially ordered set Ω: $| A | = a ⩽ b = | B |$ if the M-problem A is reducible to B. Ω is a distributive lattice with implication and has a largest and a smallest element (see [5]). The investigation of M-problems, initiated by Y.T. Medvedev, was continued by the author in [6].

Section 1

1. We describe here a second approach to the concept of reducibility of algorithmic problems, corresponding to classical, i.e., non-constructive, formulations.

Along with the problem of constructing an algorithm which solves a certain problem, it is possible to consider the problem of the existence of a required algorithm, without insisting on its concrete form. Then each condition imposed on the arithmetical functions (i.e., each family of functions) will be linked to two problems:

The problem of constructing one of the functions of this family: the M-problem.

The problem of proving the existence of a general recursive function in this family.4

⁴

It is easy to see here an analogy with the question of the existence of a solution of a differential equation and the problem of effectively finding a solution.

Problems of the second type will be called Ex-problems. There is a pairwise one-to-one correspondence between the classes of families of functions, M-problems, and Ex-problems. The Ex-problem corresponding to the family of functions A (M-problem $P (A)$ ) will be denoted by $\overline{P} (A) = Q (A)$ . The functions of the family defining the Ex-problem Q will accordingly be called the solution functions of the Ex-problem $\overline{Q}$ . An Ex-problem is called solvable if its solution functions include a general recursive one.

An important method of establishing the solvability of an algorithmic problem A is to reduce this problem to a different problem B, the solvability of which has already been established. Conversely, the unsolvability of a problem A implies the unsolvability of any problem B to which problem A is reducible.

Definition 2.

The Ex-problem $\overline{P} (A)$ (family of functions A) is weakly reducible to the Ex-problem $\overline{P} (B)$ (family B) ( $A ⊲ B$ ), if for any function f of the family B ( $f \in B$ ) there exists a partial recursive operator T, which transforms the function f into the function g of the family A ( $g \in A$ ).

The choice of the function f governs here not only g but also the operator $T = T_{f}$ . In this case we say that the problem $\overline{P} (A)$ (family A) reduces weakly to the problem $\overline{P} (B)$ (family B) by means of the operators ${T_{f}}$ .

The reducibility of families of functions (problems) in the sense of Medvedev’s definition will be called henceforth strong reducibility (or simply reducibility).

Inasmuch as each of the three objects: the family of functions, the M-problem, and the Ex-problem, defines uniquely the two others, we shall henceforth identify these objects and call them problems.

2. A natural question arises concerning the relation between these types of reducibility. It is clear that strong reducibility of a problem A to a problem B implies weak reducibility of A to B. As shown by the example considered below, the converse is generally not true.

Let the problem A be determined by a family consisting of one non-recursive function f, $A = K_{f} = {f}$ , and let problem B be determined by a family consisting of all the functions obtained from f in the following manner: for each tuple of natural numbers $\overline{n} = {n_{1}, \dots, n_{s}}$ we consider the function $f_{\overline{n}} (i)$ : $\begin{matrix} f_{\overline{n}} (i) = \{\begin{matrix} n_{i + 1} & for 0 ⩽ i < s, \\ f (i - s) & for i ⩾ s, \end{matrix} \end{matrix}$ i.e., we “place in front” of the sequence of values ${f (i)}$ the tuple $\overline{n}$ : $\begin{matrix} B = K_{f}^{'} = {f_{\overline{n}}} . \end{matrix}$ It is easy to see that the problem $K_{f}$ reduces weakly to the problem $K_{f}^{'}$ : $\begin{matrix} K_{f} ⊲ K_{f}^{'} . \end{matrix}$ For any function $f_{\overline{n}} \in B$ there exists a partial recursive operator (p.r.o.) T which transforms $f_{\overline{n}}$ into f (by “discarding” the first s values of $f_{\overline{n}}$ , where $\overline{n} = {n_{1}, n_{2}, \dots, n_{s}}$ ).

However, the problem A does not strongly reduce to the problem B.

Let us assume the opposite, i.e., that there exists a p.r.o. T which transforms any function $f_{\overline{n}}$ into f. Any p.r.o. T can be specified by means of a recursive sequence of pairs of tuples (see [4,6]) $\begin{matrix} {(d_{w}, d_{w}^{'})}, w = 0, 1, 2, \dots . \end{matrix}$ If the sequence of several first values of the function h forms a tuple d, then we call d a tuple of the function h. We shall also say that the function h begins with the tuple d. If $h = T [e]$ and $d_{w}$ is a tuple of the function e, then $d_{w}^{'}$ is a tuple of the function h. Inasmuch as $T [f_{d_{w}}] = f$ and $d_{w}$ is a tuple of the function $f_{d_{w}}$ , then $d_{w}^{'}$ is a tuple of the function f (for each w). In view of the fact that ${d_{w}^{'}}$ is a recursive sequence of tuples, the length of which is unlimited (in the aggregate), the function f is recursive, yet we have assumed it to be non-recursive. This contradiction proves that the problem A does not reduce strongly to B.

In the foregoing example, the problem B was chosen somewhat artificially. For algorithmic problems which are usually considered in the theory of algorithms and its applications, the situation is different. If we confine ourselves to reducibility (strong and weak) by means of general recursive operators5

⁵

A general recursive operator is a p.r.o. which transforms functions which are everywhere defined (on $N$ ) into functions which are everywhere defined.

or even partial recursive operators applicable to each solution function of the problem to which we reduce another problem, then both types of reducibility are equivalent for a broad class of problems. We shall return to this question in Section 2, and consider here in greater detail the calculus that results from the definition of weak reducibility of problems.

3. If problems A and B reduce weakly to each other, we shall call them weakly equivalent: $A ⊢ ⊣ B$ . This relation is transitive, symmetrical, and reflexive. The class of all problems therefore breaks up into classes of weakly equivalent problems. The class of problems which are weakly equivalent to A will be called the weak degree of difficulty of problem A. The weak degree of difficulty of the problem A characterizes the problem of proving the existence (in the classical sense) of a computable solution function of the problem A.

A weak degree of difficulty $\overline{b}$ exceeds $\overline{a}$ , $\overline{b} ⩾ \overline{a}$ or $\overline{a} ⩽ \overline{b}$ , if the problem A reduces weakly to the problem B ( $\overline{a} = | \overline{A} |$ , $\overline{b} = | \overline{B} |$ ). We denote by $\overline{Ω}$ the partially ordered set of weak degrees of difficulty.

Between Ω and $\overline{Ω}$ there is a one-sidedly univalent correspondence $Ω \to \overline{Ω}$ ; to each degree of difficulty $a \in Ω$ there corresponds a weak degree of difficulty $\overline{a}$ : $\overline{a}$ is the weak degree of difficulty of a problem A with degree of difficulty a. The correspondence $a \to \overline{a}$ does not depend on the choice of the problem A, since equivalence of problems implies weak equivalence of problems. This relation is isotopic, since reducibility of problems implies weak reducibility. The solvable (smallest) degree 0 from Ω corresponds to the solvable weak degree $\overline{0}$ from $\overline{Ω}$ , and the improper (largest, i.e., defined by the empty class of functions) degree ∞ from Ω corresponds to an equal degree from $\overline{Ω}$ . We shall prove that $\overline{Ω}$ is a lattice and the indicated correspondence is a lattice homomorphism.

We note that $\overline{Ω}$ admits a natural topological interpretation. Define a complete family of functions or points of Baire space (complete problem) to be any family (problem) A having the following property: together with each function f belonging to A, the family A contains any function g with respect to which the function f is recursive.

We shall establish some properties of complete families. The union and intersection of any number of complete families (finite or infinite) are also complete families.

Let B be some family of functions. The family consisting of all functions ${g}$ , for each of which there exists a certain function f from B, which is recursive with respect to this function g will be called the completion $B^{'}$ of the family B. It is obvious that $B^{'}$ is the smallest complete family containing the family B, and the completion of a complete family A coincides with A: $A^{'} = A$ . The family $B^{'}$ is weakly equivalent to B. It is sufficient to establish that $B^{'} ⊴ B$ , since $B^{'} \supset B$ , from which follows $B ⊴ B^{'}$ . Indeed, for any function $g \in B^{'}$ there exists a p.r.o. T such that $T [g] = f \in B$ .

Completions of two weakly equivalent families A and B coincide: $A ⊢ ⊣ B \to A^{'} = B^{'}$ . Let $g \in A^{'}$ . Then there exists a function $f \in A$ and a p.r.o. $T_{1}$ such that $T_{1} [g] = f$ . In view of $A ⊢ ⊣ B$ , there exists a p.r.o. T such that $T [f] = h \in B$ . Then $T_{2} [g] = T [T_{1} [g]] = h \in B$ . Therefore $g \in B^{'}$ . Conversely, if $g \in B^{'}$ , then $g \in A^{'}$ . Thus $A^{'} = B^{'}$ .

In view of the foregoing, any weak degree $\overline{a}$ defines uniquely a complete family (problem) A, which we shall call the representative of $\overline{a}$ .

Lemma.

Let $\overline{a}$ and $\overline{b}$ be weak degrees of complete families A and B respectively. Then $\overline{a} ⩾ \overline{b} \leftrightarrow A \subset B$ , 6

⁶

$A \leftrightarrow B$ denotes that the statement $A$ is equivalent to statement $B$ .

or using a different notation

\begin{matrix} (1) & \overline{A} ⊵ \overline{B} \leftrightarrow A \subset B . \end{matrix}

Let $g \in A$ . Then there exists a p.r.o. T such that $T [g] = f \in B$ . In view of the completeness of the family B, $g \in B$ . The relation $A \subset B \to A ⊵ B$ is obvious.

We now readily prove some theorems concerning the properties of $\overline{Ω}$ .

Theorem 1.

For any set of weak degrees ${{\overline{a}}_{ξ}}$ there exist exact upper and lower bounds, denoted by $⋁ {\overline{a}}_{ξ}$ and $⋀ {\overline{a}}_{ξ}$ , respectively.

Let $A_{ξ}$ be a complete family with weak degree of difficulty ${\overline{a}}_{ξ}$ and $A = ⋃_{ξ} {\overline{A}}_{ξ}$ , $\overline{a} = | \overline{A} |$ . We shall prove that $\overline{a} = inf {{\overline{a}}_{ξ}}$ . Obviously A is a complete family and $\overline{a} ⩽ {\overline{a}}_{ξ}$ for any ξ. Further, let $\overline{b} ⩽ {\overline{a}}_{ξ}$ for any ξ and B a complete family, $\overline{b} = | \overline{B} |$ . Then $B \supset A_{ξ}$ and $B \supset A$ , hence $\overline{b} ⩽ \overline{a}$ . We put $A^{*} = ⋂_{ξ} A_{ξ}$ . Obviously, ${\overline{a}}^{*} ⩾ {\overline{a}}_{ξ}$ for any ξ. In addition, if $\overline{b} ⩾ {\overline{a}}_{ξ}$ for all ξ, and B is a representative of $\overline{b}$ , then $B \subset A_{ξ}$ and $B \subset ⋂_{ξ} A_{ξ} = A^{*}$ , i.e., $\overline{b} ⩾ {\overline{a}}^{*}$ . Hence ${\overline{a}}^{*} = sup {{\overline{a}}_{ξ}}$ .

From the proof of Theorem 1, we see that the operations of taking the exact upper and lower bounds in $\overline{Ω}$ correspond to the operations of intersection and union of complete families of functions.

$\overline{Ω}$ is a complete lattice, represented by subsets of the Baire space J. In the function space J it is possible to introduce a topology by assigning as open sets the complete families of functions. This will be a $T_{0}$ space. (On this subject see G.D. Birkhoff, Lattice theory, Russian translation of the 2nd edition, IL 1952, Chapter IV, §§ 1 and 2.)

Theorem 2.

Let A and B be arbitrary problems, $a = | A |$ , $\overline{a} = | \overline{A} |$ , $b = | B |$ , $\overline{b} = | \overline{B} |$ . Then the problem $C = A \cup B$ with degree of difficulty $c = a \lor b$ has a weak degree $\overline{c} = \overline{a} \lor \overline{b}$ , and the problem D with degree of difficulty $d = a \land b$ has a weak degree $\overline{d} = \overline{a} \land \overline{b}$ .

Following Y.T. Medvedev [5], we choose problems C and D in the following fashion. We define the p.r.o.s $R_{0}$ , $R_{1}$ and a two-place p.r.o. R: $\begin{array}{rcl} f_{i} (n) = R_{i} [f], \\ f_{i} (n) = \{\begin{matrix} i & for n = 0, \\ f (n - 1) & for n > 0 \end{matrix}\} (i = 0, 1), \\ h (n) = R [f (m), g (m)], \\ h (n) = \{\begin{matrix} f (m) & for n = 2 m, \\ g (m) & for n = 2 m + 1 . \end{matrix} \end{array}$ The problem C consists of all the functions $f_{0} (n) = R_{0} [f]$ , where $f \in A$ , and all the functions $g_{1} (n) = R_{1} [g]$ , where $g \in B$ , and $| C | = c = a \lor b$ . The problem $C_{1}$ consists of all the solution functions of problems A and B, $\begin{matrix} | {\overline{c}}_{1} | = \overline{c} = \overline{a} \lor \overline{b} . \end{matrix}$ We shall prove that C and $C_{1}$ are weakly equivalent, i.e., $| {\overline{C}}_{1} | = | \overline{C} |$ . Indeed, each function $h \in C_{1}$ can be transformed with the aid of $R_{0}$ or $R_{1}$ into a function $h_{i} \in C$ , and each function $h_{i} \in C$ can be reduced by means of an inverse transformation into $h \in C_{1}$ (i.e., $C_{1}$ reduces even strongly to C).

Further, the problem D consists of all the functions $h = R [f, g]$ , where f runs through class A and g through class B. The problem $D_{1}$ consists of all the functions e such that problems A and B reduce to the problem of computability $A_{e} = {e}$ , i.e., for each function e there exists p.r.o. $T_{1}$ and $T_{2}$ such that $T_{1} [e] \in A$ , $T_{2} [e] \in B$ . We shall prove that problems D and $D_{1}$ are weakly equivalent:

$D_{1} ⊴ D$ (even $D_{1} ⩽ D$ ). The relation $D_{1} ⩽ D$ follows from the fact that class D is contained in $D_{1}$ , since any function $h \in D$ can be transformed with the aid of the p.r.o. $T_{1}$ ( $T_{2}$ ) into the function $f (g)$ , $f \in A$ ( $g \in B$ ). To this end it is sufficient to put $\begin{array}{rcl} T_{1} [h] = f (m) = h (2 m), \\ T_{2} [h] = g (m) = h (2 m + 1) . \end{array}$

$D ⊴ D_{1}$ . Let the function $e \in D_{1}$ . Then there exist p.r.o. $T_{1}$ and $T_{2}$ such that $\begin{matrix} f = T_{1} [e] \in A, g = T_{2} [e] \in B, R [f, g] = h \in D \end{matrix}$ and $\begin{matrix} h = T [e] = R [T_{1} [e], T_{2} [e]] \in D . \end{matrix}$ The p.r.o. T transforms the function e into $h \in D$ , from which it follows that $D ⊴ D_{1}$ .

The weak degree $\overline{c} = \overline{a} \lor \overline{b}$ will be called the disjunction, and $\overline{d} = \overline{a} \land \overline{b}$ will be called the conjunction, of the weak degrees $\overline{a}$ and $\overline{b}$ . Let us prove that the lattice $\overline{Ω}$ has an implication operator:

Theorem 3.

For any weak degrees $\overline{a}$ and $\overline{b}$ there exists a smallest degree ${\overline{c}}^{*}$ in the class of weak degrees $\overline{c}$ such that $\overline{a} \land \overline{c} ⩾ \overline{b}$ .

Proof.

We consider the representatives of the weak degrees $\overline{a}$ and $\overline{b}$ , i.e., the complete families (problems) A and B, $| \overline{A} | = \overline{a}$ , $| \overline{B} | = \overline{b}$ . We denote by $C^{*}$ the family of all the functions ${g}$ such that for each pair of functions $[f, g]$ , where $f \in A$ and $g \in C^{*}$ , there exist a p.r.o. T which transforms the pair $[f, g]$ into a function $e \in B$ , $e = T [f, g]$ . It is obvious that the family $C^{*}$ includes the family B and that $\overline{a} \land {\overline{c}}^{*} ⩾ \overline{b}$ where ${\overline{c}}^{*} = | {\overline{C}}^{*} |$ . Let us prove that the problem $C^{*}$ reduces weakly to any problem C such that $\overline{a} \land \overline{c} ⩾ \overline{b}$ where $\overline{c} = | \overline{C} |$ . Let C be such a problem and g an arbitrary function from C. As follows from Theorem 2, the problem D, which consists of all of the functions $h = R [f, g]$ where f runs through the family A and g through the family C, has the weak degree $\overline{d} = \overline{a} \land \overline{c}$ . Inasmuch as $\overline{d} ⩾ \overline{b}$ , i.e., $| D | ⊴ | B |$ , for any function $h \in D$ , there exists a p.r.o. $T_{1}$ such that $e = T_{1} [h] \in B$ . This means that for any pair of functions $[f, g]$ where $f \in A$ and $g \in C$ , there exists a two-place p.r.o. $T = T_{1} R$ such that $e = T [f, g] = T_{1} [R [f, g]] \in B$ . By definition of $C^{*}$ , the function $g \in C^{*}$ . It follows therefore that $C \subset C^{*}$ and $| C^{*} | ⊴ | C |$ . This completes the proof. □

We shall call $C^{*}$ the weak problem of reducibility of the problem B to the problem A, and ${\overline{c}}^{*}$ the implication, denoted by $\overline{a} \supset \overline{b}$ . Obviously $C^{*}$ is a complete family, i.e., the representative of ${\overline{c}}^{*}$ .

We note that implication, generally speaking, is not conserved in homomorphism of the lattices $Ω \to \overline{Ω}$ . Indeed, in the example discussed in Section 2, the problems A and B ( $A = K_{f}$ , $B = K_{f}^{'}$ ) were related by $| A | > | B |$ and $| \overline{A} | ⊢ ⊣ | \overline{B} |$ , or $a > b$ and $\overline{a} = \overline{b}$ . Therefore the implication $\overline{b} \supset \overline{a}$ is the solvable (trivial) weak degree (i.e., the degree of a solvable problem), and $b \supset a$ is an unsolvable degree and $\overline{b \supset a} \neq \overline{b} \supset \overline{a}$ .

Note that solvability of the weak degree $\overline{a} \supset \overline{b}$ is equivalent to the relation $\overline{a} ⩾ \overline{b}$ . The proof of this is simple and will be omitted. Further consideration of this point is analogous to that of Y.T. Medvedev with respect to the calculus of Ω.

We consider an arbitrary segment $\overline{Ω} : 0 ⩽ x ⩽ \overline{d}$ . The weak degree $\neg x = x \supset d$ is called the negation of the weak degree x (with respect to $\overline{d}$ ). We introduce also the notation $\overline{a} \sim \overline{b}$ for the degree $(\overline{a} \supset \overline{b}) \cap (\overline{b} \supset \overline{a})$ .

The thought arises of the connection between the calculus of weak degrees $\overline{Ω}$ and the propositional calculus: elementary propositions can be interpreted as weak degrees, and the operations of propositional calculus correspond to like operations of the calculus of weak degrees. The truth of a formula corresponds to the solvability of a weak degree.

Theorem 4.

All the axioms and rules of derivation of intuitionistic propositional calculus are satisfied for weak degrees of an arbitrary segment $0 ⩽ x ⩽ \overline{d}$ in $\overline{Ω}$ .

Theorem 4 follows from the existence of implication in the distributive lattice Ω (see Birkhoff, Lattice theory, Russian translation of the 2nd edition, Chapter XII, §7).

Let us discuss the consequences of this point. In spite of the fact that the definition of weak reducibility of problems has been chosen in accordance with classical premises, the calculus of weak degrees obtained thereby is an interpretation of constructive propositional calculus and does not include, for example, the law of the excluded third.

However, this should not surprise us, since the calculus of weak degrees $\overline{Ω}$ , like that of Ω, is a refinement of Kolmogorov’s calculus of problems.

The question whether the weak degrees $\overline{Ω}$ are an exact7

⁷

An interpretation of a logical calculus K is called exact if all formulas true (solvable, realizable) in the interpretation are derivable in the calculus K.

interpretation of constructive propositional calculus remains open. We note that the calculus of degrees of difficulty Ω, as shown recently by Y.T. Medvedev, is an exact interpretation of the constructive calculus.

Section 2

In this section we analyze the question of the relation between strong and weak reducibility under certain limitations on the p.r.o.s by means of which the reducibility is realized, and on the problems themselves.

We need several new concepts. In the arguments that follow we shall find it convenient to use the Baire space J.

Arithmetical functions can be interpreted as points in Baire space (considering the sequence of the values of these functions [1,4]). To each problem A in such an interpretation, there corresponds a certain set of points $M_{A}$ of the Baire space, which defines it completely.

Let $δ_{\overline{n}}$ be a Baire interval, defined by a tuple $\overline{n} = (n_{1}, n_{2}, \dots, n_{s})$ . The problem which is defined by the set of points $M_{A} \cap δ_{\overline{n}}$ shall be called the interval $A_{\overline{n}}$ of the problem A. In other words, $A_{\overline{n}}$ is defined by the class of solution functions of the problem A beginning with the tuple $\overline{n}$ . The interval $A_{\overline{n}}$ is called non-empty if the set $M_{A} \cap δ_{\overline{n}}$ is non-empty. A problem A is called uniform if any of its non-empty intervals is (strongly) reducible to it.

The problem of solvability $A_{E}$ of the set E is defined by the class $K_{A} (E)$ , consisting of one characteristic function of the set E. The problem of enumerability $C (E)$ is determined by the class $K_{C} (E) = {f (n)}$ of the functions that enumerate the set E, i.e., the set E is the image of the function $f (n)$ . The problem of separability $A_{E_{0} E_{1}}$ of the sets $E_{0}$ and $E_{1}$ with empty intersection is determined by the class of functions ${f (n)}$ satisfying the condition $\begin{matrix} (2) & f (k) = \{\begin{matrix} 0 & for k \in E_{0}, \\ 1 & for k \in E_{1}, \\ 0 or 1 & for k \notin E_{0} \cup E_{1} . \end{matrix} \end{matrix}$

Theorem 5.

The problem of enumerability of any non-empty set E is uniform.

Indeed, let C be the problem of enumerability of the set E and let $C_{\overline{n}}$ be a non-empty interval in it: $\overline{n} = (n_{1}, n_{2}, \dots, n_{s})$ . Thus $K_{C_{\overline{n}}}$ consists of all the functions which enumerate the set E and begin with the tuple $\overline{n}$ . The problem $C_{\overline{n}}$ is (strongly) reducible to the problem C by means of the p.r.o. T which, being applied to any function f, shifts the sequence of its values by first adding the tuple $\overline{n}$ .

Theorem 6.

The problem of separability $A_{E_{0} E_{1}}$ is uniform for arbitrary $E_{0}$ , $E_{1}$ ( $E_{0} \cap E_{1} = Λ$ , where Λ is the empty set).

We denote the problem $A_{E_{0} E_{1}}$ by A. Let $A_{\overline{n}}$ be a non-empty interval of the problem A, $\overline{n} = (n_{1}, n_{2}, \dots, n_{s})$ . It is obvious that $\begin{matrix} (3) & n_{k} = \{\begin{matrix} 0 & for k \in E_{0}, \\ 1 & for k \in E_{1}, \\ 0 or 1 & for k \notin E_{0} \cup E_{1} \end{matrix}\} (k = 1, 2, \dots, s) . \end{matrix}$

The problem $A_{\overline{n}}$ is (strongly) reducible to the problem A by means of the p.r.o. T which replaces the first s values of any function by the tuple $\overline{n}$ . If $f (k)$ is a solution function of the problem A, then it satisfies the condition (2). But then the function $g = T [f]$ also satisfies the condition (2), as follows from (3) and from the definition of the p.r.o. T. In addition, the function g begins with the tuple $\overline{n}$ and hence is a solution function of the M-problem $A_{\overline{n}}$ , which was to be proved.

The problem of continuation of the partial8

⁸

I.e., perhaps not everywhere defined.

function

f (m)

is the problem

B_{f}

defined by the class of functions (which are defined everywhere on

N

) coinciding with the function

f (m)

wherever the latter is defined. (We shall call such functions continuations of

f (m)

.) We note that a problem of separability is a particular case of a problem of continuation. Obviously we have:

Theorem 7.

The problem of continuation of any partial function is uniform.

The proof of Theorem 7 is analogous to the proof of Theorem 6.

Inasmuch as the p.r.o.s used in the proofs of Theorems 1 and 2 are general recursive, each problem of enumerability or separability reduces to any of its non-empty intervals by means of a general recursive operator. Problems possessing this property will be called general recursively uniform. In addition to problems of enumerability and separability, problems of solvability are also general recursively uniform, since the operator of identical transformation reduces any function to itself.

An example of a non-uniform problem is the problem defined by the class $K = {f, g}$ , where the degree of non-computability of the function f is strictly greater than the degree of non-computability of the function g.

We shall call the problem B closed if it corresponds to a closed set of points $M_{B}$ of the Baire space J. Obviously, solvability problems are closed.

Theorem 8.

The continuation problem of any partial function is closed.

Let ${g_{k} (m)}$ be a convergent sequence of continuations of the function $f (m)$ , and let $g (m) = {lim}_{k \to \infty} g_{k} (m)$ . We shall prove that $g (m)$ also continues $f (m)$ . If the function $f (m)$ is defined for $m = m_{0}$ , then $g_{k} (m_{0}) = f (m_{0})$ for all k. Consequently $g (m_{0}) = f (m_{0})$ , as was to be proved.

Corollary.

Any problem of separability is closed.

Theorem 9.

The problem of enumerability $C (E)$ of any set E containing more than one element is not closed.

Let $a \in E$ and let the function $f (m)$ enumerate the set E. We define the sequence of functions ${f_{k} (m)}$ enumerating the set E: $\begin{matrix} f_{k} (m) = \{\begin{matrix} a & for m < k, \\ f (m - k) & for m ⩾ k . \end{matrix} \end{matrix}$ Obviously $\begin{matrix} lim_{k \to \infty} f_{k} (m) = g (m) \equiv a . \end{matrix}$ In view of the fact that the set $E ∖ {a}$ is not empty, $g (m)$ is not a solution function of the problem $C (E)$ , and consequently the problem $C (E)$ is not closed.

However, it is possible to generalize the concept of closedness of a problem in such a way that enumerability problems as well as many other problems which are of interest for the recursive theory of sets are included. This concept is closely related with the theory of infinite games [9].

Let S be a set of points of the Baire space J. We imagine two players I and II who move alternately, and their moves consist of choosing Baire intervals which intersect with the set S. Player I chooses as his first move the Baire interval $δ_{1}$ , which intersects with S. If player I chose in move m the Baire interval $δ_{m}$ , then player II chooses in the mth move a sub-interval9

⁹

We consider Baire sub-intervals which are proper parts of their intervals.

δ_{m}^{*}

of the interval

δ_{m}

intersecting with S. Then player I chooses in the

(m + 1)

st move a sub-interval

δ_{m + 1}

of the interval

δ_{m}^{*}

intersecting with S. Let us assume that after the mth move of player I (II) the play is in the interval

δ_{m}

(

δ_{m}^{*}

). We agree that at the beginning the game is in the interval

δ_{0} = J

. Player II wins if the sequence of intervals

\begin{matrix} δ_{0} \supset δ_{1} \supset δ_{1}^{*} \supset δ_{2} \supset δ_{2}^{*} \supset \dots \supset δ_{m} \supset δ_{m}^{*} \supset δ_{m + 1} \dots \end{matrix}

contracts to a point of the set S. Otherwise, player I wins.

We fix once and for all some effective numbering of the Baire intervals by means of natural numbers. By a strategy of a player we mean a function $r = φ (n)$ which indicates for each interval with number n the number r of a sub-interval of it. If the game is in the interval numbered n, then the player making the next move chooses the interval with number $φ (n)$ . The strategy φ is called correct with respect to the set S if for any interval numbered n intersecting with S, the interval numbered $φ (n)$ also intersects with S. We shall henceforth take strategy to mean a strategy which is correct with respect to the considered set. A strategy is called winning (for the set S) if player II, using this strategy, wins for any correct strategy of his opponent. A set S is called winning if there exists a winning strategy for this set. The M-problem $A (S)$ and the class of functions $K (S)$ defined by the set S will also be called winning in this case.

A set S (a problem $A (S)$ ) the complement of which is nowhere dense is called trivially winning. In order to win, it is sufficient for player II to choose as his first move an interval which is completely contained in S, which is possible since the complement $C S$ is nowhere dense.

If neither the set S nor its complement $C S$ is trivially winning (or equivalently, neither S nor $C S$ is nowhere dense), then they cannot be simultaneously winning. In fact, let S be a winning set and $φ (n)$ its winning strategy. Let us consider the game with respect to $C S$ . Player I chooses as his first move an interval in which the set S is everywhere dense (such an interval exists, since S is not a set which is nowhere dense). Then player I applies strategy $φ (n)$ . For any strategy of player II, the sequence of intervals in which the game is situated will contract to a point belonging to S, i.e., player II loses.

An example of a winning set (problem) is a closed set S (problem $A (S)$ ). In this case the sequence of intervals ${δ_{m}, δ_{m}^{*}}$ contracts always to a point of S. It follows therefore that problems of solvability and separability are winning. There exist also non-closed winning problems.

Theorem 10.

Any problem of enumerability is a winning problem.

Let $G_{F}$ be the problem of enumerability of a set F of natural numbers, and let $M$ be the corresponding subset of J. Player II chooses a strategy $r = φ (n)$ in the following manner: let n be the number of an interval $δ_{n} = (n_{1}, n_{2}, \dots, n_{s})$ containing points in $M$ , by virtue of which $n_{1}, n_{2}, \dots, n_{l} \in F$ . We denote by $n_{l + 1}$ the smallest number belonging to the set F which is not equal to $n_{i}$ for $i = 1, 2, \dots, l$ , and if there is no such number, then $n_{l + 1} = n_{l}$ . We put $δ_{φ (n)} = (n_{1}, n_{2}, \dots, n_{l}, n_{l + 1})$ . Obviously $δ_{φ (n)}$ intersects with $M$ . We consider the sequence of intervals in which the game occurs: $\begin{matrix} δ_{1}, δ_{1}^{*}, \dots, δ_{m}, δ_{m}^{*}, \dots . \end{matrix}$ We note that: (1) for each m, all of the numbers of the tuples10

¹⁰

As is well known, Baire intervals are identified with tuples of natural numbers.

\begin{matrix} δ_{m} = (n_{1}, n_{2}, \dots, n_{p}) and δ_{m}^{*} = (n_{1}, n_{2}, \dots, n_{p^{*}}) \end{matrix}

belong to F; (2) any number

q \in F

will be sooner or later encountered in the tuples

{δ_{m}, δ_{m}^{*}}

, because going from

δ_{m}

δ_{m}^{*}

we add a still unchosen element of the set F (if it exists). But then the sequence

{δ_{m}, δ_{m}^{*}}

contracts to the point

b = (n_{1}, n_{2}, n_{3}, \dots, n_{l}, \dots)

where the set

{n_{i}}

coincides with F, i.e.,

b \in M

. This proves the theorem.

A partial recursive operator T is called fully applicable to a problem B if it is defined on each solution function of the problem B. The class of all p.r.o.s which are fully applicable to the problem B will be denoted by $Q_{B}$ .

If a problem A reduces strongly (weakly) to a problem B by means of operators of a certain class P, then we say that A is strongly (weakly) P-reducible to B.

Let U be some class of p.r.o.s. A problem B is called U-uniform if any of its non-empty intervals is strongly reducible to it by means of operators of the class U.

The class of p.r.o.s represented in the form of compositions11

¹¹

$R T [f]$ is the result of successive application of the p.r.o.s R and T to the function f.

R T [f]

where

R \in P

and

T \in U

will be denoted by

P U

Theorem 11.

Let A be a closed problem, B a U-uniform winning problem, and P a subclass of $Q_{B}$ . If the problem A is weakly P-reducible to the problem B, then the problem A is strongly $P U$ -reducible to the problem B.

Proof. Let us assume that no operator of class $P U$ reduces the problem A to the problem B. We arrange all the p.r. operators of the class P in some sequence $\begin{matrix} T_{1}, T_{2}, T_{3}, \dots, T_{s}, \dots . \end{matrix}$ To each operator $T_{s}$ there corresponds a continuous function $θ_{s}$ in the Baire space (see [4]) defined at each point of the set $M_{B}$ , by virtue of $P \subset Q_{B}$ . By virtue of our assumptions, including continuity of the functions $θ_{s}$ and closedness of the set $M_{A}$ , there exists for each s an interval δ represented by the function $θ_{s}$ in $C M_{A}$ , the complement of $M_{A}$ . Let φ be the winning strategy for the set $M_{B}$ . By the method indicated above, we obtain for $T_{1}$ an interval $δ = δ_{1}$ . Let $n_{1}$ be the number of $δ_{1}$ ; let $r_{1} = φ (n_{1})$ ; let $δ_{1}^{*}$ be the interval numbered $r_{1}$ ; let $B_{1}$ be the problem defined by the set $M_{B} \cap δ_{1}^{*}$ , which is then a non-empty interval of the problem B.

Inasmuch as the problem B is U-uniform, the problem $B_{1}$ is strongly U-reducible to B. But then the problem A cannot be strongly P-reducible to $B_{1}$ , since in accordance with our assumption the problem A is not strongly $P U$ -reducible to B. Consequently, there exists a non-empty interval $δ_{2}$ intersecting with the set $M_{B}$ and transformed by the function $θ_{2}$ into a subset of $C M_{A}$ . Obviously it is possible to choose $δ_{2}$ so as to make $δ_{2} \subset δ_{1}^{*}$ . If $n_{2}$ is the number of $δ_{2}$ , then $r_{2} = φ (n_{2})$ is the number of a sub-interval $δ_{2}^{*}$ , $δ_{2}^{*} \subset δ_{2}$ , which also intersects with $M_{B_{1}}$ . Let $B_{2}$ be the problem defined by the set $\begin{matrix} M_{B_{1}} \cap δ_{2}^{*} = M_{B} \cap δ_{2}^{*} . \end{matrix}$ We define further in the same manner the intervals $\begin{matrix} δ_{3} \supset δ_{3}^{*} \supset δ_{4} \supset δ_{4}^{*} \supset \dots \end{matrix}$ and the problems $B_{3}, B_{4}, \dots$ .

The problem B, by virtue of U-uniformity, is strongly U-reducible to any problem $B_{s}$ , while the problem A does not reduce strongly to $B_{s}$ by any P-operator. By virtue of the winning character of the problem B and of the strategy φ, the sequence ${δ_{s}, δ_{s}^{*}}$ contracts to a point $f \in M_{B}$ .

Inasmuch as for any s the operator $T_{s}$ transforms the set $M_{B_{s}}$ into a subset of $C M_{A}$ , we have $T_{s} [f] = g \in C M_{A}$ for any s, and this means that the problem A does not reduce weakly to B by means of operators in the class P, which contradicts the conditions of the theorem. Consequently, the assumption that the problem A does not reduce strongly to B by means of operators in the class $P U$ is incorrect. The theorem is proved.

Our desire to be as general as possible has made it necessary to formulate the theorem in a rather cumbersome manner. We present some simply formulated corollaries of Theorem 11.

Corollary 1.

If a closed problem A reduces weakly to a uniform winning problem B by means of operators of the class $Q_{B}$ , then A reduces strongly to B.

A U-uniform problem is called general recursively uniform if U is the class of general recursive operators [4,11]. Problems of solvability, separability, and enumerability are general recursively uniform.

Corollary 2.

If a closed problem A reduces weakly to a general recursively uniform problem B by means of general recursive operators, then problem A reduces strongly to problem B by means of a general recursive operator.

In conclusion, we formulate some unsolved problems.

Is it possible to strengthen the fundamental theorem in such a way that weak reducibility (by means of arbitrary partial recursive operators) of a closed problem A to a uniform problem B would imply strong reducibility of A to B?

Under what “natural” conditions imposed on problems A and B does weak reducibility (by means of an arbitrary p.r.o.) imply strong reducibility?

What is the situation in the particular case when A is a solvability problem and B is a separability problem of enumerated recursively inseparable sets (we note that no non-trivial solvability problem A can be reduced strongly to a separability problem B [6,7]).

References

[1]

P.S.

Aleksandrov and

A.N.

Kolmogorov, Introduction to the General Theory of Sets and Functions, Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow–Leningrad, 1948.

[2]

S.C.

Kleene and

E.L.

Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics. Second Series 59(3) (1954), 379–407.

[3]

Kolmogoroff, Zur Deutung der intuitionistischen Logik, Mathematische Zeitschrift 35(1) (1932), 58–65.

[4]

A.V.

Kuznetsov and

B.A.

Trakhtenbrot, Investigation of partial recursive operators by means of the theory of Baire space, Doklady Akademii Nauk SSSR 105(5) (1955), 897–900.

[5]

Y.T.

Medvedev, Degrees of difficulty of mass problems, Doklady Akademii Nauk SSSR 104(4) (1955), 501–504.

[6]

A.A.

Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR 108(2) (1956), 194–197.

[7]

A.A.

Muchnik, On the reducibility of problems of solvability of enumerable sets to problems of separability, Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 29 (1965), 717–724.

[8]

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50(5) (1944), 284–316.

[9]

E.D.

Stotskii, On the descriptive theory of games, in: Problemy Kibernetiki (Problems of Cybernetics), Vol. 8, Fizmatgiz, Moscow, 1962, pp. 45–54.

10.

[10]

B.A.

Trakhtenbrot, On recursive separability, Doklady Akademii Nauk SSSR 88(6) (1953), 953–956.

11.

[11]

B.A.

Trakhtenbrot, Tabular representation of recursive operators, Doklady Akademii Nauk SSSR 101(3) (1955), 417–420.

12.

[12]

V.A.

Uspenskii, Gödel’s theorem and the theory of algorithms, Doklady Akademii Nauk SSSR 91(4) (1953), 737–740.