RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Generalised immune sets

P. Flajolet, J.M. Steyaert

Rapport de Recherche n°40
novembre 1973
# GENERALISED IMMUNE SETS

P. Flajolet - J.M. Steyaert

(Presented by M. Nivat)

## Résumé :

Nous étudions une généralisation de la notion d'immunité en récursivité : un ensemble est -immune s'il ne possède aucun sous-ensemble infini dans la famille .

Nous construisons de tels ensembles, prenant pour les notions habituelles de complexité : classes de Grzegorczyk, classes de complexité abstraites, classes de machines de Turing utilisant une quantité limitée de ressources. Si nous considérons comme faciles à reconnaître les éléments de ces classes, nous construisons donc des ensembles qui n'ont que des sous-ensembles (non triviaux) durs à reconnaître.

Des résultats d'indécidabilité s'en déduisent qui peuvent s'interpreter comme des propriétés de compacité de programmes dans des langages de programmation subrecursifs de puissances différentes.

## Abstract :

A generalisation of the concept of immunity in recursive function theory is investigated : being a class of sets, a set is -immune iff it has no infinite subset in .

Such sets are constructed when we take for the usual complexity classes : classes defined by nesting of loops, complexity classes in any abstract measure and Turing machine tape or time bounded classes. Considering the elements of these classes as "easy", we thus construct sets which have only "hard" non trivial subsets.

Unsolvability results are derived which can also be interpreted as properties about program compactness in subrecursive programming languages of different powers.
# 1- Introduction :

The aim of this paper is to construct sets which have only "hard" non trivial (i-e infinite) subsets when we take for hard the various notions introduced in complexity theory. As independently noticed by Constable [4] and the authors[5],[6] , this concept is strongly reminiscent of the notion of immune set in recursive function theory ; indeed, an immune set is an infinite set that has no infinite recursively enumerable (r-e) subset.

Constable [4] shows the existence of such sets by a diagonal argument based on list processing. We proceed differently and use a more natural method closer to Post's original construction of an immune set : this enables us to deal uniformly with loop classes and complexity classes, as opposed to Constable's construction.

It also has the further advantage of being suitable for cost evaluation in the case of Turing machine computations : for instance, we can obtain an exponential (w. r. t. time) law having no infinite polynomial sublaw ; this can be conjectured to be the case for the law of primes.

We can also derive a whole class of undecidability results for membership problems :

Let $\mathcal{A}$ and $\mathcal{B}$ be two classes of subsets of $N$ with $\mathcal{A} \notin \mathcal{B}$ ; the membership problem of $\mathcal{B}$ w. r. t. $\mathcal{A}$ is to determine whether an element of $\mathcal{B}$ (given by its index in a standard enumeration $\mathcal{B}$) belongs to the smaller class $\mathcal{A}$ . Similarly hierarchy problems, viz problems of placing a set in a hierarchy of classes, can be shown to be rather highly unsolvable : this applies as well to hierarchy of loop classes or hierarchy of languages defined by multihead automata as in Flajolet-Steyaert [6].
Finally, we show that these unsolvability results can be interpreted
as results about program compactness in subrecursive programming langua-
ges of different powers, which provides an easy proof of results of Meyer [13]

2. The basic construction :

In this section we give a particular construction of an infinite set $I \subset N$
having no infinite subset in a denumerable class $\mathcal{B}$ of subsets of $N$.

We first notice that I has no infinite subset belonging to $\mathcal{B}$ iff its com-
plement intersects all the infinite elements of $\mathcal{B}$. This follows from equivalence
between (1) and (2) below :

$$
(1) \quad \forall A \text{ infinite} \quad \left[ A \subset I \longrightarrow A \notin \mathcal{B} \right]
$$

$$
(2) \quad \forall A \text{ infinite} \quad \left[ A \in \mathcal{B} \longrightarrow \exists I \neq \emptyset \right]
$$

The problem of finding such an I has always a trivial solution which
consists in taking I finite and S= I cofinite. Putting these solutions away, we
define.

**Definition :** — A set is **B**-immune iff it is infinite and has no infinite subset which belongs to **B**.

- A set is **B** -simple iff it is co-infinite and intersects every infinite element of **B**.

As noted above, a set is **B**-simple iff its complement is **B**-immune.
These two concepts are clear extensions of the corresponding notions in recursive function theory (cf. Rogers [16]). In our framework, an immune set in the classical sense is an r. e. -immune set and a simple set is an r. e. -simple set which is itself r. e.

