  This paper contributes to the study of CPAC learnability -- a computable
version of PAC learning -- by solving three open questions from recent papers.
Firstly, we prove that every improperly CPAC learnable class is contained in a
class which is properly CPAC learnable with polynomial sample complexity. This
confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that
there exists a decidable class of hypothesis which is properly CPAC learnable,
but only with uncomputably fast growing sample complexity. This solves a
question from Sterkenburg (COLT 2022). Finally, we construct a decidable class
of finite Littlestone dimension which is not improperly CPAC learnable,
strengthening a recent result of Sterkenburg (2022) and answering a question
posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our
results provide a complete landscape for the learnability problem in the CPAC
setting.
