During the twentieth century, discoveries in mathematical logic revolutionized our understanding of the very foundations of mathematics. In 1931, the logician Kurt G\u00f6del showed that, in any system of axioms that is expressive enough to model arithmetic, some true statements will be unprovable1<\/a><\/sup>. And in the following decades, it was demonstrated that the continuum hypothesis \u2014 which states that no set of distinct objects has a size larger than that of the integers but smaller than that of the real numbers \u2014 can be neither proved nor refuted using the standard axioms of mathematics2<\/a><\/sup>\u2013<\/sup>4<\/a><\/sup>. Writing in\u00a0Nature Machine Intelligence<\/i>,\u00a0Ben-David\u00a0et al.<\/i><\/a>5<\/a><\/sup>\u00a0show that the field of machine learning, although seemingly distant from mathematical logic, shares this limitation. They identify a machine-learning problem whose fate depends on the continuum hypothesis, leaving its resolution forever beyond reach.<\/p>\n Machine learning is concerned with the design and analysis of algorithms that can learn and improve their performance as they are exposed to data. The power of this idea is illustrated by the following example: although it seems hopelessly difficult to explicitly program a computer to determine what objects are in a picture, the Viola\u2013Jones machine-learning system can detect human faces in real time after being trained on a labelled sample of photographs6<\/a><\/sup>. Today, we regularly interact with machine-learning algorithms, from virtual assistants on our phones to spam filters for our e-mail. But these modern real-world applications trace their origins to a subfield of machine learning that is concerned with the careful formalization and mathematical analysis of various machine-learning settings.<\/p>\n The goal of learning a predictor (a mathematical function that can be used to make predictions) from a database of random examples was formalized in the aptly named probably approximately correct (PAC) learning model7<\/a><\/sup>. In this model, the aim is to train the predictor to match some true function that labels the data. A different model, called online learning, has the learner making immediate predictions as data arrive \u2014 for example, capturing a trading system\u2019s task of executing transactions in an ever-changing market. And another model known as multi-armed bandits can simulate clinical trials, in which the medical outcomes that an experimenter observes depend on his or her own choices.<\/p>\n These are only a few examples of the many models used in machine learning. In each case, the basic goal is to perform as well, or nearly as well, as the best predictor in a family of functions, such as neural networks or decision trees. For a given model and function family, if this goal can be achieved under some reasonable constraints, the family is said to be learnable in the model.<\/p>\n Machine-learning theorists are typically able to transform questions about the learnability of a particular function family into problems that involve analysing various notions of dimension that measure some aspect of the family\u2019s complexity. For example, the appropriate notion for analysing PAC learning is known as the Vapnik\u2013Chervonenkis (VC) dimension8<\/a><\/sup>, and, in general, results relating learnability to complexity are sometimes referred to as Occam\u2019s-razor theorems9<\/a><\/sup>. These notions of dimension happen to be simple enough to leave no room for the spectre of unprovability to manifest itself. But Ben-David and colleagues show that machine learning cannot always escape this fate. They introduce a learning model called estimating the maximum (EMX), and go on to discover a family of functions whose learnability in EMX is unprovable in standard mathematics.<\/p>\n Ben-David\u00a0et al.<\/i>\u00a0describe an example EMX problem: targeting advertisements at the most frequent visitors to a website when it is not known in advance which visitors will visit the site. The authors formalize EMX as a question about a learner\u2019s ability to find a function, from a given family, whose expected value over a target distribution is as large as possible. EMX is actually quite similar to the PAC model, but the slightly different learning criterion surprisingly connects it to the continuum hypothesis and brings unprovability into the picture.<\/p>\n