We now turn to the basic construction which is close to Post's original one as described in Rogers [16]

Let $\mathcal{B}$ be a denumerable class of subsets of $N$ and $\{B_i\}$ be an enumeration of $\mathcal{B}$; we shall also denote $j \in B_i$ by $B$ $(i, j)$ and call that binary predicate a universal relation for $\mathcal{B}$. We shall say that a class is recursive (primitive recursive...) if it has a recursive (primitive recursive...) universal relation.

A $\mathcal{B}$-simple set $S$ can be obtained by choosing an integer in every infinite element of $\mathcal{B}$, simultaneously ensuring that we keep $\overline{S}$ infinite. Following Post, we consider the set:

$$C(\mathcal{B}) = \{ (x, y) \mid B(x, y) \wedge y > 2x \}$$

and obtain a $\mathcal{B}$-simple set by a *choice* in $C(\mathcal{B})$ according to the first coordinate, i. e. for each $x$ we select a $y$ such that $(x, y) \in C(\mathcal{B})$ if there exists some $\mathcal{B}$; the set of all such $y$'s constitutes the $\mathcal{B}$-simple set. Clearly it intersects every infinite element in the family $\mathcal{B}$; it is co-infinite since in the interval $[0, 2n]$ we may choose only elements from $B_0, B_1, \dots, B_n$, and thus the simple set contains at most $n$-elements less or equal to $2n$.

Having in mind the case when $\mathcal{B}$ is recursive or subrecursive we alter Post's original construction and take a different choice operator, namely a boundary operator instead of a *single-valuedness* choice based on an enumeration.
That is, for each x, we select the smallest y, if it exists, such that $(x, y) \in C \mathcal{B}$

Our $\mathcal{B}$-simple set, call it S, is hence defined by :

$$ y \in S \quad \text{iff} \quad \exists x \left[ (x, y) \in C \mathcal{B} \wedge \forall t < y (x, t) \notin C \mathcal{B} \right] $$

$$ \text{iff} \quad \exists x \left[ B_x (y) \wedge y > 2x \wedge \forall t < y \left[ B_x (t) \wedge t > 2x \right] \right] $$

It is important to notice that the existential quantifier can be changed into a bounded quantifier since $\exists x [y > 2x \wedge \dots]$ is equivalent to $\exists x < y [y > 2x \wedge \dots]$. We can thus provide an equivalent definition of S :

$$ y \in S \quad \text{iff} \quad \exists x < y \left[ B_x (y) \wedge y < 2x \wedge \forall t < y \left[ t > 2x \rightarrow \neg B_x (t) \right] \right] $$

By the same token we obtain the relation defining a $\mathcal{B}$-immune set
$I = \bar{S}$ as :

$$ y \in I \quad \text{iff} \quad \forall x < y \left[ (B_x (y) \wedge y > 2x) \rightarrow \exists t < y \left[ B_x (t) \wedge t > 2x \right] \right] $$

This construction can be summarized in the following theorem :

**Theorem 1:** Let $\mathcal{B}$ be a demunerable class of subsets of $N$ and $C$ be a class of predicates over $N$. suppose $C$ satisfies both conditions.

(a) $C$ contains a universal relation for $\mathcal{B}$ and the binary relation $\lambda u v u > 2v$

(b) $C$ is closed under explicit transformations (i. e. changes of variables)
boolean operations and bounded quantification.

Then $C$ contains a $\beta$-immune set.

Let us point out that these conditions are fulfilled when take the couple $(C, \beta)$ to be (recursive, primitive recursive) or (primitive recursive, elementary recursive) or in general $(\mathbb{A}^{n+1}, \mathbb{A}^n)$ and $(\epsilon^{n+1}, \epsilon^n)_{n \ge 3}$. Here $\mathbb{A}^n$ and $\epsilon^n$ are respectively Rosza Peter's [15] and Grzegorczyk's [7] classes hence :

**Corollary 2 :** For each $n$, there exists in $\mathbb{A}^{n+1}$ an $\mathbb{A}^n$-immune set
For each $n \ge 3$, there exists in $\epsilon^{n+1}$ an $\epsilon^n$-immune set

**Complexity classes of sets**

