Kurt Gödel, Alan Turing, and the Limits of AI Intelligence
Infinities, impossibilities, and the man in the white linen suit
I explore how Kurt Gödel proved mathematics cannot fully explain itself, while Alan Turing showed no machine can predict all program behaviors. These foundational limits challenge today's AI boom, which often assumes intelligence is merely a scaling problem. From Gödel's tragic end to the theoretical blueprint of modern computers, I trace why rule-based systems will always have blind spots.
The greatest logician since Aristotle, a man who had proved that mathematics itself contained truths it could never reach, was killed by a distorted inner logic he could not escape.
- jsrozner
Has anyone here actually looked at the Shai Ben David (SBD) result? I did a final grad project on it recently for a class on incompleteness. In my view it's not really that interesting. For learnability to be undecidable, the cardinality of the continuum (size of the reals) must exceed \aleph_k for all finite k. ZFC does not bear upon this (CH is independent of ZFC), so this is a possible setting of the world, and therefore learnability can be undecidable.
But say the size of the continuum is, e.g., \aleph_3, (in this case CH is false, but it's not "horribly false"), then SBD shows how to build a compression scheme, and thus their EMX -- estimating the maximum problem -- is "learnable". But the compression scheme whose existence they show (it's just a function whose existence they prove) can't actually be encoded, since it requires identifying a maximal element by invoking the well-ordering theorem. So there's no algorithm that enables solving the problem (though a function solving the problem exists).
This result, without further work, does not immediately say anything about the sorts of problems for which abstractions can be learned. And abstraction is at the heart of understanding and problem solving.
See e.g., https://arxiv.org/pdf/1909.08410 (§5)
- azakai
The overall point feels strained to me.
Yes, formal mathematics has such limits. We can't expect machines to be perfect and provably perfect. But the industry isn't assuming that. Why would it? Natural intelligence is not perfect or provably perfect, either.
Rather than certainty, measurement is often enough. We can't prove a program will always halt, but we can check it halts in a specific execution.
Approximation is also often all we need. Even if we can't prove that we can train a network with more than 50% success, if we can get multiple shots at that (using different data, or initial random weights, or training techniques, or something else), then we can reduce that danger exponentially. (I don't know that we have a guarantee of succeeding there, but this would be the hope, and I am not aware of anything showing it is impossible, unlike perfect provability.)
Finally, it is possible that perfect provability does work on the problems we care about. Godel and Turing etc.'s proofs rely on finding rare situations where we can't prove things - cleverly-constructed pathological cases - but perhaps human behavior does not fall into that set. Human behavior may not be a pathological case for proofs or learnability.
- zeitgeistcowboy
Yes, but does a computer system or tool or AI need to be provably correct or 100% guaranteed not to cause harm to be useful? Alternative methods (human, simple rules) aren’t either. Perfect can be the enemy of good enough. Just being pragmatic here.
- skippyfish
Aside from seemingly being 100% AI-generated, this article makes a really spurious use of Godel's argument, which I think is best exemplified by the following passage near the end:
"These four threads share a common ancestor in what Gödel proved in 1931, and Turing sharpened in 1936. Rule-based systems cannot fully account for themselves. A system cannot certify its own trustworthiness. A learning framework cannot determine its own boundaries. A safety strategy cannot verify its own completeness.
None of this is softened by the fact that a neural network feels organic rather than rule-like. A model’s weights are numbers, and its training is arithmetic, all of it running on von Neumann’s realisation of Turing’s imaginary device. AI is not adjacent to this mathematics. AI is made of it.
The AI industry, understandably, would rather not dwell on this. "
This is a complete non-sequitur. Godel's argument isn't even that profound: it just says that a system of axioms good enough to embed standard natural number arithmetic must be independent of a certain constructed sentence, i.e., it will run the same whether that sentence is true or false and you can't tell from its axioms which of these two options is in effect. While that sucks for philosophers, it doesn't make mathematics less useful, less dependable, or less correct in a practical sense. It has no practical implications to anything that the AI industry is promising today.
- jibal
Turing proved that no TM can determine whether all TMs halt ... not that no TM can determine whether some specific TM halts ... the difference a common misunderstanding of the proof. Analogously, while we can't prove that no AI is or isn't harmful, we can prove that certain AIs are or aren't harmful.