Per request, I cross post the question here which is original from math.stackexchange

In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting problem is learnable in a probabilistic learnability. So except halting problem, are there more undecidable cases which can be learned?

For example, the Chaitin's halting probability $\Omega$ is uncomputable, but if we gives enough many random sample programs and then wait for enough long time, and treat the non-stop program as not halting, we might be possible to approach the constant $\Omega$. And please check this question

And I think the above idea is similar to the idea in Richard Lathrop's paper.

Few people talk about this paper which seems to be important, because the conclusion makes us more clear on the relationship of computable and learnable. I am also curious about the reason.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.