Learning theory in the arithmetic hierarchy II

Abstract

The present work determines the arithmetic complexity of the index sets of u.c.e. families which are learnable according to various criteria of algorithmic learning. Specifically, we prove that the index set of codes for families that are TxtFex$^a_b$-learnable is $\Sigma _4^0$-complete and that the index set of TxtFex$^*_*$-learnable and the index set of TxtFext$^*_*$-learnable families are both $\Sigma _5^0$-complete.

1 Introduction

At its heart, the goal of algorithmic learning theory is a formalization of the intuitive concept of learning. Specifically, algorithmic learning theory aims to formalize the process of extrapolation. As a rudimentary example of extrapolation, if one is given the finite sequence

$$\begin{aligned} 2,4,6,8 \end{aligned}$$

a natural conclusion is that the sequence represents an initial segment of the infinite sequence of all even numbers. The process of extrapolating a generative algorithm from given finite data is modeled in a number of different ways in algorithmic learning theory. The standard model of learning – introduced in Gold [8] – is explanatory learning or EX-learning. A computable function $M: 2^{< \omega } \rightarrow \omega$ EX-learns a computably enumerable (c.e.) set $A \subseteq \omega$ iff, for any enumeration $f : \omega \rightarrow \omega$ of A,

$$\begin{aligned} (\exists e) \big (W_e = A \wedge (\forall ^\infty n)(M (f \upharpoonright n) = e) \big ) \end{aligned}$$

