  The present work explores the theoretical limits of Machine Learning (ML)
within the framework of Kolmogorov's theory of Algorithmic Probability, which
clarifies the notion of entropy as Expected Kolmogorov Complexity and
formalizes other fundamental concepts such as Occam's razor via Levin's
Universal Distribution. As a fundamental application, we develop Maximum
Entropy methods that allow us to derive the Erd\H{o}s--Kac Law and
Hardy--Ramanujan theorem in Probabilistic Number Theory, and establish the
impossibility of discovering a formula for primes using Machine Learning via
the Prime Coding Theorem.

Computational Complexity