UDC 517.11

MATHEMATICS

M. I. KANOVICH

ON THE COMPLEXITY OF DECIDING RECURSIVELY ENUMERABLE SETS

(Presented by Academician P. S. Novikov on 28 XI 1969)

The paper considers questions connected with estimates of the complexity of algorithms recognizing membership of natural numbers from a certain finite set in a recursively enumerable set. We use the terminology and concepts introduced in papers \((^{1-3})\).

Let \(\mathfrak M\) be a recursively enumerable set, and let \(n\) be a natural number. We shall call a \(\Phi\)-algorithm \(\mathfrak A\) an \((\mathfrak M,n)\)-deciding one if it is applicable to every natural number \(x\) not exceeding \(n\), and for every such \(x\)

\[ \mathfrak A(x) \simeq \Lambda \equiv x \in \mathfrak M . \]

We shall call a function \(f\) a lower estimate of the complexity of deciding the recursively enumerable set \(\mathfrak M\) if, whatever the natural number \(n\), every \((\mathfrak M,n)\)-deciding \(\Phi\)-algorithm has complexity not less than \(f(n)\).

We shall call a recursively enumerable set \(\mathfrak M\) effectively nonrecursive if there exists an unbounded general recursive function that is a lower estimate of the complexity of deciding the set \(\mathfrak M\).

1. Let \(\mathfrak M\) be a recursively enumerable set. We shall call a general recursive function \(g\) an enumeration of the set \(\mathfrak M\) if, for every natural number \(x\), the equivalence

\[ x \in \mathfrak M \equiv \exists n\,(g(n)=x) \]

holds.

We shall call a general recursive function \(f\) regular if, for any natural number \(k\), one can indicate a natural number \(m\) such that every natural number \(n\), as soon as \(f(n)=f(k)\), does not exceed \(m\).

Let \(f,g\) be a pair of general recursive functions. By the symbol \(f \triangleleft g\) we shall denote the following assertion: “the function \(f\) is nondecreasing and \(\forall n(f(n)\leq g(n))\).”

1.1. The following theorem is proved comparatively simply.

Theorem 1. a) Let the general recursive function \(g\) be an enumeration of the recursively enumerable set \(\mathfrak M\). Let there exist an unbounded general recursive function \(f\) such that \(f \triangleleft g\). Then the set \(\mathfrak M\) is recursive and the function \(g\) is regular.

b) Let the general recursive function \(g\) be regular and be an enumeration of the recursively enumerable set \(\mathfrak M\). Then one can indicate an unbounded general recursive function \(f\) such that \(f \triangleleft g\).

Thus, if a regular function \(g\) is an enumeration of a recursively enumerable set \(\mathfrak M\), then a necessary and sufficient condition for the nonrecursiveness of \(\mathfrak M\) is the absence of an unbounded general recursive function \(f\) such that \(f \triangleleft g\).

1.2. The following theorems indicate conditions satisfied by enumerations of effectively nonrecursive sets.

Theorem 2. Let the general recursive function \(g\) be an enumeration of an effectively nonrecursive set \(\mathfrak M\). Then for any partial-recursive-

function \(\varphi\) one can specify a natural number \(m\) such that, if \(\varphi\) is general recursive and \(\varphi \prec g\), then \(\forall n(\varphi(n) \leq m)\).

We introduce the following notation. Let \(f\) be a general recursive function. Denote by the symbol \(\chi(f)\) the formula

\[ \exists m \forall n(f(n)=0 \vee f(n)=m). \]

Let \(g\) be a general recursive function. By the symbol \(\vartheta(g)\) we shall denote the following statement: “there exists a partial recursive function \(\varphi\) such that, for every Gödel number \(k\) of a general recursive function \(f\) such that \(f \prec g\) and \(\chi(f)\), \(\varphi(k)\) is defined and \(\forall n(f(n)\leq \varphi(k))\).”

Theorem 3. Let the general recursive function \(g\) be a listing of a recursively enumerable set \(\mathfrak M\) such that \(\vartheta(g)\). Let \(h\) be an unbounded general recursive function. Then one can specify general recursive functions \(f\) and \(d\) such that: 1) the function \(f\) is a listing of the set \(\mathfrak M\); 2) \(\forall n(f(n)\leq d(h(n)))\); 3) the function \(f\) is regular if and only if the functions \(g\) and \(h\) are regular simultaneously.

Corollary 1. Let a regular general recursive function \(g\) be a listing of a recursively enumerable set \(\mathfrak M\) such that \(\vartheta(g)\). Then the set \(\mathfrak M\) is effectively nonrecursive.

1.3. The regularity condition for the listing in Corollary 1 is essential. This is asserted by the following theorem.

Theorem 4. For every infinite recursively enumerable set \(\mathfrak M\) one can specify a general recursive function \(g\) such that: 1) the function \(g\) is a listing of the set \(\mathfrak M\), and for every \(n\) the equation \(g(x)=n\) has no more than two roots; 2) for every partial recursive function \(\varphi\) one can specify a natural number \(m\) such that, if \(\varphi\) is general recursive and \(\varphi \prec g\), then \(\forall n(\varphi(n)\leq m)\).