Recall that $W_e$ is the c.e. set with Turing code e. The topic of learning families of c.e. sets has been studied extensively (for example, see [1, 10]. A computable machine M EX-learns a uniformly c.e. (u.c.e.) family ${\mathcal {F}}$ if it EX-learns every $A \in {\mathcal {F}}$. While a family consisting of a single c.e. set can always be learned by an appropriate M, there are many families which are not EX-learnable. For instance, the family consisting of the finite sets $\{ 0, \ldots , n\}$ together with $\omega$ cannot be EX-learned. In this case, any learning machine which identifies the finite sets in this family will fail to identify $\omega$ from suitably chosen enumerations.

With this in mind, it is natural to ask which u.c.e. subsets of ${\mathcal {P}} (\omega )$ are EX-learnable. In [3], author A. Beros took up this question from the point of view of definable complexity. Specifically, A. Beros showed that the set of Turing codes for u.r.e families which are EX-learnable is $\Sigma ^0_4$-complete. The lower bound was achieved by a finite injury priority construction which reduced an arbitrary $\Sigma ^0_4$ predicate the set EXL of Turing codes for EX-learnable u.c.e. families. The upper bound (i.e., the statement that EXL is $\Sigma ^0_4$) relied upon a result of Blum–Blum [4] to the effect that a u.c.e. family is EX-learnable if it is EX-learnable from computable enumerations. Whereas the definition of an EX-learnable family is apparently $\Pi ^1_1$, the theorem of Blum–Blum guarantees that the initial universal quantifier can be restricted to only those functions $f: \omega \rightarrow \omega$ which are computable.

There are a number of learning criteria besides EX-learning which differ according to what type of convergence is required from the learning machine M [5, 6] as well as the types of errors M is permitted to make [7] and the use of oracles [11]. For instance, a machine M BC-learns a set A if, given any enumeration f of A,

$$\begin{aligned} (\forall ^\infty n) (W_{M(f \upharpoonright n)} = A). \end{aligned}$$

In other words, although $M (f \upharpoonright n)$ is allowed to change infinitely many times as n increases, $M (f \upharpoonright n)$ must be a Turing code for A for cofinitely many n. In [3], A. Beros showed that the set of all codes for u.c.e. families which BCL-learnable is $\Sigma ^0_5$-complete. In this case, the upper bound required a BC-learning analogue of Blum–Blum’s theorem: if a family is BC-learnable from $\Delta ^0_2$ enumerations, it is BC-learnable from arbitrary enumerations.

Vacillatory learning models strike a compomise between the infinitely many distinct hypotheses of BC-learning and the discrete convergence of EX-learning. Specifically, the learning machine is permitted to change its output infinitely many times (or vacillate) between finitely many distinct codes for the set to be learned, i.e.,

$$\begin{aligned} \{ M(f \upharpoonright n) : n \in \omega \} \end{aligned}$$

must be a finite set.

There are further learning criteria whereby the learning machine is permitted to output codes for sets which are merely equal to the set to be learned modulo finite sets. For instance, a computable function $M : 2^{<\omega } \rightarrow \omega$ TxtFex$_*^*$ -learns a c.e. set A if, given any enumeration $f : \omega \rightarrow \omega$ of A, there is a finite set F such that

• $(\forall ^\infty n) (M(f \upharpoonright n) \in F)$ and

• $(\forall e \in F) (W_e \text{ and } A \text{ have } \text{ finite } \text{ symmetric } \text{ difference})$.

TxtFex$_*^*$-learning is therefore a criterion which permits both vacillation and errors. Placing fixed bounds on the number of vacillations and/or the number of errors permitted yields an infinite number of distinct learning criteria. If the symmetric difference $W_e \triangle A$ is permitted to have cardinality at most a and only b many vacillations are allowed, the resulting learning criterion is denoted TxtFex$^a_b$. If $a \in \omega$, a family is TxtFex$^a_*$-learnable if only a many errors, but arbitrarily many vacillations are permitted. Details of these definitions are given in the next section.

The results in the present work cover a variety of different vacillatory learning criteria and establish definable complexity results in each case.

Theorem 3.5

For $a \in \omega$ and $b \in \omega \cup \{ * \}$, the set of Turing codes for u.c.e. families which are TxtFex$^a_b$-learnable is $\Sigma ^0_4$-complete.

Theorem 4.2

The set of Turing codes for u.c.e. families which are TxtFex$_*^*$-learnable is $\Sigma ^0_5$-complete.

This latter result uses machinery developed by author A. Beros in his doctoral thesis and published in [3].

2 Preliminaries and notation

2.1 Fundamental notions

For the most part, the terminology of this paper is standard. For reference, this section contains a summary of the relevant notation. We refer the reader to [12] for more on computability theory and to [9] for learning theory.

For $e \in \omega$, let $\varphi _e$ be the Turing machine coded by e. The domain of $\varphi _e$ is denoted by $W_e$. If M is any computable function, $M(\alpha ) \downarrow$ indicates that M converges on input $\alpha$. The notation $M(\alpha ) \downarrow _t$ indicates that M has converged on input $\alpha$ within t computation stages. Similarly, $M(\alpha ) \uparrow$ indicates that M never halts on input $\alpha$ and $M(\alpha ) \uparrow _t$ indicates that M has not yet converged on input $\alpha$ after t stages.

Let |A| denote the cardinality of A. For sets $A , B \subseteq \omega$, let $A \triangle B$ denote the symmetric difference of A and B. Let $A =^* B$ indicate that A and B are equal mod finite, i.e., $|A \triangle B| < \infty$. If $|A \triangle B| \le a$ for some fixed $a \in \omega$, write $A =^a B$.

If $f : \omega \rightarrow \omega$ is any function, let $f \upharpoonright n$ denote the restriction of f to the set $\{ 0 , \ldots , n-1\}$.

For $A \subseteq \omega$, let $A^{<\omega }$ denote the set of finite strings of elements of A. If $\sigma , \tau \in A^{<\omega }$, write $\sigma \preceq \tau$ to indicate that $\sigma$ is a prefix of $\tau$. Likewise, if $f : \omega \rightarrow A$, let $\sigma \prec f$ indicate that $\sigma$ is a prefix of f.

2.2 Vacillatory learning preliminaries

The present paper focuses on the following family of vacillatory learning criteria.

Definition 2.1

Let $a,b \in \omega \cup \{ * \}$. A partial computable function $M : \omega ^{<\omega } \rightarrow \omega$ $\text{ TxtFex}^a_b$ -identifies a c.e. set $A \subseteq \omega$ iff, for any $f : \omega \rightarrow A$ which enumerates A, there is a set $F \subseteq \omega$ such that

• F is finite if $b = *$ and $| F | \le b$ if $b \in \omega \setminus \{0\}$,

• $(\forall ^\infty n) (M(f \upharpoonright n) \downarrow \ \& \ M(f \upharpoonright n) \in F)$ and

• $(\forall e \in F) (W_e =^a A)$.

When $a = *$, the only requirement in the final clause is that $W_e$ equal A modulo finite sets.

The function M TxtFex$^a_b$ -learns a u.c.e. family ${\mathcal {F}} \subseteq {\mathcal {P}} (\omega )$ iff it identifies each $A \in {\mathcal {F}}$. Finally, a u.c.e. family is TxtFex$^a_b$ -learnable iff there exists a machine M which learns ${\mathcal {F}}$.

Theorem 4.2 below concerns another form of vacillatory learning.

Definition 2.2

A computable function on strings TxtFext$^*_*$ -identifies a c.e. set A iff it TxtFex$^*_*$-identifies A and the finite set F in the definition above has the additional property that

$$\begin{aligned} (\forall e_1 , e_2 \in F)(W_{e_1} = W_{e_2}). \end{aligned}$$

The definitions of “TxtFext$^*_*$-learning” and “TxtFext$^*_*$-learnable” are analogous to the ones above in the TxtFex$^*_*$ case.

The following is a useful observation.

Proposition 2.3

If M TxtFex$^a_b$-identifies or TxtFext$^*_*$-identifies a c.e. set $A \subseteq \omega$, there is a string $\sigma \in A^{<\omega }$ such that, for every $\tau \in A^{<\omega }$,

$$\begin{aligned} M(\sigma {}^\smallfrown \tau ) \in \{ M(\alpha ) : \alpha \preceq \sigma \}. \end{aligned}$$

Proof

Suppose otherwise. This implies that every $\sigma \in A^{<\omega }$ has an extension $\sigma ' \in A^{<\omega }$ such that

$$\begin{aligned} M(\sigma ') \notin \{ M(\alpha ) : \alpha \preceq \sigma \}. \end{aligned}$$

In other words, the set

$$\begin{aligned} X = \{ \sigma \in A^{<\omega } : (\exists \sigma ' \succeq \sigma ) (M( \sigma ') \notin \{ M(\alpha ) : \alpha \preceq \sigma \}) \} \end{aligned}$$

is dense in $A^{<\omega }$. It is therefore possible to inductively define an enumeration f of A such that

$$\begin{aligned} \{ M(f \upharpoonright n) : n \in \omega \} \end{aligned}$$

is infinite. In particular, M does not identify A from f. This is a contradiction. Note that, since X is c.e., f can be made recursive. $\square$

What follows is a powerful result due to John Case, reproduced for the reader’s convenience. This result is a cornerstone of the complexity upper bounds obtained in the present paper.

Theorem 2.4

(Case [6], Theorem 5.5) Let $a,b \in \omega \cup \{ * \}$. If M TxtFex$^a_b$-learns a family ${\mathcal {F}} \subseteq {\mathcal {P}} (\omega )$ from computable enumerations, then there exists a total computable ${{\widehat{M}}} : \omega ^{< \omega } \rightarrow \omega$ which TxtFex$^a_b$-learns ${\mathcal {F}}$ from arbitrary enumerations.

Remark 2.5

A routine modification of Case’s proof establishes the same result for TxtFext$^*_*$-learning.

3 Vacilation with bounded error

Definition 3.1

For $a \in \omega \cup \{*\}$ and $b \in \omega \cup \{*\}$, let $\text{ FEXL}^{a}_{b}$ denote the index set of natural numbers coding u.c.e. families which are $\text{ TxtFex}^a_b$-learnable.

Theorem 3.2

For $a \in \omega$ and $b \in \omega \cup \{ * \}$, the index set FEXL$^a_b$ has a $\Sigma ^0_4$ description.

First, a lemma.

Lemma 3.3

$\{ \langle y,z \rangle : m \le |W_y \triangle W_z| \le n\}$ is $\Delta ^0_3$ for all $m,n \in \omega$.

Proof

Fix $m,n \in \omega$ and let $A = \{ \langle y,z \rangle : m \le |W_y \triangle W_z| \le n\}$.

$$\begin{aligned} \langle y,z \rangle \in A \iff |W_y \triangle W_z| \le n \wedge |W_y \triangle W_z| \ge m. \end{aligned}$$

In other words,

$$\begin{aligned} (\exists x_0&, \ldots , x_{m-1}, s)(\forall t) \Big [ (\forall i,j \le m)\big (i \ne j \implies x_i \ne x_j\big ) \wedge \\&\bigwedge _{i \le m-1}(x_i \in W_{y,s} \wedge x_i \not \in W_{z,t}) \vee (x_i \in W_{z,s} \wedge x_i \not \in W_{y,t}) \Big ]\\&\wedge (\forall x_0, \ldots , x_{n})\Big [ (\forall i,j \le n)\big ( i \ne j \implies x_i \ne x_j \big ) \implies \\&\bigvee _{i \le n}(x_i \in W_y \cap W_z) \vee (x_i \not \in W_y \cup W_z) \Big ] \end{aligned}$$

which is the conjunction of a $\Pi ^0_2$ statement with a $\Sigma ^0_2$ statement. $\square$

Proof

(Proof of Theorem 3.2) For each $e \in \omega$, let ${\mathcal {L}}_e$ denote the u.c.e. family coded by e. For each i, let

$$\begin{aligned} {\mathcal {L}}_e [i] = \{ j : \langle i , j \rangle \in {\mathcal {L}}_e\}. \end{aligned}$$

That is, ${\mathcal {L}}_e [i]$ is the ith set in the family ${\mathcal {L}}_e$. For each $p \in \omega$, let

$$\begin{aligned} M_p : 2^{< \omega } \rightarrow \omega \end{aligned}$$

be the learning machine coded by p.

First of all, if a family ${\mathcal {L}}_e$ is learnable, say by M, there is a total learner ${{\widehat{M}}}$ which also learns ${\mathcal {L}}_e$. Indeed, let ${{\widehat{M}}}$ be defined by

$$\begin{aligned} {{\widehat{M}}} (\sigma ) = {\left\{ \begin{array}{ll} M(\sigma \upharpoonright n) &{} \text{ where } n \text{ is } \text{ largest } \text{ such } \text{ that } M(\sigma \upharpoonright n) \\ &{} \text{ converges } \text{ in } |\sigma | \text{ computation } \text{ stages },\\ 0 &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

The learner ${{\widehat{M}}}$ learns every subset of $\omega$ that M learns. To see this, suppose that M learns a set $A \subseteq \omega$. Let $f : \omega \rightarrow \omega$ be any enumeration of A. Let $n_0$ be large enough that $W_{M(f \upharpoonright n)} =^a A$ for each $n \ge n_0$. Let $n_1 \ge n_0$ be large enough that $M(f \upharpoonright n_0) \downarrow$ within $n_1$ computation stages. It follows that, if $\sigma \prec f$ and $|\sigma | \ge n_1$, then ${{\widehat{M}}}( \sigma ) = M( f \upharpoonright n)$ for some $n \ge n_0$. Hence, $W_{{{\widehat{M}}} (\sigma )} =^a A$. This shows that ${{\widehat{M}}}$ learns A.

Next, by Case’s Theorem (Theorem 2.4), it follows that a family is learnable iff it is learnable from computable enumerations. Therefore, a family ${\mathcal {L}}_e$ is TxtFex$^a_b$ learnable iff there exists $p \in \omega$ such that, for all $x , i \in \omega$,

• (1) $M_p$ is total and,

• (2) if $\varphi _x$ is total and enumerates ${\mathcal {L}}_e [i]$, then

• (a) there exists a finite set $D \subseteq \omega$ such that

• (i) $|D| \le b$ (if $b \ne *$) and

• (ii) $(\forall ^\infty n) (\forall t) (M_p (\varphi _x \upharpoonright n) \downarrow _t \implies M_p (\varphi _x \upharpoonright n) \in D)$

• (b) and $(\forall j) (|W_j \triangle {\mathcal {L}}_e [i]| > a \implies (\forall ^\infty n) (\forall t) (M_p (\varphi _x \upharpoonright n)\downarrow _t \implies M_p (\varphi _x \upharpoonright n) \ne j))$.

Note that, in the case of $b = *$, condition (i) above is removed. Condition (b) says that if j is an incorrect code for ${\mathcal {L}}_e [i]$, there are cofinitely many n such that $M_p (\varphi _x \upharpoonright n) \ne j$.

To see that the predicate “${\mathcal {L}}_e$ is learnable” is $\Sigma ^0_4$, observe first that condition (1) above is $\Sigma ^0_2$. Next, notice that condition (i) is computable and condition (ii) is $\Sigma ^0_2$. Finally, condition (b) is $\Pi ^0_3$ by Lemma 3.3. It follows that condition (2) is $\Pi ^0_3$ and therefore, “${\mathcal {L}}_e$ is learnable” is $\Sigma ^0_4$. $\square$

The next objective is to show that TxtFex$^a_b$ is $\Sigma ^0_4$-hard. This is established by Theorem 3.5 below. The following example serves the basic building block in the proof of this theorem.

Example 3.4

For each $e \in \omega$, define a family ${\mathcal {L}}_e$ of c.e. sets as follows:

• if $e \in \mathrm{INF}$, i.e., $W_e$ is infinite, let ${\mathcal {L}}_e = \{ [e, \infty )\}$

• if $e \in \mathrm{FIN}$, i.e., $W_e$ is finite, let ${\mathcal {L}}_e = \{ [e,e+i+|W_e| ] : i \in \omega \}$

Now let ${\mathcal {F}} = \bigcup _e {\mathcal {L}}_e$.

In the first place, ${\mathcal {F}}$ is u.c.e. To see this, observe that ${\mathcal {F}}$ is the collection of all sets of the form

$$\begin{aligned} L_{e,i} = \{ x : (\exists s)(e \le x \le e + i + |W_{e,s}|) \}. \end{aligned}$$

Note that, if $e \in \mathrm{INF}$, then $L_{e,i} = [e, \infty )$ for each $i \in \omega$.

The key attribute of ${\mathcal {F}}$ is that it is not TxtFex$^a_b$-learnable for any $a \in \omega$ and $b \in \omega \cup \{*\}$. To prove this, it will suffice to show that ${\mathcal {F}}$ is not TxtFex$^a_*$-learnable for any $a \in \omega$. To this end, suppose that the contrary is true. Say M TxtFex$^a_*$-learns ${\mathcal {F}}$. By Case’s Theorem (Theorem 2.4 above), it is no loss to assume that M is total. Consider the $\Sigma ^0_2$ predicate Q given by

$$\begin{aligned} Q(e) \iff (\exists \sigma \in [e,\infty )^{<\omega }) (\forall \tau \in [e,\infty )^{<\omega }) (M(\sigma {}^\smallfrown \tau ) \in \{ M(\alpha ) : \alpha \preceq \sigma \}). \end{aligned}$$

Since INF is $\Pi ^0_2$-complete, a contradiction will be obtained by showing that $\mathrm{INF} = Q$.

Suppose $e \in \mathrm{INF}$. As M identifies $L_{e,i} = [e,\infty )$, it follows from Proposition 2.3 that there is a string $\sigma \in [e,\infty )$ with

$$\begin{aligned} M(\sigma {}^\smallfrown \tau ) \in \{M(\alpha ) : \alpha \preceq \sigma \} \end{aligned}$$

for all $\tau \in [e, \infty )^{<\omega }$. In other words, Q(e) holds.

For $e \in \mathrm{FIN}$, the machine M identifies each

$$\begin{aligned} L_{e,i} = [e , e + i + |W_e|]. \end{aligned}$$

Given $\sigma \in [e,\infty )^{< \omega }$, let $i > \max (\mathrm{content} (\sigma ))$ be large enough that, for all $\alpha \preceq \sigma$,

$$\begin{aligned} W_{M(\alpha )} \ne ^a [e , e + i + |W_e|]. \end{aligned}$$

Since M identifies $[e , e + i + |W_e|]$, there exists $\tau \in [e , \infty )^{<\omega }$ such that

$$\begin{aligned} W_{M(\sigma {}^\smallfrown \tau )} =^a [e , e + i + |W_e|]. \end{aligned}$$

In particular, $M(\sigma {}^\smallfrown \tau ) \notin \{ M(\alpha ) : \alpha \preceq \sigma \}$. Thus, $\lnot Q(e)$ holds. This yields a contradiction since it shows that $\mathrm{INF} = Q$ and Q is $\Sigma ^0_2$.

In the proof that follows, ${\mathcal {L}}_x$ and ${\mathcal {F}}$ are as in Example 3.4. The proof is based on ideas which arose from correspondence between the first author and Frank Stephan.

Theorem 3.5

For $a \in \omega$ and $b \in \omega \cup \{ * \}$, the index set FEXL$^a_b$ is $\Sigma _4^0$-hard.

Proof

In what follows, “learnable” means “TxtFex$^a_b$-learnable” for fixed $a \in \omega$ and $b \in \omega \cup \{ * \}$. No distinction need be made as the argument is identical for all such a and b.

Fix a $\Sigma ^0_4$ predicate P and a total computable function $f: \omega ^2 \rightarrow \omega$ such that for each $n \in \omega$,

$$\begin{aligned} P(n) \implies (\forall ^\infty x) ( f(n,x) \in \mathrm{COINF}) \end{aligned}$$

and

$$\begin{aligned} \lnot P(n) \implies (\forall x) ( f(n,x) \in \mathrm{COF}). \end{aligned}$$

Also, assume that f is strictly increasing in the second coordinate, i.e.,

$$\begin{aligned} f(n , 0)< f(n , 1) < \ldots \end{aligned}$$

for all $n \in \omega$.

Fix $n \in \omega$. Given $x,e,i,p \in \omega$, define $R^n_{x,e,i,p} \subseteq \omega$ as follows. First of all, assume $p \in W_{f(n,x)}$; otherwise, $R^n_{x,e,i,p}$ will be undefined. Let $I_{p,s}$ be the largest interval contained in $W_{f(n,x),s}$ with $p \in I_{p,s}$.

$$\begin{aligned} R^n_{x,e,i,p} = \Big \{ x : (\exists s) (e \le x \le e + i + \min \{|I_{p,s}|, |W_{e,s}|\} \Big \} \end{aligned}$$

Further, define ${\mathcal {R}}^n_{x,e,p} = \{ R^n_{x,e,i,p} : (\exists s)(i \le |I_{p,s}|) \}$. Now let

$$\begin{aligned} {\mathcal {F}}_n = \bigcup \Big \{ {\mathcal {R}}^n_{x,e,p} : x\in \omega \wedge f(n,x) \le e < f(n , x+1) \wedge p \in W_{f(n,x)} \Big \}. \end{aligned}$$

Since ${\mathcal {F}}_n$ is u.c.e., the proof will therefore be completed by showing that ${\mathcal {F}}_n$ is learnable iff P(n).

Recall now the families ${\mathcal {L}}_{e} = \{ L_{e,i} : i \in \omega \}$ from Example 3.4 above. Also, let ${\mathcal {A}}_{n,x,e}$ be the set of those members of ${\mathcal {F}}_n$ whose minimum element is e. Although the dependence of ${\mathcal {A}}_{n,x,e}$ on x is redundant, including it makes some formulas simpler to write.

Claim 1. If $f(n,x) \le e < f(n,x+1)$, $i \in \omega$ and $W_{f(n,x)}$ is cofinite, then $R^n_{x,e,i,p} = L_{e,i}$ for all but finitely many $p \in W_{f(n,x)}$.

To see why this is so, fix $p \in W_{f(n,x)}$ such that p is contained in an infinite interval of $W_{f(n,x)}$. Note that all but finitely many $p \in W_{f(n,x)}$ are contained in such an infinite interval. For such p, it follows from the definition of $R^n_{x,e,i,p}$ that

$$\begin{aligned} R^n_{x,e,i,p} = [e , e + i + |W_e|] = L_{e,i} \end{aligned}$$

if $W_e$ is finite, and

$$\begin{aligned} R^n_{x,e,i,p} = [e , \infty ) = L_{e,i} \end{aligned}$$

if $W_e$ is infinite. This establishes the claim.

Claim 2. If $W_{f(n,x)}$ is coinfinite, $R^n_{x,e,i,p}$ is finite for all e, i, p.

This follows from the fact that the minimum in the definition of $R^n_{x,e,i,p}$ will be bounded by the length of the interval in $W_{f(n,x)}$ which contains p.

Claim 3. If $W_e$ is infinite and $W_{f(n,x)}$ is cofinite, then ${\mathcal {A}}_{n,x,e}$ is a finite - hence learnable - family.

Indeed, in this case, claim 1 implies that, for all but finitely many $p \in W_{f(n,x)}$,

$$\begin{aligned} R^n_{x,e,i,p} = L_{e,i} = [e, \infty ). \end{aligned}$$

Hence ${\mathcal {A}}_{n,x,e}$ consists of the infinite set $[e , \infty )$ together with finitely many finite sets.

Towards the end of showing that ${\mathcal {F}}_n$ is learnable iff P(n), suppose first that P(n) holds. It follows from the choice of f that $W_{f(n,x)}$ is coinfinite for all but finitely many x, i.e.,

$$\begin{aligned} H = \{ x \in \omega : W_{f(n,x)} \text{ is } \text{ cofinite }\} \end{aligned}$$

is a finite set. Consequently, the set

$$\begin{aligned} G = \{ \langle x,e \rangle : x \in H \wedge e \in \mathrm{INF} \} \end{aligned}$$

is also finite. Let

$$\begin{aligned} {\mathcal {B}} = \bigcup \{ {\mathcal {A}}_{n,x,e} : \langle x,e \rangle \in G\} \end{aligned}$$

Since H is finite, claim 3 implies that ${\mathcal {B}}$ is a finite set as well. Hence, ${\mathcal {B}}$ is learnable, say by a total machine M. It follows from the definition of ${\mathcal {F}}_n$ that

$$\begin{aligned} {\mathcal {F}}_n \subseteq {\mathcal {B}} \cup {\mathcal {C}}. \end{aligned}$$

where ${\mathcal {C}}$ is a collection of finite sets. Therefore, if N is a total machine which learns all finite sets, ${\mathcal {F}}_n$ is learned by the machine ${{\widehat{M}}}$ with

$$\begin{aligned} {{\widehat{M}}} (\sigma ) = {\left\{ \begin{array}{ll} M (\sigma ) &{} \text{ if } (\exists x \in H) \big (\langle x, \min (\mathrm{content} (\sigma )) \rangle \in G\big ),\\ N(\sigma )&{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

for each string $\sigma \in \omega ^{<\omega }$.

Finally, suppose that $\lnot P(n)$. In this case, $W_{f(n,x)}$ is cofinite for every $x \in \omega$ and hence, for each pair e, i, $R^n_{x,e,i,p} = L_{e,i}$ all but finitely many p. It follows that ${\mathcal {F}}_n$ contains the non-learnable family ${\mathcal {F}}$ from Example 3.4. In particular, ${\mathcal {F}}_n$ is not learnable. This complete the proof. $\square$

4 Unbounded vacilation and error

4.1 Upper bounds

An upper bound for $FEXTL^*_*$ is obtained in a manner similar to $FEXTL^a_b$. The only distinction between the descriptions is $W_e=W_{e'}$ has a $\Pi _2^0$ description whereas $W_e=^{*}W_{e'}$ has a $\Sigma _3^0$ description. The defining arithmetic formula for $FEXTL^*_*$ is as follows.

$$\begin{aligned} (\exists a) (\forall k, i) \Big ( (M_a \text{ is } \text{ total}) \wedge (\phi _k \text{ is } \text{ total}) \wedge (\phi _k \text{ enumerates } L_i) \rightarrow \psi (k,a,i) \Big ) \end{aligned}$$

(1)

where we define $\psi (k,a,i)$ to be

$$\begin{aligned}&(\exists s,c) (\forall t \ge s) \\&\quad \Big (M_a(\phi _k \upharpoonright t) \in D_c \wedge \forall x,y\in D_c(W_x=W_y)\Big ) \wedge (\forall n) \Big (W_{M_a(\phi _k \upharpoonright n)} =^{*} L_i \\&\quad \vee (\exists m)(\forall u \ge m) \big ( M_a(\phi _k \upharpoonright m) \ne M_a(\phi _k \upharpoonright n) \big ) \Big ). \end{aligned}$$

The last formula is $\Pi _4^0$. Thus, (1) is $\Sigma _5^0$ and characterizes TxtFex-learning because, for any family coded by a number e which satisfies formula (1), there is a learner whose hypotheses converge to correct hypotheses on every computable enumeration and if e fails to satisfy formula (1), every learner must fail for some set in the family.

We have, therefore, exhibited a $\Sigma _5^0$ description of $FEXTL^{*}_{*}$. Notice the weakening of $FEXTL^{*}_{*}$ to $FEXL^{*}_{*}$ must also have a $\Sigma _5^0$ description. It is meaningful to study both $FEXTL^{*}_{*}$ and $FEXL^{*}_{*}$ as $FEXTL^{*}_{*} \ne FEXL^{*}_{*}$, a result due to the first author that appears in [2].

4.2 Lower bounds

Lemma 4.1

Let $M = M_m$ be a computable learning machine and $W_e$ a c.e. set. There is a family ${\mathcal {F}}_{m,e}$, uniformly computable in both m and e, such that:

• (1) If $W_e$ is coinfinite, then ${\mathcal {F}}_{m,e}$ is not TxtFex$^*_*$-learnable by M, but the family is TxtFext$^*_*$-learnable.

• (2) If $W_e$ is cofinite, then ${\mathcal {F}}_{m,e}$ is uniformly TxtFext$^*_*$-learnable in both m and e.

Proof

Fix a machine $M = M_m$ and a c.e. set $W_e$. We will construct a family

$$\begin{aligned} {\mathcal {F}}_{m,e} =\left\{ A, F^0_0, \ldots , F^0_{k_0}, F^1_0, \ldots , F^1_{k_1}, \ldots \right\} \end{aligned}$$

in stages. Each set in ${\mathcal {F}}_{m,e}$ will have two columns ($\{ \langle 0,x \rangle : x\in \omega \}$ and $\{ \langle 1,x \rangle : x\in \omega \}$) reserved for markers. Every set in ${\mathcal {F}}_{m,e}$ contains $\langle 0,\langle m,0 \rangle \rangle$ and $\langle 0,\langle e,1 \rangle \rangle$ and A contains the marker $\langle 0,\langle 0,3 \rangle \rangle$ as well. Unless otherwise indicated, any action during the construction is performed on the complement of the reserved columns. We identify this complement with $\omega$ as it is a computable copy. At any stage of the construction, there will be at most one $n \in \omega$ for which the sets $F^n_0, \ldots , F^n_{k_n}$ will be actively involved in the construction. When there is such a value n, we call $F^n_0, \ldots , F^n_{k_n}$ the active sets and n the active index. We also maintain an associated function $r_n$ which stores information about that those sets.

Stage 0: Search for the least string $\sigma$ on which M outputs a hypothesis. Set $\sigma _0$ equal to $\sigma$ and enumerate content$(\sigma _0)$ into A.

Stage s+1: Let $\sigma _0 \prec \ldots \prec \sigma _s$ be the sequence of strings passed to the current stage from stage s. If there is a currently active index n with active sets $F^n_0, \ldots , F^n_{k_n}$, then for $j\in W_{e,s+1}$, we enumerate $r_n(j), \ldots , r_n(j) + k_n$ into all of the active sets. We then consider four cases depending on the status of two parameters. First, the existence of an active index. Second, the availability, within computational bounds, of an extension $\alpha \succeq \sigma _s$ on which M outputs a hypothesis different from all the hypothesis it has output on prefixes of $\sigma _s$. We only consider the finite set of strings $S = \{ \sigma _s {}^\smallfrown \tau : (|\tau |<s+1) \wedge (\text{ content }(\tau ) \subset s+1) \}$ in our search for $\alpha$.

Case 1: Suppose there is no active index, but there is an extension $\alpha \in S$, of $\sigma _s$ such that $M(\alpha ) \not \in \{M(\tau ) : \tau \preceq \sigma _s\}$. We pick the least such $\alpha$. Set $\sigma _{s+1} = \alpha {}^\smallfrown \beta$, where $\beta$ is an increasing enumeration of $\{ x : x \le \text{ max(content }(\alpha )) \}$, and enumerate content$(\sigma _{s+1})$ into A.

Case 2: Next, consider the case where there is neither an active index nor an $\alpha \in S$ such that $M(\alpha ) \not \in \{M(\tau ) : \tau \preceq \sigma _s\}$. Let $n\in \omega$ be least such that n has never been the active index before, set $k_n = |\{M(\tau ) : \tau \preceq \sigma _s\}|$ and set $F^n_0, \ldots , F^n_{k_n}$ to be the active sets. Set $\sigma _{s+1} = \sigma _s$ and enumerate content$(\sigma _{s+1})$ into each of $F^n_0, \ldots , F^n_{k_n}$. Pick the least $q \in \omega$ such that no number greater than $(k_n + 1)q$ has appeared in the construction so far. Enumerate $(k_n + 1)q + i$ into $F^n_i$ for each $i \le k_n$.

Case 3: Let n be the active index and $F^n_0, \ldots , F^n_{k_n}$ be the active sets. Also, suppose $\alpha \in S$ is least such that $M(\alpha ) \not \in \{M(\tau ) : \tau \preceq \sigma _s\}$. Set $\sigma _{s+1} = \alpha {}^\smallfrown \beta$, where $\beta$ is an increasing enumeration of $\{ x : x \le \text{ max(content }(\alpha )) \}$, and enumerate content$(\sigma _{s+1})$ into A. Next, we “cancel” the active index and active sets. Specifically, we enumerate the marker element $\langle 1,\langle n,i \rangle \rangle$ into $F^n_i$ for each $i \le k_n$ and mark the sets as inactive.

Case 4: Finally, assume there is a currently active index n and active sets $F^n_0, \ldots , F^n_{k_n}$, but no $\alpha \in S$ such that $M(\alpha ) \not \in \{M(\tau ) : \tau \preceq \sigma _s\}$. Pick the least $q \in \omega$ such that no number greater than $(k_n + 1)q$ has appeared in the construction so far. Enumerate $(k_n + 1)q + i$ into $F^n_i$ for each $i \le k_n$ and set $r_n(i+1)=(k_n + 1)q$, where i is the greatest value for which $r_n(i)$ is defined.

To verify that the above construction produces a family with the desired properties, we must verify three statements:

• (1) ${\mathcal {F}}_{m,e}$ is TxtFext$^*_*$-learnable for all M and e.

• (2) If $W_e$ is coinfinite, then M does not TxtFex$^*_*$-learn ${\mathcal {F}}_{m,e}$.

• (3) If $W_e$ is cofinite, then there is a machine, computable from m and e, that TxtFext$^*_*$-learns ${\mathcal {F}}_{m,e}$.

If a natural number remains the active index cofinitely, then ${\mathcal {F}}_{m,e}$ is a finite family. If no such number exists, then every finite set has a unique marker by which it can be identified and the only infinite set is A. In either case, the family is learnable and we conclude that the first statement is true.

To prove the second statement, we must again consider two cases. Suppose $W_e$ is coinfinite. If $n \in \omega$ remains the active index cofinitely, then M outputs the same hypothesis on all extensions of a finite partial enumeration whose content is contained in each of $F^n_0, \ldots , F^n_{k_n}$. Thus, there are $k_n + 1$ enumerations, one for each of $F^n_0, \ldots , F^n_{k_n}$, on which M converges to the same hypothesis. The pairwise symmetric difference of any two active sets, however, is infinite. If no pair remains active infinitely, then there must be an infinite number of stages during the construction at which $\sigma _0 \prec \sigma _1 \prec \ldots$ are found such that $M(\sigma _{s+1}) \not \in M(\alpha ) \not \in \{M(\tau ) : \tau \preceq \sigma _s\}$ and A is enumerated by $f(n)=\sigma _n(n)$. In either case, M fails to TxtFex$^*_*$-learn ${\mathcal {F}}_{m,e}$.

Finally, we must exhibit a machine that can TxtFext$^*_*$-learn all possible families ${\mathcal {F}}_{m,e}$ where $e \in \text{ COF }$. In particular, a machine that can TxtFex$^*_*$-learn the following possibly non-u.c.e. family as well as every subfamily:

$$\begin{aligned} {\mathcal {G}} = \bigcup _{e\in \text{ COF }, m \in \omega } {\mathcal {F}}_{m,e}. \end{aligned}$$

Since $W_e$ is cofinite for all the families under consideration, observe that ${\mathcal {F}}_{m,e}$ consists of a (possibly infinite) number of finite sets and a finite number (A or $F^n_0, \ldots , F^n_{k_n}$) that are cofinite in the complement of the marker columns. Fix codes $a_0$, $a_1$ and $a_{m,e}$ such that $W_{a_0} = \emptyset$, $W_{a_1} = \omega \setminus \{ \langle x,y \rangle : (x=0 \vee x=1) \wedge y \in \omega \}$ and $W_{a_{m,e}}$ is the set $A \in {\mathcal {F}}_{m,e}$. For notational ease, let $C(k) = \{ \langle k,x \rangle : x \in \omega \}$. Define $N_{m,e}$ by

$$\begin{aligned} N_{m,e}(\sigma ) = {\left\{ \begin{array}{ll} a_0 &{} \text{ if } \text{ content }(\sigma )\cap C(1) \ne \emptyset , \\ a_{m,e} &{} \text{ if } \langle 0,\langle 0,3 \rangle \rangle \in \text{ content }(\sigma ), \\ a_1 &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Further, define a machine N by

$$\begin{aligned} N(\sigma ) = {\left\{ \begin{array}{ll} N_{m,e} &{} \text{ if } \langle 0,\langle m,0 \rangle \rangle ,\langle 0,\langle e,1 \rangle \rangle \in \text{ content }(\sigma ), \\ 0 &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$

To prove that N learns ${\mathcal {G}}$, select an arbitrary $D \in {\mathcal {G}}$. Let e and m be the codes such that $D \in {\mathcal {F}}_{m,e}$ for cofinite $W_e$.

Case 1: Suppose that, during the construction of ${\mathcal {F}}_{m,e}$, no natural number is the active index cofinitely. In this case, every member of ${\mathcal {F}}_{m,e}$ is marked, either with a marker in C(1) or with $\langle 0,\langle 0,3 \rangle \rangle$. Thus, N succeeds in TxtFex$^*_*$-learning ${\mathcal {F}}_{m,e}$.

Case 2: Suppose, on the other hand, that n remains active cofinitely during the construction. Let $F^n_0, \ldots , F^n_{k_n}$ be the sets that are active cofinitely. If $D = A$, then $\langle 0,\langle 0,3 \rangle \rangle \in D$ and cofinitely often $N_{m,e}$ hypothesizes $a_{m,e}$. Every other finite set contains a unique marker and is hence TxtEx$^*$-learnable by $N_{m,e}$. Finally, if D is one of the active sets, then $D =^* \omega \setminus (C(0)\cup C(1))$. No initial segment of any enumeration of D contains either a marker in C(1) or the marker $\langle 0,\langle 0,3 \rangle \rangle$. Thus, $N_{m,e}$ again succeeds in TxtFex$^*_*$-learning the set. $\square$

Theorem 4.2

FEXL$^*_*$ and FEXTL$^*_*$ are both $\Sigma _5^0$-hard

Proof

We wish to reduce an arbitrary $\Sigma ^0_5$ predicate P(e) to FEXL$^*_*$ and FEXTL$^*_*$. For an arbitrary $\Sigma _4^0$ predicate Q(e), there is a $\Sigma _2^0$ predicate, R(e, x, y), such that the following representation can be made:

$$\begin{aligned} Q(e)&\leftrightarrow (\exists a) (\forall b) (R(e,a,b)) \\&\leftrightarrow (\exists \langle a,s\rangle ) [((\forall b) (R(e,a,b)))\wedge ((\forall a'<a) (\exists s'\le s) (\lnot R(e,a',s'))) \\&\wedge ((\exists a'<a) (\forall s'<s) (R(e,a',s')))] \\&\leftrightarrow (\exists ! \langle a,s\rangle ) [((\forall b) (R(e,a,b)))\wedge ((\forall a'<a) (\exists s'\le s) (\lnot R(e,a',s'))) \\&\wedge ((\exists a'<a) (\forall s'<s) (R(e,a',s')))]. \end{aligned}$$

Since the predicate

$$\begin{aligned}&((\forall b) (R(e,a,b)))\wedge ((\forall a'<a) (\exists s'\le s) (\lnot R(e,a',s')))\\&\quad \wedge ((\exists a'<a) (\forall s'<s) (R(e,a',s'))) \end{aligned}$$

is $\Pi ^0_3$, for a suitable computable function g,

$$\begin{aligned} Q(e) \rightarrow (\exists ! x) (g(e,x)\in \text{ COINF}) \end{aligned}$$

and

$$\begin{aligned} \lnot Q(e) \rightarrow (\forall x) (g(e,x)\in \text{ COF}). \end{aligned}$$

Applying the above to P(e), the arbitrary $\Sigma _5^0$ predicate under consideration, we may define a computable function f such that

$$\begin{aligned}&P(e)\rightarrow (\exists x) [ (\forall x'>x) (\forall y) (f(e,x',y)\in \text{ COF}) \\&\wedge (\forall x' \le x) (\exists ^{\le 1} y) (f(e,x',y)\in \text{ COINF}) ] \end{aligned}$$

and

$$\begin{aligned} \lnot P(e)\rightarrow (\forall x) [(\exists ! y) (f(e,x,y)\in \text{ COINF}) ]. \end{aligned}$$

We will now define a family ${\mathcal {G}}_e$ from e such that ${\mathcal {G}}_e$ will be learnable if and only if P(e). Define

$$\begin{aligned} {\mathcal {G}}_e = \bigcup _{x,y\in \omega } {\mathcal {F}}_{x,f(e,x,y)}. \end{aligned}$$

Case 1: Suppose $\lnot P(e)$. Then for every x, there is a y for which $f(e,x,y)\in \text{ COINF }$. From this we conclude that for each computable learner, M coded by m, there is a y such that $f(e,m,y)\in \text{ COINF }$. ${\mathcal {G}}_e$ contains a subfamily, ${\mathcal {F}}_{m,f(e,m,y)}$, that M cannot TxtFex$^*_*$-learn. Thus, ${\mathcal {G}}_e$ is not TxtBC-learnable.

Case 2: Suppose P(e) and let $x_0$ be such that $(\forall x\ge x_0) (\forall y) (f(e,x,y)\in \text{ COF})$. Let $a_0, a_1,\ldots , a_k$ enumerate the numbers less than $x_0$ such that, for unique corresponding $b_0, b_1,\ldots , b_k$, we have $f(e,a_i,b_i)\in \text{ COINF }$ and let $K_i$ be a computable machine that learns ${\mathcal {F}}_{a_i,f(e,a_,b_i)}$. The existence of such a machine is guaranteed by Lemma . Using the machine N from the proof of Lemma , define a computable machine M on input string $\sigma$ by

$$\begin{aligned} M(\sigma ) = {\left\{ \begin{array}{ll} K_i(\sigma ) &{} \text{ if } \langle 1,\langle 0,a_i\rangle \rangle , \langle 1,\langle 1,b_i\rangle \rangle \in \text{ content }(\sigma ) \text{ for } i\le k, \\ N(\sigma ) &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

If an enumeration of a set in the subfamily ${\mathcal {F}}_{a_i,f(e,a_i,b_i)}$ is fed to M, then eventually a tag in the $1^{st}$-column will appear identifying it as such. Cofinitely often, the appropriate $K_i$ will be used to learn the enumeration. If the enumeration is for a set from ${\mathcal {F}}_{x,f(e,x,y)}$ with either $x\not = a_i$ or $y\not = b_i$ for any $i\le k$, then N will be used. From Lemma , it is known that N is capable of TxtFext$^*_*$-learning ${\mathcal {F}}_{x,f(x,y)}$ for any x provided that $y\in \text{ COF }$.

We conclude that both FEXL$^*_*$ and FEXTL$^*_*$ are $\Sigma _5^0$-hard. $\square$

Note that because the family described above is in fact TxtEx$^*$-learnable in the $\Sigma ^0_5$ case, meaning that this result has a result from [3] as a corollary.

5 Conclusion

With these results, the arithmetic complexity of the core models of vacillatory learning have been established.

The effort to classify the arithmetic complexity of learning criteria was initiated by the first author as an attempt to distinguish TxtFex$^*_*$ and TxtFext$^*_*$, a problem the first author answered in [2]. As is clear from these results, although the two learning models are distinct, their complexities do not distinguish them.