二十世紀，數學邏輯的發現徹底改變了我們對數學基礎的理解。1931年，邏輯學家哥德爾（ Kurt Gdel）證明，在可比擬算術的公理系統中，一些陳述是不可證偽的。這就是著名的哥德爾不完備性定理。
隨後的幾十年中，連續統假說——即不存在大於整數而小於實數的集合——被證實在標準公理體系中是不完備的，它既不能被證明，也不能被證偽。
機器學習領域，似乎遠離數理邏輯，但最近本-大衛（Ben-David）等人發現了一個機器學習中的問題，它與連續統假說等價，表明機器學習中也存在不可證偽的算法。
對機器學習的暢想，源自這樣的事實：2001年，Viola和Jones在AdaBoost算法的基礎上，使用Haar-like小波特徵和積分圖方法進行人臉檢測，發現在經過照片樣本訓練之後，機器系統可以實時地檢測人的面孔。這可以說是機器學習史上的裡程碑。
本-大衛等人描述一個估計最大值(EMX)問題：在事先不知道哪些訪客會訪問該網站的情況下，投放以網站最頻繁的訪客為目標的廣告。作者將EMX正規化為一個關於學習者從給定的函數族中尋找特定函數的問題，該函數族對目標分布的期望值儘可能大。EMX模型實際上與PAC模型（Probably Approximately Correct）)非常相似，但稍微不同的學習標準將它與連續統假設聯繫在一起。
作者證明機器學習和數據壓縮之間有一個漂亮的關聯：如果由某個函數族標記的樣本總是能被壓縮，那麼這個函數族在某種意義上必須是低複雜度的，因此是可學習的。單調壓縮是壓縮的一種變體，它適用於描述EMX中特定函數族的可學習性。對於0到1之間的實數構成的集合，其有限子集具有單調壓縮格式，因此在EMX中是可學習的，但前提是若且唯若連續統假設是正確的，而眾所周知，這是一個不可證明的命題。
EMX是機器學習中的一個新模型，我們還不知道它在開發真實世界算法中的作用。因此，這些結果可能沒有實際意義。機器學習作為一門數學學科已經成熟，也許這樣的結果會給機器學習領域帶來新的機遇。