We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Sta- tistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Funda- mental Theorem in the computable setting, for instance by introducing an effective VC-dimension. In this work, we investigate the relationship between CPAC learning and recursively enumerable representable (RER) classes, hypothesis classes whose members can be algorithmically listed, in the context of the Fundamental Theorem. We demonstrate that the RER property is deeply con- nected to CPAC learning by characterizing several notions of CPAC learnability via the existence of certain RER classes realizing the same samples. We further establish that the RER property alone is sufficient to guarantee nonuniform CPAC learnability and give a sufficient condition for CPAC learnable classes to be RER. Other results show that the effective VC-dimension can take arbitrary values above the traditional one and we note that the two dimensions coincide given the existence of a computable empirical risk minimizer. This recovers classical PAC bounds for most practically relevant classes and establishes a family of examples separating several notions of learnability.

We develop a first-order theory of ordered transexponential fields in the language { + , ⋅ , 0 , 1 , < , e , T } , where e and T stand for unary function symbols. While the archimedean models of this theory are readily described, the study of the non-archimedean models leads to a systematic examination of the induced structure on the residue field and the value group under the natural valuation. We establish necessary and sufficient conditions on the value group of an ordered exponential field ( K , e ) to admit a transexponential function T compatible with e . Moreover, we give a full characterisation of all countable ordered transexponential fields in terms of their valuation theoretic invariants.

Abstract Given a Henselian valuation, we study its definability (with and without parameters) by examining conditions on the value group. We show that any Henselian valuation whose value group is not closed in its divisible hull is definable in the language of rings, using one parameter. Thereby we strengthen known definability results. Moreover, we show that in this case, one parameter is optimal in the sense that one cannot obtain definability without parameters. To this end, we present a construction method for a t-Henselian non-Henselian ordered field elementarily equivalent to a Henselian field with a specified value group.