The basic construction has been seen to apply to the "natural" complexity notions of recursive function theory. In this section, we show that it can be adapted to any measure which satisfies Blum's axioms [1]

**Definition :** (Blum) : -An abstract complexity measure is a couple of binary partial recursive functions $(\Phi, \Phi)$ such that.

(0) - $\Phi$ is an acceptable numbering of one place recursive functions

(1) - $\text{dom } \Phi = \text{dom } \Phi$

(2) - $\Phi$ has a recursive graph

As usual $\mathbb{A}(t)$ will denote the class of functions whose complexity is bounded almost every where (a. e) by a recursive function $t$ :

$$ \mathbb{A}(t) = \{ f \mid \exists i \phi_i = f \wedge \Phi_i \le t \text{ a. e} \} $$

Similarly $C(t)$ will denote the class of sets defined by characteristic
functions whose complexity is bounded a. e. by t :

$$
C(t) = \{ A \mid \exists i \ \Phi_i = \text{car}(A) \wedge \Phi_i \le t \text{ a. e.} \}
$$

$$
\text{with } \text{car}(A)(x) = \left. \begin{array}{l} \text{If } x \in A \quad \text{THEN} \quad \underline{\quad} \quad \text{ELSE} \quad \underline{\quad} \\ \phantom{\text{If } x \in A \quad \text{THEN} \quad \underline{\quad} \quad \text{ELSE}} 1. \end{array} \right\}
$$

It is well known that arbitrarily complex functions and sets exist
(cf Blum [1]). It can be shown that an infinite set always has subsets of
arbitrarily high complexity. On the other hand, some complex sets have
infinite subsets of very low complexity : for instance, the set of non primes
admits the set of even integers as an "easy" subset. In the sequel, we apply
results of section 2 to construct sets which have no "easy" infinite subsets.
This amounts to constructing C (t) -immune sets for all recursive t. We thus
establish a result obtained independently by Constable [4] using different
techniques.

Let us first notice that the construction of section 2 does not apply
directly here since complexity classes do not have in general a recursive
enumeration cf Lewis [12], Landweber-Robertson [11]. We shall thus proceed
in two steps : first we construct a recursive predicate which enumerates a
class $\mathcal{B}(t)$ containing $\mathcal{C}(t)$ as a subclass ; then we get a $\mathcal{B}(t)$-immune set by
the basic construction ; since $\mathcal{C}(t) \subseteq \mathcal{B}(t)$, this set will also be $\mathcal{C}(t)$-immune.

Let $r$ be a recursive function which takes infinitely often (i. o) any
value : $\forall x \exists y [r(y)=x]$. Let us define a relation $V$ by

$$
V(z, x) = \Phi(r(z), x) \leq \max(z, t(x)) \ \underline{\text{AND}} \ \Phi(r(z), x) = 0
$$

(we denote equivalently $\phi_i(x)$ and $\Phi_i(x)$ by $\phi(i, x)$ and $\Phi(i, x)$).
This relation is recursive since $\phi(r(z), x)$ can be evaluated only once $\Phi(r(z), x)$ has been seen to converge. It also enumerates a class $\mathcal{B}(t)$ which contains $\mathcal{C}(t)$ as a subclass. Indeed let $A$ be a set in $\mathcal{C}(t)$ with index $z_o$, let $p$ be such that $x > p$ implies $\Phi(z_o, x) \le t(x)$; $A$ is enumerated in $V$ by all $i$ such that $r(i)=z_o$ and $i > p$, i. e. by $r^{-1}(z_o) \cap [p, +\infty)$ which is a non empty set since $r^{-1}(z_o)$ is infinite.

Using the basic construction on the universal relation $V$, we obtain:

**Lemma 3:** For all recursive $t$, there exists a recursive $\mathcal{C}(t)$-immune set.

The next step consists in showing that the complexity of that $\mathcal{C}(t)$-immune set can be bounded above uniformly in $t$. However, in order to avoid conflict with the gap theorem of Borodin [3], we must further assume that $t$ is a self-computable function i. e. $t=\Phi_i$ for some $i$.

**Theorem 4:**

There exists a recursive function $s$ such that for every increasing self-computable function $t$ satisfying $\forall x t(x) \ge x$, then the class $\mathcal{C}(s, t)$ contains a $\mathcal{C}(t)$ immune set.

