"Delle Rose et al. (COLT’23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one—which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information a bound on the numbers to be guessed. Interestingly, finite effective Littlestone dimension also guarantees that the class consists only of computable functions. Keywords: Online learning, Littlestone dimension, computable machine learning"

We revisit the problem of algorithmically deciding whether a given infinite connected graph has an Eulerian path, namely, a path that uses every edge exactly once. It has been recently observed that this problem is D0 3 -complete for graphs that have a computable description, whereas it is Π02-complete for graphs that have a highly computable description, and that this same bound holds for the class of automatic graphs. A closely related problem consists of determining the number of ends of a graph, namely, the maximum number of distinct infinite connected components the graph can be separated into after removing a finite set of edges. The complexity of this problem for highly computable graphs is known to be Π02-complete as well. The connection between these two problems lies in that only graphs with one or two ends can have Eulerian paths. In this paper we are interested in understanding the complexity of the infinite Eulerian path problem in the setting where the input graphs are known to have the right number of ends. We find that in this setting the problem becomes strictly easier, and that its exact difficulty varies according to whether the graphs have one or two ends, and to whether the Eulerian path we are looking for is one-way or bi-infinite. For example, we find that deciding existence of a bi-infinite Eulerian path for one-ended graphs is only Π0 1-complete if the graphs are highly computable, and that the same problem becomes decidable for automatic graphs. Our results are based on a detailed computability analysis of what we call the Separation Problem, whichwe believe to be of independent interest. For instance, as a side application, we observe that K¨onig’s infinity lemma, well known to be non-effective in general, becomes effective if we restrict to graphs with finitely many ends.

We study immunity properties of the transversals of computably enumerable equivalence relations (or, briefly, ceers ), where a transversal is a set which picks at most one element from every equivalence class of the given equivalence relation. Among transversals, a particular role is played by the principal transversal , whose members are the least elements of the various equivalence classes. While hyperimmunity of the principal transversal implies hyperimmunity of every infinite transversal, we show that this fails both for immunity and hyperhyperimmunity. In both cases, counterexamples are taken from the class of interval ceers , that is, ceers whose equivalence classes are either singletons or intervals of maximal length consisting of consecutive elements of some given c.e. set. We also look into the class of hyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperimmune, analyzing how this property relates to other computability theoretic properties of the infinite transversals. We make some preliminary observations on the hyperhyperdark ceers, that is, those ceers with infinitely many classes, whose infinite transversals are all hyperhyperimmune.