The uncomputable-hypothesis conjecture for CPAC learning
Let H\mathcal{H}H be a hypothesis class, and let eVCdim(H)\operatorname{eVCdim}(\mathcal{H})eVCdim(H) denote its effective VC-dimension. A hypothesis in H\mathcal{H}H is uncomputable if it is not…