**Proof:** It proceeds through standard methods of complexity theory. First notice that in the construction of lemma 3, an index for the $\mathcal{C}(t)$-immune set can be obtained effectively from an index of $t$. Let $\xi$ be the total recursive function $s$.

$\phi_i$ total implies $\xi$ (i) is the index of this $\mathcal{C}(\phi_i)$-immune set.

Now apply an extended combining lemma (cf Hartmanis-Hopcroft [8]). Define
$$ p(i, n, m) = \begin{cases} \Phi_i^{(n)} \text{ if } \forall k \le n \ \xi^{(i)} \le m \\ \Phi_i^{(n)} \text{ otherwise} \end{cases} $$

and : $h(n, m) = \max_{i \ge n} P(i, n, m)$

Clearly $h(n, m)$ is increasing in $n$ and satisfies $\Phi_i^{(n)} \le h(n, \Phi_i^{(n)})$ whenever $\Phi_i$ is total and $n \ge i$.

The proof is completed by taking $s(x)=h(x,x)$ □

In the case of Turing machine tape and time complexity classes, the function $s$ above can be evaluated by other means; the complexity of computations is measured by the amount of resource necessary to process all the inputs of length $n$. A straight application of the basic construction would not give good results in the case of time bounded classes since the number of integers of length less than $n$ is exponential in $n$ and we should diagonalise over all of them. We shall thus diagonalise only on integers whose binary representation is a sequence of 1's. This is in fact equivalent to applying diagonalisation on integers represented in unary notation and then transferring the results for Turing machines with binary encoded inputs.

**Notations:** $UTIME(t)$-resp.$BTIME(t)$-is the class of sets given in unary-resp. binary-notation which are recognizable within time bound $t$ by some multitape Turing machine. The tape bounded classes $UTAPE$ and $BTAPE$ are defined similarly.

We also need an analogue of self computable functions : a function $t$ is time constructible iff it can be computed in unary notation within time $t$; tape constructible is similarly defined.
We can now state:

**Lemma 5:** Let $s(x)=x^5$. For increasing constructible functions $t(x) \le x$, UTIME ($s.o.t$) contains a UTIME ($t$)-immune set and UTAPE ($s.o.t$) contains a UTAPE ($t$)-immune set.

We give the proof only in the case of time bounded class, the simpler case of tape classes being omitted.

We first need a simulation lemma to provide us with a universal relation for UTIME ($t$). We use an adapted form of theorem 6 of Hartmanis and Stearns [9]. We have not tried to get sharper bounds that could be obtained by more evolved simulation techniques such as in Hennie-Stearns [10].

**Lemma 6:** Let $t$ be a time constructible function. There exists a numerisation $\delta$ of $t$ ($n$) time-restricted Turing machines working on unary inputs and a universal machine $U$ which, given the description $\delta(T)$ of machine $T$ and input $x$ in unary notations yields the result of $T$ applied to $x$ in time $\delta(T) \cdot t^2(x)$.

Lemma 6 provides us with a universal relation for UTIME ($t$) such that $U(i,j)$ is computable in time $i \cdot t^2(j)$. Let $J$ be the UTIME ($t$)-immune set obtained by the basic construction. An inspection of this construction shows that determining whether $x \in J$ requires only elementary evaluations of the kind $U(i,j)$ with $i,j \le x$. Due to additive properties of computation time, $x \in J$ can thus be evaluated in time of order:

$$ \theta(x) = \begin{cases} 1 & i \le x \\ 0 & j \le x \end{cases} $$

$\le x^2 \cdot x \cdot t^2(x)$ since $t$ is increasing

$\le t^5(x)$ since $t(x) \ge x$ □
Hence :

**Theorem 7:** Let $s(x)=x^5$. For increasing constructible functions $t(x) \ge x$, BTIME ($s_o t$) contains a BTIME ($t$)-immune set and BTAPE ($s_o t$) contains a BTAPE ($t$)-immune set.

**Proof:** Let $J$ be defined as above. Consider $I = \{2^n - 1 | n \in J\}$. The key property is that unary representation of elements in $J$ coincide with binary representation of elements in $I$. $I$ is BTIME ($t$)-immune; otherwise there would be $I'$ infinite $I' \subset I$ recognisable in time $t$ in binary notations. The set $J' = \{\Gamma \log p' | p \in I'\}$ whose unary representations coincide with binary representations for $I'$, would then be in UTIME ($t$), contradicting the fact that $J$ is UTIME ($t$)-immune. $\square$

