{'fraction_non_alphanumeric': 0.037416685819351876, 'fraction_numerical': 0.009515054010572283, 'mean_word_length': 4.403750620963736, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Undecidability of Learnability

Machine learning researchers and practitioners steadily enlarge the multitude of successful learning models. They achieve this through in-depth theoretical analyses and experiential heuristics. However, there is no known general-purpose procedure for rigorously evaluating whether newly proposed models indeed successfully learn from data. We show that such a procedure cannot exist. For PAC binary classification, uniform and universal online learning, and exact learning through teacher-learner interactions, learnability is in general undecidable, both in the sense of independence of the axioms in a formal system and in the sense of uncomputability. Our proofs proceed via computable constructions of function classes that encode the consistency problem for formal systems and the halting problem for Turing machines into complexity measures that characterize learnability. Our work shows that undecidability appears in the theoretical foundations of machine learning: There is no one-size-fits-all algorithm for deciding whether a machine learning model can be successful. We cannot in general automatize the process of assessing new learning models.


Introduction
One of the foundational questions in machine learning theory is "When is learning possible?" This is the question for necessary and sufficient conditions for learnability. Such conditions have been identified for different learning models. They can take the form of requiring a certain, often combinatorial, complexity measure to be finite. Well known examples of such complexity measures include the VC-dimension for binary classification in the PAC model, the Littlestone dimension for online learning, or different notions of teaching dimensions for teacher-learner interactions.
We consider a question that is slightly different from, but arguably just as important as the one above. Namely, we ask "Can we decide whether learning is possible?" At first glance, the ability to answer the first question might also seem to allow to resolve this second one. If, e.g., you know a complexity measure whose finiteness is equivalent to learnability, that gives you a criterion to decide learnability. However, whether this is indeed a satisfactory criterion strongly depends on the exact meaning of "decide" in the second question.
We consider two such meanings and thereby obtain two variants of the second question. The first is natural from a mathematician's perspective, namely "If a class is learnable, can we prove that this is the case?" The second is intimately familiar to computer scientists, namely "Does there exist an algorithm that decides learnability?" After specifying in either of these two ways what it means to "decide whether learning is possible," we see that the answer to the second question is not trivially positiveEven given the definition of a complexity parameter that is finite if and only if learning is possible, answering the second question still requires a proof of finiteness of that complexity measure or an algorithm that decides whether the complexity measure is finite or not.
In fact, we show that the answer to the question "Can we decide whether learning is possible?" is, in general, negative for both of the variants introduced above and for different learning scenarios.
In particular, we demonstrate this for learning models in which criteria for learnability in terms of complexity measures are known. More concretely, we consider binary classification, uniform and universal online learning, and the task of exactly identifying a function through teacher-learner interactions. We show in all these scenarios: On the one hand, there is a function class that is learnable but whose learnability cannot be proved. On the other hand, there is no general-purpose algorithm that, upon input of a class, decides whether it is learnable.

Overview Over the Results
Our undecidability results come in two flavours, one about provability in a formal system, the other about computability via Turing machines. We summarize our line of reasoning in Figure 1 and explain it in more detail in the following paragraphs.
We first study binary classification in Probably Approximately Correct (PAC) learning. The relevant complexity measure for this learning scenario is the VC-dimension due to [VC71]. On the one hand, given a recursively enumerable formal system F , we define a class G F ⊆ {0, 1} N   Our constructions start from the recursively enumerable set c c ({0, 1}) of functions with compact support in N. Depending on the underlying object, i.e., the formal system or the Turing machine, we then further restrict the function class. We implement these restrictions based on consistency of finitely many provable theorems and halting after finitely many steps. Thereby, we ensure that they are computable from the underlying object (see Corollaries 2.14 and 2.19). For the Gödel  1.2 Related Work [Lat96] made an early investigation into the relationship between computability and learnability.
The main question in [Lat96] is whether and under which notions of "learnability" one can consider an uncomputable problem to be learnable. More precisely, [Lat96] considered the task of learning the halting problem relative to an oracle.
Both [Sch99] and [Zha18] studied the computability of finiteness of the VC-dimension. In particular, Theorem 1 in [Zha18] and Theorem 4.1 in [Sch99]  [Aga+20] initiated a study of computable learners, which then truly deserve to be called "learning algorithms." In particular, [Aga+20] showed that not every PAC learnable class admits a computable learner and also identified conditions under which PAC learnability implies copmutable PAC learnability. Thereby, [Aga+20] extended considerations from [Sol08], which studied the task of non-uniform learning over all computable functions by a computable learner. As the underlying questions of [Aga+20] and our work differ, the results are not comparable. However, as we show the function classes G F and H M to be computable, the results of [Aga+20] imply that our undecidability results hold not only for PAC learning, but also for computable PAC learning.
[SFM21] took yet another perspective on undecidabity in learning theory. Namely, [SFM21] considered the problem of deciding, given an algorithm A and a dataset d, whether A is a learning algorithm and the output model of A underfits d. Here, [SFM21] used an information-theoretic notion of underfitting. The main result of [SFM21]: This decision problem can be reduced to the halting problem and is thus Turing undecidable.
[Han+21] recently identified a further potential source of undecidability in learning theory. They studied the existence of universally Bayes consistent learners for countable multiclass classification, i.e., of learners whose classification error almost surely converges to the optimal Bayes risk (over all Borel measurable classifiers) as the sample size goes to infinity. Theorem 4.1 in [Han+21] states: A universally Bayes consistent classifier can only exist if the metric space from which the instances are drawn is essentially separable. The existence of metric spaces that are not essentially separable, however, is believed to be independent of the ZFC axioms. Hence, whether all metric instance spaces admit a universally Bayes consistent classifier might turn out to be a learning-theoretic question independent of ZFC.
Combinatorial complexity measures for learning have also been studied from in computational complexity theory. [PY96], motivated by [LMR91], determined the complexity of computing the VC-dimension of a finite concept class over a finite domain. While they argue that this problem is probably not NP-complete, [PY96] proved its completeness for the complexity class LOGNP, a logarithmically-restricted version of NP. [Shi93] obtained a similar completeness result. [FL98] then, by reduction to computing the VC-dimension, established the LOGNP-hardness of computing the Littlestone dimension. [Sch99] later showed that a variant of the above problem, namely that of computing the VC-dimension of a class described by a polynomial-sized circuit, is Σ p 3 -complete. Computing the Littlestone dimension from a circuit description is PSPACE-complete [Sch00]. Extending a result by [Sch99], [MU02] determined the complexity of a promise version of approximating the VC-dimension of a class associated to a polynomial-size circuit. More recently, [MR17] has proved nearly tight quasi-polynomial time lower bounds for approximating the VC-dimension and the Littlestone dimension, assuming the randomized Exponential Time Hypothesis.

Structure of the Paper
Section 2 contains our main constructions and results leading to undecidability of finiteness of the VC-dimension. In Section 3, we demonstrate that our constructions also yield undecidability results for teaching problems. In Section 4, we exhibit analogous results for both uniform and universal online learning. We conclude with an outlook and open questions in Section 5. Full proofs appear either directly in the text or in Appendix A. Appendices B and C contain standard definitions and results related to formal systems and computability that are used in the main text.
2 Undecidability of Finiteness of the VC-Dimension

Preliminaries: PAC Binary Classification and the VC-Dimension
We start by recalling one of the most influential learning models for binary classification: Definition 2.1 (Probably approximately correct binary classification [Val84]). Let X be some space, write Z = X × {0, 1}. Let G ⊂ {0, 1} X , and let D be a probability distribution on Z. A map A : ∞ m=1 Z m → {0, 1} X , S → h S , is a probably approximately correct (PAC) learner for G if there exists a function m : (0, 1) 2 → N ≥1 such that, given ε, δ ∈ (0, 1), if m ≥ m(ε, δ), then, with probability ≥ 1 − δ with respect to repeated sampling of S ∼ D m , it holds that The PAC learners of interest are polynomial PAC learners, for which the sample size m(ε, δ) can be chosen to depend polynomially on 1 /ε and log ( 1 /δ). Here, the "polynomial" refers to the sample size only, not to the runtime. If G admits a polynomial PAC learner, we call G PAC learnable.
For the scenario of binary classification, whether there exists a polynomial PAC learner can be understood in terms of a combinatorial quantity of the function class under consideration. If S ⊆ X is a set such that |G| S | = 2 |S| , we say that S is shattered by G.
Under suitable measurability assumptions on the function class G, we have the following Among the assumptions on G that guarantee the equivalence of Theorem 2.3 are that G be image admissible Suslin, universally separable, well behaved, or countable [Dud78; Pol84; Blu+89; Pes11]. The function classes considered in this paper are all countable, so Theorem 2.3 applies.
Therefore, when studying PAC learnability, we focus on studying finiteness of the VC-dimension.
Interestingly, [AW18] found the VC-dimension to characterize quantum PAC learnability in the same way. Therefore, our undecidability results carry over to quantum PAC learnability as well.

Gödel Undecidability
For the purpose of this subsection, let F denote a recursively enumerable formal system in which infinitely many different theorems can be proved. (See Definition B.3 for a definition of "recursively enumerable.") Let ϕ be a primitive recursive enumeration of the theorems provable in F . Here, we think of theorems being "different" in a symbolic way. I.e., two theorems are the same if and only if they are the exact same sequence of symbols from the alphabet available in F . This, in turn, is equivalent to the two theorems having the same Gödel number in a fixed Gödel numbering.
Also, we will denote by E 2 : N → N × N a primitive recursive enumeration of N 2 . I.e., E 2 is a total bijective function such that both component functions E 2 i : N → N, i = 1, 2, are primitive recursive and such that the inverse (E 2 ) −1 : N × N → N is primitive recursive. The existence of such an E 2 can, e.g., be proved using so-called pairing functions.
We begin by defining our main object of study for this subsection.
Definition 2.4. Let F , ϕ, E 2 be as above. For a compactly supported sequence a = (a(k)) k∈N ∈ c c ({0, 1}), define the function g a : , and the function class Here, the equality ϕ(E 2 1 (n)) = ¬ϕ(E 2 2 (n)) is to be understood as the symbolic equality between the theorem with Gödel number ϕ(E 2 1 (n)) and the negation of the theorem with Gödel number ϕ(E 2 2 (n)). Equivalently, we require equality of the corresponding Gödel numbers. We first observe that the class G F "collapses" to a single function, the zero function, if and only if the underlying formal system F is consistent.
Proof. This follows from the construction of the function class because E 2 1 and E 2 2 are surjective and the range of ϕ consists exactly of all Gödel numbers of theorems provable in F .
For later reference, we note a direct consequence of this observation.
We now make two more observations about the class G. The first concerns its VC-dimension for the case in which the underlying formal system is inconsistent. In that case, the restriction "ϕ(E 2 1 (n)) = ¬ϕ(E 2 2 (n))" is satisfied infinitely often and the VC-dimension of the function class G is infinite. This is the content of the following For the proof, we first recall that "anything can be deduced from a contradiction," sometimes also known as "ex falso quodlibet." Proposition 2.8. Let F be an inconsistent formal system. Let q be a theorem in F . Then both q and ¬q can be proved in F .

Proof. See Appendix A.
With this we can now prove Theorem 2.7.
Proof of Theorem 2.7. As F is inconsistent and infinitely many different theorems can be proved in F , by "ex falso quodlibet" there are infinitely many n ∈ N such that ϕ(E 2 1 (n)) = ¬ϕ(E 2 2 (n)), because E 2 1 and E 2 2 are surjective and the range of ϕ consists exactly of all Gödel numbers of theorems provable in F . Let N ∈ N. Then, by the above, there exist pairwise distinct n 1 , . . . , n N ∈ N such that If we now combine the statements of Corollary 2.6 and Theorem 2.7, we obtain the following Remark 2.10. There is a naïve way of constructing a function class that satisfies the same property as the one just established for G F . Namely, given F , we could efinẽ Whereas we can understand F → G F as a computable mapping (see Corollary 2.14), the same is not the case for F →G F . Hence, our procedure for constructing G F from F has a desirable property that the assignment F →G F would not guarantee.
If the formal system F is capable of expressing both the class G F and the finiteness of its VC-dimension, we can combine Corollary 2.9 with Gödel's second incompleteness theorem.
Corollary 2.11. Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic such that infinitely many different theorems can be proved in F .
Then VCdim(G F ) < ∞, but the finiteness of VCdim(G F ) cannot be proved in F .
Proof. Assume for contradiction that the statement VCdim(G F ) < ∞ can be proved in F . In Corollary 2.9, we have given a proof that this implies consistency of F . If this proof can be expressed in the formal system F , F proves its own consistency. This contradicts Gödel's second incompleteness theorem.
Now we come to the second relevant observation about the class G F : Not only is it a computable function class, but even the mapping F → G F is computable. We first prove the slightly weaker result that G F is a computable function class in the sense of Definition C.3: Theorem 2.12. Assume that F is a recursively enumerable formal system. Then the class G F is computable.
As a first step towards proving this result, we observe that the sequence space c c ({0, 1}) used for indexing the class can be recursively enumerated.
Lemma 2.13. There exists a primitive recursive function C : Proof. See Appendix A.
With this ingredient at hand, we can prove Theorem 2.12.
Proof of Theorem 2.12. According to Definition C.3, we want to find a total computable function It remains to show that G F is a total computable function. As C is total computable, even primitive recursive by Lemma 2.13, it suffices to show that the predicate ϕ(E 2 1 (n)) = ¬ϕ(E 2 2 (n)) is total computable.
To this end, recall that E 2 1 , E 2 2 and ϕ are primitive recursive. Thus, we only have to show that, given the Gödel numbers of two theorems, checking whether the theorem corresponding to the first number is the negation of the theorem corresponding to the second number can be done in a computable manner. This is even possible in a primitive recursive manner simply by how Gödel numbers are constructed.
Note that our proof of Theorem 2.12 even shows that G F is primitive recursive if we define a primitive recursive class of functions analogously to Definition C.3. The proof tells us more about the construction of G F with respect to computability. Not only is the function class G F computable for every formal system F . (This is also true forG F .) But we even see that the assignment F → G F is computable in the following sense: Corollary 2.14. There exists a partial computable function G : N 3 → N such that G F = {N ∋ n → G(ϕ, m, n) | m ∈ N} for any recursively enumerable formal system F whose theorems are enumerated by the primitive recursive function ϕ : N → N.
Proof sketch. As ϕ is primitive recursive, it is in particular computable. Thus, we can represent it via its code with respect to our universal Turing machine. With this code, we can compute the predicate ϕ(E 2 1 (n)) = ¬ϕ(E 2 2 (n)) and the Corollary is proved just like Theorem 2.12.
Here, the "partial" is only with respect to the first argument, G is total with respect to the second and third input. Together, Theorem 2.12 and Corollary 2.14 provide an advantage of our construction over the "trivial"G F in Remark 2.10. Given a recursively enumerable system in terms of an explicit primitive recursive enumeration ϕ of theorems, they provide us with an explicit algorithmic procedure for evaluating elements of the function class G F and thereby with an explicit description of G F obtained by fixing certain inputs of the concrete function G.

Turing Undecidability
We now change the perspective and ask whether there is a general-purpose algorithmic procedure for deciding whether a binary-valued function class has finite VC-dimension. We begin by describing what such a hypothetical algorithm should do: It would take as input the code of an arbitrary computable binary-valued function class G. It should output 0 if VCdim(G) is infinite and 1 if VCdim(G) is finite. Note that such an algorithm would decide finiteness of the VC-dimension "only" for computable function classes since it is exactly the computability which allows us to provide their code as input.
We show that such an algorithm does not exist by reduction to the halting problem. The   Proof. We have already seen in Lemma 2.13 that there exists a primitive recursive function C :  is Gödel undecidable in F and thus gives a result comparable to Corollary 2.11. We have presented our results on independence of the axioms of a formal system and on uncomputability separately, so that these parts of the paper can be read independently from one another.

Undecidability in Teaching Problems
In this section, we demonstrate that the function classes constructed in Section 2 are useful beyond the scenario of PAC binary classification, namely also for teaching problems.

Preliminaries: Teaching Problems and the Teaching Dimension
We now turn our attention to a different learning problem. The differences to the PAC model are two-fold. The source of the training data is now a benevolent teacher who knows the function to be learned. And, instead of requiring the learner to approximate the unknown function with high probability, the unknown function must be exactly identified. To help the learner identify the target function, the teacher has to provide a training data set that uniquely characterizes it. The difficulty of the learning/teaching problem is then captured by the worst case size of a smallest such training data set. This is made formal in the following Definition 3.1 (Teaching sets and the teaching dimension [GK95]).
, is a teaching set for g in G if g(x i ) = y i for all (x i , y i ) ∈ S and for everyg ∈ G \ {g} there exists (x j , y j ) ∈ S such thatg(x j ) = y j . I.e., g is the unique concept in G that is consistent with the labelled data S.
The teaching dimension of G is the worst case size of a minimal teaching set, i.e., Tdim(G) := sup g∈G inf{|S| | S is a teaching set for g}.
We consider a learning/teaching problem for a class G to be solvable if Tdim(G) < ∞. Note that we will use this notion specifically for X = N. This is non-standard. Usually, X is assumed to be finite so that the teaching dimension is automatically finite.
If the teacher and the learner are allowed to make additional assumptions about the respectively other party's strategy, more refined notions of teaching dimensions should be used (see [Zil+11] for an overview). We, however, restrict our attention to the simplest complexity measure for teaching tasks, namely the one in Definition 3.1.

Gödel Undecidability of the Existence of Finite Teaching Sets
Before coming to the teaching dimension itself, we discuss a different problem in teaching. Namely, we ask whether, given a function that can be taught to a learner by a teacher using finitely many examples, we can always prove that this is the case. The answer will turn out to be no, in general.
For this and the next subsection, we take F and ϕ as in Subsection 2.2. We consider the class of threshold functions on N and allow for the possibility of a "threshold at infinity." I.e., we consider where we use the convention sgn( Note that F step consists of computable functions and is a computable class in the sense introduced in Definition C.3.
We consider the function Here, ϕ(1), . . . , ϕ(n) are said to be inconsistent if and only if for some 1 ≤ i, j ≤ n we have ϕ(i) = ¬ϕ(j), and consistent otherwise.
Note that the mapping F → f F , where we think of F as given via the code of the corresponding ϕ, is computable. Clearly, f F ∈ F step for any formal system F . Therefore we can study whether f F admits a finite teaching set in the class F step .
Proposition 3.2. f F admits a finite teaching set in F step iff F is inconsistent.
Proof. If F is inconsistent, then there exists k ∈ N such that f F (n) = sgn(n − k) for all n ∈ N.
So f F is the only element of F step that is consistent with the training data set {(k − 1, 0), (k, 1)}.
Thus, we have found a teaching set of size 2 for f F .
If F is consistent, then f F ≡ 0 is the zero-function. So any finite training data set consistent But also the function N ∋ n → sgn(n − k * ) with k * = max 1≤i≤N n i + 1 is an element of F step that is consistent with such a training data set. So f F cannot be uniquely identified in F step by a finite training data set. I.e., f F does not have a teaching set of finite size.
We see that the teaching dimension of F step is infinite. The formal system determines which element of F step we consider and Proposition 3.2 states that, if F is consistent, this "filters out" precisely the one concept in F step that does not have a finite teaching set.
If F is capable of expressing the function f F , the class F step , and the (non-)existence of finite teaching sets, we are again in the position to apply Gödel's second incompleteness theorem.
Corollary 3.3. Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic. The function f F defined above does not have a finite teaching set in F step , but this statement is not provable in F .

Gödel Undecidability of Finiteness of the Teaching Dimension
Next, we study G F from the perspective of the teaching dimension. For the purpose of this discussion, F , ϕ and E 2 are again as in Subsection 2.2. Our first observation is that also finiteness of the teaching dimension of G F can be related to consistency of underlying formal system.
Proof. The proof is similar to that of Corollary 2.9. See Appendix A for details.
The proof of Proposition 3.5 shows that, if F is inconsistent, then in fact no element of G F has a finite teaching set. This is different from our result of the previous subsection, where a single function in F step required teaching sets of infinite size and whether this function was the one characterized by F depended on (in-)consistency.
Again, if F can reason about G F and the finiteness of its teaching dimension, we can combine Proposition 3.5 with Gödel's second incompleteness theorem: Corollary 3.6. Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic. Then G F has finite teaching dimension, but this statement cannot be proved in F .
Thus, we have shown that also the teaching dimension captures the contrast between the "collapse" of G F in the consistent case and the "richness" of G F in the inconsistent case. Therefore, finiteness of the teaching dimension is also Gödel undecidable.
Remark 3.7. If we leave aside questions of computability, we could also consider the following construction: TakeF

Turing Undecidability of Finiteness of the Teaching Dimension
We can also view H M through the lens of teacher-learner interactions. As before, the first step in our approach consists in relating whether the underlying Turing machine M halts to whether the teaching dimension of H M is finite. Proof. This follows from the equality H M =H M (Remark 2.17). See Appendix A for details.
As we already know from Corollary 2.19 that H M can be computed from the underlying Turing machine M , we can again reduce to the halting problem and obtain Corollary 3.9. There is no Turing machine that, upon input of the code of an arbitrary computable binary-valued function class, decides whether that class has finite teaching dimension. In other words, finiteness of the teaching dimension is Turing undecidable.

Undecidability in Online Learning Problems
As a final demonstration of the applicability of our constructions to different learning models, we show that universal and uniform online learning are undecidable in the by now familiar two senses.

Preliminaries: Online Learning and Littelstone Trees and Dimension
In online learning, we consider a game between two players, a learner L and an adversary A, both of which know the function class G ⊆ {0, 1} X . The game consists of infinitely many rounds. Round t ∈ N ≥ 1 consists of three steps: First, A chooses a "question" x t ∈ X . Second, L guesses a label y t ∈ {0, 1}. Third, A reveals the true label y t ∈ {0, 1} to L. Crucially, A must ensure that the sequence of true labels can actually be realized within G. I.e., the produced sequence ((x t , y t )) ∞ t=1 must be such that, for every t ∈ N ≥1 , there exists a function g ∈ G with g(x s ) = y s for all 1 ≤ s ≤ t.
Note: A does not have to pick a fixed g ∈ G in advance. Instead A can choose the true labels adaptively, based on the actions of L and A in previous rounds.
The goal of L is to make as few mistakes as possible, where we say that L makes a mistake in round t ∈ N ≥1 ifŷ t = y t . Conversely, A wants to make the number of mistakes made by L as large as possible. Note that, while we can also interpret teaching problems as two-player games, the role of the second player is quite different. A teacher is seen as benevolent and has the same goal as the learner. In contrast, an adversary's goal is exactly opposite to that of the learner.
We consider two variants of the online learning problem. On the one hand, we work in the scenario of universal online learning, recently introduced in [Bou+20]. We say that G ⊆ {0, 1} X is universally online learnable if there exists an adaptive strategyŷ t =ŷ t (x 1 , y 1 , . . . , x t−1 , y t−1 , x t ) for L such that, for any adversary A, L makes only finitely many mistakes in the above game. On the other hand, we also formulate results in the uniform mistake bound model of online learning, which we refer to as uniform online learning. We say that G ⊆ {0, 1} X is uniformly online learnable if there exist a d ∈ N and an (adaptive) strategyŷ t =ŷ t (x 1 , y 1 , . . . , x t−1 , y t−1 , x t ) for L such that, for any adversary A, L makes at most d mistakes in the above game.
Both whether a class is universally or uniformly online learnable can be understood in terms of so-called Littlestone trees.
We say that G has an infinite Littlestone tree if there exists a Littlestone tree of depth ∞ of G.
A Littlestone tree of G is a complete binary tree in which the nodes are labelled by points in X and the edges are labelled by 0 or 1 in such a way that for every path of finite length, starting from the root of the tree, there is a function in G that labels all nodes along the path according to the respectively outgoing edges. Note that the definition is only concerned with finite paths, even for an infinite Littlestone tree.
The relation between universal online learnability and the (non-)existence of infinite Littlestone trees is summarized in the following Theorem 4.2 (Theorem 3.1 in [Bou+20]). G ⊆ {0, 1} X is universally online learnable iff G does not have an infinite Littlestone tree.
Going from "universal" to "uniform" on the level of Littlestone trees corresponds to requiring a uniform bound on the depth of all Littlestone trees of a class. This gives rise to

Gödel Undecidability of Finiteness of the Littlestone Dimension
We have seen in Theorem 4.4 that uniform online learnability is equivalent to the Littlestone dimension being finite. Therefore, we again start by relating consistency of the formal system F underlying G F to finiteness of the Littlestone dimension of G F . For both this subsection and for Subsection 4.4, we use the notation and classes introduced in Subsection 2.2.
Proof. This follows from our results on the VC-dimension and the inequality VCdim ≤ Ldim. See Appendix A for details.
The Gödel undecidability of uniform online learnability now follows as in Subsection 2.2: Corollary 4.6. Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic. Then G F has finite Littlestone dimension, but this statement cannot be proved in F .

Turing Undecidability of Finiteness of the Littlestone Dimension
This subsection as well as Subsection 4.5 use the notation and constructions from Subsection 2.3.

Gödel Undecidability of the Existence of Infinite Littlestone Trees
Because of Theorem 4.2, we first establish an equivalence between the formal system F underlying the class G F being consistent and G F having no infinite Littlestone tree.
Proposition 4.9. F is consistent iff G F does not have an infinite Littlestone tree.
Proof. The proof is similar to that of Corollary 2.9. See Appendix A.
With this observation, the same reasoning, using Gödel's second incompleteness theorem, as in Subsection 2.2 yields: Corollary 4.10. Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic. Then G F does not have an infinite Littlestone tree, but this statement cannot be proved in F .

Turing Undecidability of the Existence of Infinite Littlestone Trees
Analogously to the other scenarios, we want to connect the (non-)existence of infinite Littlestone trees for H M to whether or not M halts.

Conclusion
In this work, we have shown that in the standard model of binary classification, in two models of online learning, and in a basic model describing teacher-learner interactions, it is in general undecidable whether the learning task can be completed. We have established this for two different meanings of "undecidable," the first being "true, but not provable in a formal system" and the second being "not computable." In both cases, our results follow by providing computable constructions that allow for a reduction of the problem of deciding finiteness of the complexity measure for the respective learning task to the prototypic undecidable problem, i.e., to proving consistency of a formal system or to deciding whether a Turing machine halts.
It was already known, due to [Ben+19], that learnability can be independent of the axioms of ZFC. We have proved a similar-in-spirit result for the arguably most influential learning model, the PAC model of binary classification. By discussing our proof strategy also for a teacher-learner model and for online learning, we have demonstrated that it is not specific to the PAC setting.
Moreover, learnability can be undecidable also in other formal systems and in the terminology of computer science. A crucial feature of our constructions, especially for establishing undecidability in the latter sense, is that we are only dealing with computable objects. This is to be contrasted with [Ben+19], where the continuum is used. In particular, the arguments of [Ben+19] do not give uncomputability results. Note that, because our constructions are computable, instead of PAC learnability, equivalently we could have considered computable PAC learnability, because of Theorem 10 of [Aga+20], when restricting our attention to the realizable scenario.
We hope that our work adds to the ongoing research aiming towards a better understanding of the theoretical prospects and limits of machine learning. Our results indicate that potential problems for applications of machine learning do not only arise on the level of algorithmic design, which in itself is an extremely challenging task. Rather, already when faced with a task, we encounter a fundamental difficulty: It is in general not possible to decide whether that task is, from the information-theoretic perspective of sample complexity, leaving questions of computational complexity aside, learnable, i.e., in principle amenable to a solution via machine learning.
From a more practical perspective, our results can be interpreted as follows: When faced with a learning task, one can usually choose which hypothesis class to use. This choice will be guided by different considerations, such as prior knowledge about the problem, potential issues for optimization, and questions of learnability. In particular, one usually chooses a class that is known to be learnable. Thereby, the "library" of candidate function classes is restricted to those whose learnability has already been established. Our results say that there is no generic way of enlarging this library: Every time one faces a learning problem for which all classes from the current library perform poorly, identifying a new suitable candidate class, even leaving questions of optimization aside, presents a new challenge because of learnability alone.
Finally, we mention some questions raised by our work: • We have approached learnability through criteria based on complexity measures of the function class under consideration. Can (un-)decidability be established for learnability via algorithmic properties, e.g., stability or compression-based schemes?
• For our PAC learning scenario, we require a sample complexity bound that is uniform over the function class. Can our results be extended to non-uniform learning models in which the sample size is allowed to depend on the function to be learned, e.g., via some "weight parameter"?
• As discussed in Remark 2.22, it would be interesting to see whether the finiteness of the VC-, teaching or Littlestone dimension remains undecidable also when restricting the potential inputs to codes of infinite function classes.
• As observed in [Bou+20], universal online learning is closely connected to Gale-Stewart games. Do undecidability results in one of these two scenarios translate to the respectively other one?
For example, can we recover the undecidability results for Gale-Stewart games due to [Rab58] and [Jon82] from our results in Section 4? Or can we these works to gain further insight into undecidability in online learning?
If F is inconsistent, then, as we have seen in the proof of Theorem 2.7, there exists a sequence (n k ) ∞ k=1 ⊂ N such that {n 1 , . . . , n N } is shattered by G F for every N ∈ N ≥1 . Therefore, we obtain an infinite Littlestone tree of H M by labelling every node in the k th layer by n k+1 , for k ∈ N 0 .
Proof of Proposition 4.11. If M halts on the empty input, then Ldim(H M ) < ∞ by Proposition 4.7. In particular, H M does not have an infinite Littlestone tree.
If M does not halt on the empty input, then {0, . . . , N } is shattered by H M for every N ∈ N, as we have seen in the proof of Lemma 2.16. Therefore, we obtain an infinite Littlestone tree of H M by labelling every node in the k th layer by k, for k ∈ N 0 .

B Gödel and Incompleteness of Formal Systems
Here, we compile standard notions connected to formal systems which appear in the main body of the paper. However, some notions will only be introduced informally and the interested reader is referred to other sources for the formal definitions.
We denote by N the natural numbers including 0. We call a function f : N k → N primitive recursive if it can be built from the zero function, the successor function, and the coordinate projection functions via composition and primitive recursion. From a modern perspective, the primitive recursive functions are those that can be implemented using basic arithmetic as well as IF THEN ELSE, AND, OR, NOT, =, >, and FOR loops. WHILE loops are not allowed here.
Next, we recall, albeit only informally, the notion of a formal system. Definition B.1 (Formal systems -Informal). A formal system F consists of a finite alphabet of symbols, a language of statements that can be well-formed from the alphabet, a distinguished set of statements called axioms, and rules for how to derive/prove new theorems from these axioms.
A formal system F is called consistent if there is no well-formed statement such that both it and its negation can be proved in F . Otherwise, we call F inconsistent.
We will be interested in a particular kind of formal systems in which the provable theorems, i.e., the statements that can be deduced from the axioms according to the derivation rules, can be recursively enumerated. To make this assumption more rigorous, we first recall Definition B.2 (Gödel numbering -Informal). A Gödel numbering for a formal system F is an injective function that maps each symbol in the alphabet and each well-formed statement to an element of N.
For our purposes, it does not matter which Gödel numbering is used. We only use that Gödel numberings exist for which "translating" between a string of Gödel numbers of symbols describing a statement and the actual Gödel number of that statement can be done primitive recursively in both directions. Gödel's original construction has this property. From now on, we fix such a Gödel numbering. This allows us to identify statements in a formal system with elements of N and "manipulations" of statements with primitive recursive maps between natural numbers. Both of these identifications will sometimes be implicit throughout the paper.
From this perspective, we can describe the type of formal systems used in this work. Definition B.3 (Recursively enumerable formal systems). A formal system F is called recursively enumerable (or effectively axiomatized) if there exists a primitive recursive function ϕ : N → N such that {ϕ(n) | n ∈ N} is exactly the set of all Gödel numbers in a fixed Gödel numbering of statements that can be proved in F .
Given such a primitive recursive enumeration ϕ of provable theorems, we will sometimes abuse notation and take ϕ(n) to denote both a theorem and its Gödel number. The exact meaning, if not made explicit, will be clear from the context.
Gödel's second incompleteness theorem provides, for any recursively enumerable and consistent formal system that contains elementary arithmetic, an explicit statement that is true but cannot be proved in that formal system. Theorem B.4 (Gödel's second incompleteness theorem [Göd31]). Assume that F is a recursively enumerable and consistent formal system that contains elementary arithmetic. Then the consistency of F is not provable in F .
We call a statement that is true but not provable in a formal system F Gödel undecidable in F . This is not standard terminology, we merely use it to shorten some formulations.
For a more formal presentation of these and other notions from mathematical logic, the reader is referred to textbooks such as [Bar93; Kle02; End13].

C Turing and Uncomputability
This section recalls standard definitions and results related to Turing machines and computability.
Again, sometimes we give only an informal presentation and refer to textbooks for details.
In [Tur37], Turing introduced what are now known as a Turing machines. We do not give a formal definition, but instead describe the workings of a Turing machine informally. For a more rigorous presentation, see, e.g., [Dav82;Soa16].
Definition C.1 (Turing machines -Informal). A Turing machine M consists of • a 1-dimensional tape with infinitely many cells extending in both directions, each of which contains a symbol from a finite alphabet Σ, • a head that can read and write symbols in a single cell and move to the left or to the right by one cell, • a finite set of states Q containing an initial state and a halting state, • and an instruction function I : Σ × Q → Σ × {L, R} × Q describing the write-, move-and state-update-behaviour of M upon reading a given symbol while in a given state.
The two distinguished states are the initial state, in which the Turing machine begins any of its computations, and the halting state, that causes the Turing machine to halt when it is reached.
According to the Church-Turing thesis, which could be considered a "law of nature" for the world of computing, everything that can be reasonably considered computable is computable by a Turing machine. Hence, we take Turing machines as our model for defining computability. It is useful to note at this point that any primitive recursive function is computable. However, there are computable functions that are not primitive recursive.
We call a decision problem whose corresponding function, mapping instances of the problem to a binary "yes-or-no" output, is not computable Turing undecidable. The prototypic example of a Turing undecidable decision problem is the halting problem, i.e., the problem of deciding whether a given Turing machine halts on the empty input. Already [Tur37] observed that this cannot be achieved in a computable way.
We will also use a notion of computability of function classes.
Definition C.3. We say that a class G ⊆ N N is computable if there exists a total computable function G : N × N → N such that G = {n → G(m, n) | m ∈ N}.
We recall one last fact related to Turing machines. Namely, there exist universal Turing machines capable of simulating any Turing machine [Tur37]. From now on, for each k ∈ N ≥1 , we fix such a universal Turing machine understood as a partial computable function M : N k+1 → N. The natural number M is called the code of the Turing machine M with respect to M. This allows us to think of Turing machines, or, equivalently, computable functions, as input when representing them by their code with respect to our fixed universal Turing machine.