Barriers to Complexity-Theoretic Proofs that “AGI” Using Machine Learning is Impossible
2024/11/10 by Michael Guerzhoy, Guerzhoy, Michael · 7 voices
Computer Science · #Computability, Logic, AI Algorithms
paper · pdf · doi:10.1007/s42113-026-00284-w
Abstract
A recent paper (van Rooij et al. 2024) claims to have proved that achieving human-like intelligence using learning from data is intractable in a complexity-theoretic sense. We point out that the proof relies on an unjustified assumption about the distribution of (input, output) tuples in the data. We briefly discuss that assumption in the context of two fundamental barriers to repairing the proof: the need to precisely define ``human-like," and the need to account for the fact that a particular machine learning system will have particular inductive biases that are key to the analysis. Another attempt to repair the proof, by focusing on subsets of the data, faces barriers in terms of defining the subsets.
Discussions
- Your "theorem" and "proof" was almost _immediately_ critiqued with a formal rebuttal, which from what I can tell, you never responded to in a journal. You can start there, instead of acting like our c [bsky, 85 points, 1 comments]
- To appear in Computational Brain & Behavior soon: the claimed 2024 proof (also in CBB) that AGI via learning is intractable also "proves" that ImageNet is intractable. My reading of the hole: equivoca [bsky, 13 points, 0 comments]
- The examples the author uses are images and chess, for spaces that are large in theory but constrained in practice arxiv.org/pdf/2411.06498 [bsky, 5 points, 2 comments]
- Barriers to Complexity-Theoretic Proofs That "AGI" Using ML Is Impossible [hn, 4 points, 0 comments]
- Next time you see someone mention that shitty Van Rooj 2024 paper purporting to prove that AGI is intractable, point em at this. TLDR: by Van Rooj's reasoning: ImageNet is intractable. Reductio ad Abs [bsky, 2 points, 1 comments]
- Hi! Ready your paper, very interesting. Thought about it, and I'm not sure I find the computational complexity proof convincing because it bites only for learning all possible distributions D -- human [bsky, 0 points, 1 comments]
- Response to a paper from a while back that claimed "Yet, as we formally prove herein, creating systems with human(-like or -level) cognition is intrinsically computationally intractable."; from the re [bsky, 0 points, 0 comments]
Related