In particular taking $t(x)=x^{\log x}$ we obtain in BTIME $(x^{5 \log x})$ a BTIME $(x^{\log x})$-immune set.

Since $\bigcup \text{BTIME}(x^p) \subseteq \text{BTIME}(x^{\log x})$
$p \in N$
and $\text{BTIME}(x^{5 \log x}) \subseteq \text{BTIME}(2^x)$, we get :

**Corollary :** There exist exponential (tape or time) recognisable sets having no polynomial (tape or time) infinite subsets.

The set of primes which is exponential time recognisable has been conjectured not to be polynomial ; the above corollary shows possibility of a stronger conjecture which might account for the failing of various attempts at finding easy sublaws to the law of prime numbers.
### Conjecture:

The law of prime numbers admits no easy (polynomial time) sublaw.

As pointed out by J. Berstel, this conjecture is linked to the existence of an infinity of primes in the set $\{2^p-1 | p \in N\}$.

### 4. The membership and hierarchy problems:

In this section, we use generalised immune sets to study the following problem. Let $\mathcal{A}$ and $\mathcal{B}$ be two denumerable classes of subsets of $N$ with $\mathcal{A} \subseteq \mathcal{B}$; let $B$ be an enumeration of $\mathcal{B}$. The membership problem $\text{MEMBER}[B, \mathcal{A}]$ is defined by: $\text{MEMBER}[B, \mathcal{A}](x) \text{ iff } B_x \in \mathcal{A}$.

For instance in the case when $\mathcal{A}$ is the class of elementary recursive sets and $\mathcal{B}$ the class of primitive recursive sets with $B$ as its standard enumeration, the membership problem $\text{MEMBER}[B, \mathcal{A}]$ is: "does a primitive recursive schema represent an elementary recursive set". ?

We shall suppose throughout that $B$ is recursive and $\mathcal{A}$ has a recursive universal relation $A$ (the properties do not actually depend on which enumeration is chosen).
In that case, the membership problem is written

$$ \text{MEMBER}[B\mathcal{A}] (x) \text{ iff } \exists y \forall t \left[ B_x(t) \leftrightarrow A_y(t) \right] $$

It is thus a $\Sigma_2$ predicate. (cf Rogers [16]).

A special case of the membership problem is the case when the smaller class is the set $\mathcal{B}$ of finite subsets of $N$; the membership problem $\text{MEMBER}[B\mathcal{B}]$ is then the finiteness problem for $B$ and denoted $\text{FINITE}[B]$. This latter problem which is also expressed in a $\Sigma_2$ form can in most cases be shown to be $\Sigma_2$-complete : it suffices that $\mathcal{B}$ contain a Turing predicate $T(z,x,y)$ whose informal interpretation is "y determines the computation sequence of machine z on input $x''$; more precisely $T$ satisfies :

$$ \text{ - } \forall s \forall x (!y) \quad T(s,x,y) \quad [! \text{ means "there exists at most one"}] $$

$$ \text{ - } \exists y \quad T(s,x,y) \text{ is an acceptable universal r. e.} $$

In particular, Grzegorczyk showed that such a predicate can be found in the simplest class $\mathcal{E}^0$.

Theorem 8 below gives a sufficient condition for $\text{FINITE}[B]$ to be reducible to $\text{MEMBER}[B,\mathcal{A}]$ and thus provides a useful tool for showing membership problems to be $\Sigma_2$-complete.

**Definition:** Let $H$ and $K$ be subsets of $N$; we define the *set composition* of $H$ and $K$, denoted $H*K$, as the set of those elements in $H$ whose rank in the natural enumeration of $H$ belongs to $K$.

$$ x \in H * K \text{ iff } x \in H \wedge \text{card} \left\{ u \mid u \in H \wedge u \le x \right\} \in K. $$
**Theorem 8**: If $\mathcal{A}$ and $\mathcal{B}$ enumerated by B satisfy the following conditions :

-1) $\mathcal{A}$ contains all the finite sets $\mathfrak{A} \subseteq \mathcal{A}$

-2) $\mathcal{B}$ contains an $\mathcal{A}$-immune set

-3) $\mathcal{B}$ enumerated by B is effectively closed under set composition

Then FINITE [B] is reducible to MEMBER [B, $\mathcal{A}$].

