Guerzhoy Challenges Claimed Proof That ML Cannot Achieve AGI

A 2024 paper by van Rooij et al. claimed to formally prove that achieving human-like intelligence through learning from data is intrinsically computationally intractable. If true, that would be a substantial result: a mathematical demonstration that machine learning cannot, in principle, produce AGI. A paper by Michael Guerzhoy, published in Computational Brain and Behavior, argues the proof does not hold.

The central problem Guerzhoy identifies is a distributional assumption embedded in the proof. According to the abstract, the original argument "relies on an unjustified assumption about the distribution of (input, output) tuples in the data." More precisely, the proof conflates two distinct roles for the same variable, one representing the actual distribution of situation-behavior data, the other standing in for an arbitrary efficiently-sampleable distribution. The most pointed illustration of the problem: the same proof structure, applied consistently, could be used to show that learning to classify images distributed as in the ImageNet dataset is intractable. Since ImageNet classification demonstrably works, something in the framework has gone wrong.

Beyond that specific flaw, Guerzhoy identifies structural barriers that would face any attempt to repair the proof. The first is definitional: "human-like" behavior would need a precise mathematical characterization, and none is provided. The second concerns inductive bias: any real machine learning system brings particular biases to a problem that are key to whether it is tractable, yet the original proof ignores them entirely. A third barrier emerges if one tries to fix the problem by restricting attention to subsets of the data; defining which subsets are relevant, without artificially constructing adversarial cases, turns out not to be straightforward.

The honest caveat is that none of this establishes AGI via machine learning is achievable, only that this particular impossibility argument fails. What the paper does not address is whether van Rooij et al. have responded, or whether a repaired proof could answer the barriers identified here.

For researchers tracking formal arguments about AI limits, the useful takeaway is about the constraints on worst-case complexity analysis: showing intractability over arbitrary distributions does not establish that the specific distributions real systems learn from are intractable, especially when those systems have inductive biases suited to the problem. Whether tighter impossibility results for AGI can ever be constructed within complexity theory remains genuinely open.