1. In what follows we use the terminology and notation of the article \((^2)\).

A word \(R\) in the alphabet \(\Phi\) will be called an \(n\)-segment of the set \(\mathfrak M\) if: 1) the word \(R\) is an \((n+1)\)-dimensional Boolean vector; 2) \(\forall m(m\leq n \supset (\sigma_{m+1}(R)=1 \equiv m\in\mathfrak M))\).

Let \(f\) be a general recursive function. We shall call a set \(\mathfrak N\) an \(f\)-image of the set \(\mathfrak M\) if there exists a \(\Phi\)-algorithm \(\mathfrak A\) such that, whatever the natural number \(n\), the algorithm \(\mathfrak A\) is applicable to any Boolean vector \(R\) that is an \(f(n)\)-segment of the set \(\mathfrak M\), and for every such \(R\) the word \(\mathfrak A(R)\) is an \(n\)-segment of the set \(\mathfrak N\).

By the letter \(E\) we denote the general recursive function defined by the equality

\[ E(n)=n. \]

Theorem 5. For every recursively enumerable set \(\mathfrak M\) one can specify a recursively enumerable set \(\mathfrak N\) such that: 1) whatever the natural number \(n\), in the intersection of the set \(\{0,\ldots,3n\}\) and the set \(\mathfrak N\) there are no more than \([n/8]\) elements; 2) the set \(\mathfrak N\) is an \(E\)-image of the set \(\mathfrak M\); 3) if the set \(\mathfrak M\) is nonrecursive, then the set \(\mathfrak N\) is simple.

Corollary 2. There exist simple non-hypersimple* sets that are not effectively nonrecursive.

A recursively enumerable set \(\mathfrak M\) will be called effectively simple if its complement is not finite and, for every infinite recursively enumerable subset \(\mathfrak N\) of the complement of \(\mathfrak M\), one can

* We call a recursively enumerable set \(\mathfrak M\) non-hypersimple if there exists a strictly increasing general recursive function \(f\) such that, for every natural number \(n\), it is false that the set \(\{f(n), f(n)+1,\ldots,f(n+1)\}\) is contained in the set \(\mathfrak M\).

indicate a natural number \(n\) such that \(\mathfrak N\) contains no more than \(n\) numbers (cf. \((^4)\)).

The following theorem is comparatively easy to prove.

Theorem 6. Every effectively simple non-hyperimmune set is effectively nonrecursive.

Corollary 3. Every effectively simple set is simple.

The condition of non-hyperimmunity in Theorem 6 is essential, since there exist effectively simple hyperimmune sets (according to Theorem 4 of paper \((^5)\), all such sets are not effectively nonrecursive).

According to Theorem 6, Corollary 2 gives us an example of a simple set that is not effectively simple. The first example of such a set was constructed by J. Sacks \((^6)\), but his construction and proof are more complicated.

Corollary 4. Among simple non-hyperimmune sets that are not effectively simple, one can exhibit both effectively nonrecursive sets and sets that are not effectively nonrecursive.

Corollary 2, Theorem 6, and Corollary 4 refine Theorem 5 of paper \((^5)\).

Let \(F\) denote the general recursive function defined by the equality

\[ F(n)=3n. \]

Using Theorem 5, one can prove the following theorem.

Theorem 7. For any recursively enumerable set \(\mathfrak M\), one can indicate a recursively enumerable set \(\mathfrak N\) such that: 1) for every positive integer \(n\), it is false that the set \(\{2n,2n+1,\ldots,3n\}\) is contained in \(\mathfrak N\); 2) the set \(\mathfrak N\) is an \(E\)-image of the set \(\mathfrak M\); 3) the set \(\mathfrak M\) is an \(F\)-image of the set \(\mathfrak N\); 4) if the set \(\mathfrak M\) is nonrecursive, then the set \(\mathfrak N\) is simple.

Theorem 7 makes it possible to obtain theorems on simple non-hyperimmune sets analogous to Theorem 1 of paper \((^5)\), Theorems 4.1 and 4.2 of paper \((^7)\), etc.

The author expresses deep gratitude to A. A. Markov for his attention and advice in writing this paper.

Moscow State University
named after M. V. Lomonosov

Received
27 XI 1969

References

1. A. A. Markov, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 42 (1954).
2. A. A. Markov, Izv. AN SSSR, ser. matem., 31, 161 (1967).
3. S. K. Kleene, Introduction to Metamathematics, Moscow, 1957.
4. A. I. Maltsev, Algorithms and Recursive Functions, Moscow, 1965.
5. M. I. Kanovich, DAN, 186, No. 5, 1008 (1969).
6. G. E. Sacks, Proc. Am. Math. Soc., 15, No. 1, 51 (1964).
7. N. V. Petri, DAN, 185, No. 1, 37 (1969).
8. N. A. Shanin, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 52, 226 (1958).