**Proof**: $\mathcal{B}$ enumerated by B is effectively closed under set composition if there exists a total recursive function $\mathcal{O}$ which represents set composition is B, i. e such that

$$B_i * B_j = B_{\mathcal{O}(i, j)}$$

Let $\Delta$ be an $\mathcal{A}$-immune set; take S an arbitrary set in B and consider $\Delta * S$. Two cases arise:

-If S is finite, $\Delta * S$ is a finite subset of $\Delta$, $\Delta * S \in \mathfrak{A}$, and from condition 1) $\Delta * S \in \mathcal{A}$

-If S is infinite, $\Delta * S$ is an infinite subset of $\Delta$ which does not belong to $\mathcal{A}$ (by immunity of $\Delta$).

The reduction is effective : let $\mathfrak{O}$ be an index of $\Delta$ in B, we have :

-If $S = B_x$ is finite then $B_\mathfrak{O} * B_x = B_{\mathfrak{O}(\mathfrak{O}, x)} \in \mathcal{A}$

-If $S = B_x$ is infinite then $B_\mathfrak{O} * B_x = B_{\mathfrak{O}(\mathfrak{O}, x)} \notin \mathcal{A}$
The function $\mathfrak{U}(x) = \sigma(\delta, x)$ thus completes the reduction :

$$ \text{FINITE}[\mathfrak{B}] < \text{MEMBER}[\mathfrak{B}, \mathfrak{a}] \quad . \Box $$

Notice that theorems 1 and 8 can be combined together.

If $\mathfrak{B}$ enumerated by $\mathfrak{B}$ is a class of predicates which possesses adequate closure properties, then the problem $\text{MEMBER}[\mathfrak{B}, \mathfrak{a}]$ is $\Sigma_2$-complete for all recursive classes $\mathfrak{a}$ containing the finite sets and having a universal relation in $\mathfrak{B}$. In that case the property is hereditary downwards; i. e., under the assumptions of theorem 8 the membership problem $\text{MEMBER}[\mathfrak{B}; \mathfrak{a}]$ is also seen to be $\Sigma_2$-complete for all recursive classes $\mathfrak{a}'$ such that $\mathfrak{a} \subsetneq \mathfrak{a}' \subsetneq \mathfrak{a}$. In particular the closure properties are shared by the classes $(\mathfrak{a}^n)^n \supset 3$ and $\mathfrak{a}^n$ given by then standard enumerations. Let $\mathfrak{R}^1$ be a standard enumeration of primitive recursive sets $\mathfrak{R}^1$; we obtain :

**Corollary 9:** For each $n$, the problem $\text{MEMBER}[\mathfrak{R}^1; \mathfrak{a}^n]$ is $\Sigma_2$-complete.

Theorem 8 also enables us to deal with hierarchy problems which are extension of membership problems.

Let $\{\mathfrak{a}_i\}$ be a hierarchy of recursive classes of sets $\mathfrak{a}^i \subsetneq \mathfrak{a}^{i+1}$ and let $\mathfrak{B} = \bigcup_{i \in \mathbb{N}} \mathfrak{a}_i$; let $\mathfrak{B}$ be a recursive enumeration of $\mathfrak{B}$. We introduce the *hierarchy function* $\mu_{\mathfrak{B}}$ defined by

$$ \mu_{\mathfrak{B}}(x) = n \quad \text{iff} \quad B_x \in \mathfrak{a}_n \setminus \mathfrak{a}_{n-1} $$

In other words, $\mu_{\mathfrak{B}}$ measures the exact complexity of the sets in $\mathfrak{B}$ with respect to the hierarchy of $\mathfrak{a}_i$.

The *hierarchy problem* is the two place relation $\mu_{\mathfrak{B}}(x)=n$. We can now state :
**Theorem 10**: Let {$\mathfrak{a}_i$}, $\mathfrak{B}$ and $B$ be defined as above.

suppose

1) The finite sets $\mathfrak{B}$ are contained in one of the $\mathfrak{a}_i: \mathfrak{B} \subset \mathfrak{a}_{i_0}$

2) For all $i$, $\mathfrak{B}$ contains an $\mathfrak{a}_i$-immune set

3) $\mathfrak{B}$ enumerated by $B$ is effectively closed under set composition

4) The finiteness problem FINITE $[B]$ is $\Sigma_2$-complete.

Then the hierarchy problem for $B$ w. r. t. the $\mathfrak{a}_i$ is strictly $\Delta_3$.

**Proof**: The hierarchy problem can be written :

$$ \mu_B(x) = i \quad \text{iff} \quad \text{MEMBER } [B; \mathfrak{a}_i] (x) \wedge $$

$$ \neg \text{MEMBER } [B; \mathfrak{a}_{i-1}] (x) $$

and therefore is in $\Delta_3$-form.

Conversely the membership problem $\text{MEMBER } [B, \mathfrak{a}_i] (x)$ is clearly equivalent to $\mu_B(x) \le i$, and theorem 8 entails that for $i > i_0$ this problem is $\Sigma_2$-complete.

Now suppose the hierarchy problem be $\Pi_2$; then $\text{MEMBER } [B, \mathfrak{a}_i] (x)$ which can be written $\exists k \le i$ [$\mu_B(x) = k$] would be $\Pi_2$ and we derive a contradiction when $i > i_0$. Suppose the hierarchy problem to be $\Sigma_2$, then $\text{MEMBER } [B, \mathfrak{a}] (x)$ which also writes $\forall k$ [$k > i \rightarrow \mu_B(x) \ne k$] would still be $\Pi_2$, leading again to a contradiction $\square$

**Corollary 11**: The hierarchy problem for primitive recursive sets w. r. t. Grzegorczyk's hierarchy or loop classes is strictly $\Delta_3$.

This is a stronger form of Meyer-Ritchie's unsolvability result [17]

**Corollary 12**: The hierarchy problem for two way multi head finite automata w. r. t. to the number of heads is strictly $\Delta_3$.

**Proof**: See Flajolet-Steyaert [5]. The hierarchy problem for one way multihead automata was first shown unsolvable by Rosenberg [18]
### 4. Program compactness:

Meyer [13] has noticed that the power of a language is not the only criterion of choice. In Meyer-Fischer [14] it is shown that context free descriptions for regular sets can be arbitrarily more compact than corresponding regular expressions. In [2] Blum obtained a similar result; descriptions of primitive recursive programs can be made arbitrarily more compact using "while" statements.

In this section, we show that immune sets together with undecidability results enable us to derive properties about program compactness in subrecursive languages of different powers.

We recall the notion of size of programs as axiomatically introduced in [2].

**Definition:** A recursive function $||: N \to N$ is called a size measure iff:

(i) there exists a finite number of programs of any given size, i. e. for all $y \in s^{-1}(y)$ is finite.

(ii) the finite set $s^{-1}(y)$ can be effectively recovered from y.

**Theorem 13:**

If the problem MEMBER $[B; a]$ is $\Sigma_2 - \Pi_2$ then B allows arbitrary program compactification for $a$; that is, given any recursive enumeration A for $a$ and two size measures $||_A$ and $||_B$:

$$ \forall f \text{ rec. } \exists B_i \in A \quad \forall j \quad [A_j = B_i \longrightarrow |j|_A > f(|i|_B)] $$
In other words, for all recursive (large) $f$, there exists a program written in language B whose size is shorter by $f$ than the sizes of all its equivalent programs in A.

**Proof:** Assume to the contrary that a recursive $f$ exists such that

$$ \forall i \left[ B_i \notin A \longrightarrow \forall j \left[ A_j = B_i \wedge \exists j \left( j \le f(|i|) \right) \right] \right] $$

First notice that in any case

$$ \forall i \left[ B_i \in A \longrightarrow \forall j \left[ \exists i \left( j \le f(|i|) \right) \longrightarrow A_j \ne B_i \right] \right] $$

Now we should have

$$ B_i \in A \quad \text{iff} \quad \exists_j \left[ j \le f(|i|) \wedge A_j = B_i \right] $$

The properties of size measures ensure that the desired $j$ is to be found in a finite set we can compute effectively from $i$.

Furthermore the problem $A_j = B_i$ is $\Pi_1$. Thus the membership problem $B_i \in \mathcal{A}$ would not be $\Sigma_2 - \Pi_2$ contradicting the hypothesis. □

For instance the language $R^1$ allows arbitrary program compactification w. r. t. the class $\mathcal{C}^3$ of elementary relations.

Furthermore if the conditions of theorem 8 are ensured the program compactification holds even for the simplest elements of A, namely the finite sets.
**Theorem 14:**

Under the conditions of theorem 8, B allows arbitrary program compactification for $\alpha$ on finite sets, i. e. :

$$ \forall f \text{ rec } \exists B_i \text{ finite } \forall j \left[ A_j = B_i \longrightarrow |j|_A > f (|i|_B) \right] $$

**Proof :** Assume to the contrary that an exists such that

$$ \forall B_i \left[ B_i \text{ finite} \longrightarrow \exists j \left[ |j|_A \le f (|i|_B) \land A_j = B_i \right] \right] $$

We use notations of the proof of theorem 8.

If $B_x$ is finite, then $B_\sigma(\delta, x)$ is finite

If $B_x$ is infinite, then $B_\sigma(\delta, x) \notin A$.

Thus we would have :

$$ B_x \text{ finite} \quad \text{iff} \quad B_\sigma(\delta, x) \text{ finite} $$

$$ \text{iff} \quad \exists j \left[ |j|_A \le f \left( \left| \sigma(\delta, x) \right|_B \right) \land A_j = B_\sigma(\delta, x) \right] $$

And hence FINITE [B] would not be $\Sigma_2 - \Pi_2$. $\square$

The above results can be reshaped to yield the following result of Meyer [13] established by completely different techniques.
**_Theorem 15:_**

(Meyer) : For every subrecursive language A, one can construct a language B primitive recursive in A such that B allows arbitrary program compactification for A on finite sets.

**_Proof:_** Take B to be the function which enumerates the elementary closure of A and apply the above results. □

It should be noticed that though our proofs deal with sets, they entail as an immediate consequence the corresponding properties for functions ; inspection of the proofs shows that the compactification can be obtained not only by any recursive function but also by any $A_2$ function (i. e. recursive in the halting problem), thus establishing Meyer's result in its full generality.

**_Notice:_** This work was done without the authors knowing Lewis ' work [19] whose motivation and results are similar to our § 4. In particular our theorem 8 is very close to (and actually entails) theorem 4 of Lewis.
REFERENCES

[1] Blum M. A machine-Independent Theory of the Complexity of Recursive Functions. JACM Vol 14 n°2 April 1967 pp 322-336.

[2] Blum M. On the size of Machines Informations and Control 11, 257-265 (1967).

[3] Borodin A. Computational Complexity and the Existence of Complexity Graps JACM, 19 (1972).

[4] Constable R. Hierarchy Theorems for Axiomatic Complexity, in Computational Complexity pp 37-63 edited by Randall Rustin-Algorithmics Press Inc (1973).

[5] Flajolet P. - Steyeart J. M. Decision Problems for Multi head Finite Automata Proceedings of MFCS Symposium pp 225-230 (1973).

[6] Flajolet P. - Steyeart J. M. Une formalisation de la Notion d'Algorithme de Tri non Récurrent Thèse de 3° cycle. Paris VII (1973).

[7] Grzegorczyk A. Some Classes of Recursive Functions, Rozprawy Matematyczne pp1 -46 (1953).

[8] Hartmanis-Hopcroft. An overview of the Theory of Computational Complexity JACM, 18 (1971).
[9] Hartamanis-Stearns. On the Computational Complexity of Algorithms, Trans AMS 117 (May 1965).

[10] Hennie-Stearns. Two-tape Simulation of Multi tape Turing Machines, JACM, 13 (1966).

[11] Landwerber-Robertson. Recursive Properties of Abstract Complexity Classes. Proc-2nd ACM symp-on Theory of Computing pp 31-36 (May 1970).

[12] Lewis F. D. Unsolvability Considerations in Computational Complexity. Proc 2nd ACM Symp-on Theory of Computing pp 22-30 (1970).

[13] Meyer A. Program Size, in Restricted Programming languages. Information and Control 21, 382-394 (1972).

[14] Meyer A. -Fischer M. Economy of Description by Automata, Grammars and Formal Systems Conference Record 1971. 12th Annual Symp-on Switching an Automata Theory pp 188-191.

[15] Peter R. Recursive Functions Academic Press 1966.

[16] Rogers H. Theory of Recursive Functions and Effective computability Mc Graw Hill 1966.

[17] Meyer A. - Ritchie D. Computational Complexity and program Structure I B M research report RC 1817 (1967).

[18] Rosenberg A. On multihead Finite Automata IBM Journal (1966) 388-394

[19] Lewis F. D. On unsolvability in Subrecursive classes of predicates. Harvard University report (1972).