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)
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.
> The overall point feels strained to me.
It is. This happens to some people who discover undecidability is a thing. Then they get carried away and try to generalize to other areas. Branches of this line of thinking include the concept that intelligence must be analog with infinite precision, (this is the same line of thinking as the argument against digital audio) or intelligence must be "quantum". (Penrose).
The formal answer to the halting problem is that deterministic systems with finite memory must repeat a previous state or halt. Undecidability requires unbounded memory. Finite memory systems may have so many states and be so complex that decidability is computationally infeasible. But that's not impossibility. I used to get this objection when I was working on proof of correctness systems. We now know that some programs are hard to decide, but many useful ones are not.
If your program is anywhere near undecidable, it's probably broken. Microsoft's position with their Static Driver Verifier was that if 45 minutes of symbolic execution hadn't found a way out, you failed driver verification. This is one of those problems, like linear programming, where part of the problem space is really hard in a computational sense, but most of it isn't.
(I sometimes wonder if Penrose was on to something with his idea that the brain uses quantum effects in microtubules.[1] Penrose is a first-rate physicist. His philosophy is not as good. It's become clear that we can do artificial intelligence with acres of transistors and gigawatts of power, but the efficiency is terrible. We need either a more efficient algorithm or better hardware elements. LLM training now is like a Newcomen steam engine, where something the size of a house had the power output of a modern motorcycle engine.)
[1] https://en.wikipedia.org/wiki/Orchestrated_objective_reducti...
> We can't prove a program will always halt, but we can check it halts in a specific execution.
The computer scientist says “The halting problem cannot be solved, I have proven it” and the software engineer goes “30 second timeout, if the answer’s not ready by then we don’t need it”
I think this comparison is interesting because it shows the difference between theory & practice, but it's a little inaccurate. The halting problem being undecidable just implies there is no single universal algorithm that can tell you whether any program at all will halt. In practice we are working in specific domains and can come up with heuristics which are "good enough" for a specific codebase / module, like the timeouts you mention. So the halting problem can be solved for some subsets of programs but not all of them, and the computer scientist would hopefully have realized this instead of treating the codebase generically as "any program".
I don't understand the point at all. Mathematical theorems like godel's incompleteness theorem or the halting problem are applicable to everything including the human brain. If they were a limitation to developing general intelligence then human beings wouldn't have existed.
> Godel's incompleteness theorem or the halting problem are applicable to everything including the human brain.
Maybe. That's if you assume that the universe is a conventional computer. Far from settled and the alternative isn't necessarily just "God does it" - it might be that the universe is a "computer-plus", with some processes that produce results not computable by Turing means. It would be strange, but so is quantum mechanics, so...
This line of thinking doesn’t really go anywhere. You can say “but what if <something outside of an axiomatic system>? Then <axiomatic system> doesn’t apply!”
Well great. Then where are you? You are precisely nowhere. You haven’t disproved the results in the system and you haven’t proved anything else.
Yep, a possibility that has found support with Roger Penrose, who wrote two books about it.
As of yet we have no such evidence of physical systems that are more powerful than Turing machines. We will consider if ever such evidence arises.
Turing machines can't operate on arbitrary real-numbered values because they require infinite precision.
If the universe indeed uses real values, it's possible that it's more powerful than Turing machines.
The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers are non-computable (the set of computable numbers is countable, so it has the same "size" as the Naturals, while the Reals are not countable - so they are much larger).
However, this doesn't mean that TMs can't operate on such numbers. You can compute the fact that pi + pi = 2 * pi even if you can't enumerate all of pi's decimals.
That's why I added the word "arbitrary" :)
> However, this doesn't mean that TMs can't operate on such numbers.
Well, it kinda does. For example, you can't compute the sum of two arbitrary real values in a finite number of steps.
That being said, it's possible that the universe actually is not "running" on real numbers. This would also mean that our physics built on top of calculus is just an approximation.
This has always fascinated me. You can't really construct a meaningful amount of calculus without having real-valued variables. The intermediate value theorem depends on it, and it's one of the foundational parts.
I tried to construct something like "bounded error rational calculus", by trying to use rational ranges instead of real values and then constraining the range size. I was able to recover _some_ calculus, but I really have not studied it in enough details.
I find this topic of precision and of the computation that happens in the universe to be pretty interesting, but also very hard to pin down.
For example, let's take two arbitrary real numbers, call them x and y. They're almost certainly irrational uncomputable numbers, of course. Now, what is their sum? It's x + y, of course - I can tell you that without doing an infinity of computational work. Now, is this a useful representation? It very much depends on the use you have for it. For two unrelated uncomputable numbers, their sum is almost certainly uncomputable anyway, so there's not going to be any meaningful representation of it either. However, we can still derive useful properties about it, and use it in physical simulations as we need. For example, if both x and y are positive, I can tell you that x+y is greater than either of them, so I can also tell you that the electromagnetic force between two particles that are at distance x+y will be weaker than the force between two particles at distances of just x or just y.
So, what would it mean for the universe to "compute the exact value" of these two, or of their sum? What can physics do, assuming that some aspects are indeed continuous, that a simulation running on a TM actually can't?
Are they? Are there any actual Turing machines? Doesn’t that require infinite memory? I don’t know of a single thing which actually has that, nor one that comes close.
Not infinite memory, a Turing machine only requires "unbounded" memory, which is a way of saying that it will not run out of memory while running its program with the given input. In other words it just needs to have enough memory to run the program with whatever inputs it was given, which is much less than infinity. And this situation is quite common in the real world -- the programs I use on a daily basis have all the memory / RAM they need to do what I want (almost by definition). So in practice I might as well view them as Turing machines.
That just means even more limitations, then. (Though the grandparent comment is correct that literally everything is subject to the same Gödel-style limitation on its ability to make negative claims about its own behavior, whether computers, humans, or any other system at all.)
Finite machines such as FSMs (finite state machines) are a subset of TMs, so yes they are actual Turing Machines. What they aren't is UTMs ... universal Turing Machines that can emulate every TM.
The court system is the system built for dealing with this indeterminism in human affairs. The question is not whether imperfect systems are useful, or whether there are ways to construct a system to accommodate those imperfections - both of those have been answered again and again in human history (yes, and yes, with the same caveats as the first systems - turtles all the way down). The questions are how much effort does it take to reduce those imperfections to a level that renders the system a net improvement, what is the total cost of the system given those required efforts, and who pays the cost of the inevitable failures that still emerge from the system? As sits, the AI industry seems unwilling to put real effort into calculating the first, is certain the answer to the second is minimal, and is absolutely uninterested in being the answer to the third. The basic point here is, given that we know for a mathematical fact that the answer to the first is larger than we want it to be (that’s this whole article), how do we want to address the second and the third?
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.
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.
I think this is selling Gödel a little bit short. He proved for the first time that in any system of mathematics with enough complexity to be interesting, there are statements that cannot be proven true or false. The Gödel sentence might seem like a trivial example, but other examples of such things have been discovered since, such as the continuum hypothesis which the article mentions.
> enough complexity to be interesting
That's the loophole. There is mathematics without infinity.[1] Until recently, it was considered somewhat fringe. But there's been enough development that it's now clear you can do mathematics without infinity. In that view, infinities are a labor-saving device to get rid of special cases. They're not essential. Mathematicians used to hate special cases, but now that the active ones all grew up with computers, they're not so scared of IF statements.
You can have "arbitrarily large" but not "infinite". Boyer-Moore theory is like that. It starts out like Peano arithmetic. There is (ZERO) and (ADD1 (ZERO)) and (EQUALP A B) and (LESSP A B) as predicates. That's the axiomatic basis. Numbers are (ADD1 (ADD1 (ADD1 (ZERO)))), etc.
You can have recursive functions, but they must terminate. They must have a value which, for each recursion, is LESSP than the previous iteration. That's how you prove termination.
You can do most of mathematics that way. But not infinitesimals. You never can get to
1 + 1/2 + 1/4 + 1/8 ... = 2
[1] https://engtechnica.com/rethinking-mathematics-without-infin...
The article is massively overstating the implications of Godel to the AI industry, so to be clear - are you defending the article, or are we bikeshedding about my phrasing? Because my "not that profound" should be interpreted as relative to the article.
Ah that "with me or against me" dichotomy again.
> n any system of mathematics with enough complexity to be interesting, there are statements that cannot be proven true or false.
Note that the article itself is not as careful as you are here about correctly stating what Godel's Incompleteness Theorem actually says. The article states it this way: "any set of rules powerful enough to handle basic arithmetic will contain true statements it cannot prove". But that's wrong, because, when you take into account Godel's Completeness Theorem, you realize that, for any formal system complex enough for the proof of Godel's Incompleteness Theorem to go through, there must be a semantic model of that system in which the Godel sentence for that system is false! The article's misstatement is unfortunately very common, but it's still a misstatement.
Axiom systems feel like the ordinal numbers: you can keep building upwards as far as the eye can see, and even farther and you run out of useful reasons to do it long before you run out of axiom systems or numbers.
"One!" "Two!" "Three!" "Infinity!" "Infinity plus one!" "Infinity plus two!" "Infinity plus infinity!" "Infinity times infinity!" "Infinity to the power of infinity!" "Infinity to the power of infinity to the power of infinity!" "The supremum of all ordinals that can be expressed in a finite sequence of symbols!" "The supremum of all ordinals that can be expressed in a finite sequence of symbols plus one!"
I think you’re right about practicality. Seems like nonstandard models of arithmetic suggest that there are things we cannot know about all natural numbers, because some of them (nearly all of them) are “too high to work with.” They are too high when all you can do with them is write proofs about them using induction.
There’s a sense in which the set of natural numbers is too big to be practically useful, but no smaller set makes sense when writing proofs. The set of numbers you can reach without using induction (say, by using a computer to check) isn’t well-defined.
And that has nothing to do with AI’s limitations.
The worse confusion they seem to have is they think mathematical theorems are only applicable to "computers". Mathematical theorems have no escape, they apply just as much to human brains as to computers. If these theorems were a blocker for developing general intelligence then how do humans exist.
Gödel believed the human brain used non-mathematical reasoning (i.e. inexpressible with a Turing machine) to derive the axioms and thus could "see outside" of any particular axiom schema.
The Church-Turing thesis throws cold water on this: since the human body (including brain) is describable by a finite system of Schrödinger equations, and these equations can be solved numerically by a Turing machine, the human process of creating an axiom scheme should be Turing-computable. But some recent results on very large finite numbers (busy beaver) suggest there may be a subtlety here, e.g. complexity blows up to the point that it takes far more energy than the sun to simulate one human.
The more interesting subtlety: for a physically meaningful result you would need to define configuration space very carefully, e.g. not screwing up the boundary consitions or causal order of subsystems. Perhaps defining this is actually not computable, and after every delta(t) in a computer simulation, a human has to check the physics and redefine certain parameters of the system. Solving the Schrodinger equation numerically is certainly Turing-computable, but the process of ensuring that solution is physically meaningful isn't even slightly formalized. It may be unformalizable.
This is a fantastic article with lots of interesting questions raised between the halting problem and applications of AI.
The MRI example is very interesting - add a bit of noise and the crisp results fall apart. But we know we can carve out some determinism by orchestrating around LLM (validation loops) but they are only as good as the coverage of validation and the fidelity of expectations.
Which raises a fundamental question: where is the line between an effective harness and a broken one?
To put it in halting problem terms, if we have an outside program that checks the internal program for halting, we know we will capture some number of previously incatchable halting problems. How can we quantify this? We know there is a class of halts we can catch and prevent, but there will always be more complex ones that escape us.
In the real world, knowing the task is impossible doesn't impact the value of reducing the problem. More importantly, knowing which types of halting problems can be fully captured and which ones are intractable. Agent orchestration could directly benefit from layering a framework over this fuzzy space of knowableness.
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.
> The greatest logician since Aristotle
Not to diminish Gödel's work, but the greatest logician since Aristotle was clearly Gottlob Frege, the inventor of modern predicate logic.
You’re going to need to prove that one
One might gently recommend reading the "Political and social views" section on Frege's wikipedia entry before hitching your hot-take wagon to that particular horse.
> One might gently recommend reading the "Political and social views" section
This obviously changes absolutely nothing about his status as greatest logician since Aristotle.
By the way, he is also the person who could be, more appropriately than anyone else, called "father of analytic philosophy", since he strongly influenced Russel, Wittgenstein and Carnap, all themselves major figures of early analytic philosophy, and wrote influential analytic philosophy classics like "On Sense and Reference" more than 130 years ago.
Michael Dummett (who was, according to an obituary, "among the most significant British philosophers of the last century and a leading campaigner for racial tolerance and equality") marked Frege's 1884 book "The Foundations of Arithmetic" as the beginning of analytic philosophy.
"obviously" -- keep telling on yourself.
Why does him being a raging racist preclude him from being the greatest logician?
Given that the case for "greatest logician" can be made for at least a dozen candidates, picking the bigot is conspicuous - especially raised specifically in contrast to Gödel who literally had to flee the Nazis. "Show us your politics without telling."
Ah, well, could be. I don't know enough about logicians to argue.
This wall of slop is just a long, boring ad.
> We help companies make sense of technology and build lasting improvements to their operations.
Could it possibly be any more meaningless? I could help make sense of words and build lasting improvements to drivel.
Is it just me or does this article have a lot of LLM-isms?
I didn't pick up on it. I see this often: comments on HN remarking that something is AI generated, yet it's not obvious to me. Makes me worry that I am an LLM myself[1].
I've seen lot of bizarre, hard to understand or weirdly formulaic writing pre-2023, so I guess that's why I don't assume anything is AI generated.
[1] BTW, I am not.
Yes, it is very clearly AI written or substantially AI assisted. "Claude, write about Godel's incompleteness thms with respect to AI"
And it's annoying that comments like yours get downvoted. Maybe HN should have a "vote that this is undisclosed AI writing" button for every post now.
I wrote this partly because nobody seems to know about Gödel who is arguably a more important figure than Turing.
The piece follows four threads where formal limits show up in AI practice today: learnable problems that mathematics cannot sort, neural networks that exist but cannot be trained, self-improving systems that dropped their safety proofs for benchmark scores, and the fact that “will this AI cause harm” is, mathematically, an unanswerable question.
The piece is long and the math is dense. I’m curious whether people see the connection as tight or as overextended—whether Gödel’s structural limits actually do constrain what we’re doing now, or whether I’m collapsing categories that should stay separate.
This is a wild statement to me that “nobody seems to know about Gödel”… I think I learned about him when I was like 12? And while I’ve certainly met plenty of people who haven’t heard of him, until 10-15 years ago the same was true about Turing, mostly changed by a some Hollywood and/or literary references… and Gödel had a tiny bit of that in Oppenheimer if i recall, though not to the same degree? I bet if you asked 100 comp sci students if they’ve heard of Gödel at least 50 would say yes? On what basis do you think no one has heard of him? Not many have read the original math, sure, but… the idea that he was a mathematician who wrote an incompleteness theorem? VERY widely known.
I’m curious how much you used AI to write it, as it’s just chock full of Claude-isms.
This does read a little like AI, but I can't see many vocabulary based Claude-isms. But it does start with an anecdote, and there are other aspects of the writing which seem AI.
Gödel, Escher, Bach (1980, Pulitzer prize) was how I first got exposed to Gödel.
I think there is a loose connection. Hofstadter's 1979 masterpiece, Gödel Escher Bach (https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach --- mentioned in an earlier reply), has a chapter called Contracrostipuntus (https://genius.com/Douglas-hofstadter-contracrostipunctus-an...) which describes an arms-race tension between Crab's "perfect" record player and Tortoise's mischievous records designed to be unplayable on that record player, with titles such as "I Cannot Be Played on Record Player X". Crab's then invents a "Record Player Omega" which includes an ahead-of-time "scanning" step to reconfigure itself based on the record it scans...
All of which reminds me of virus-scanning on computers, and AI efforts for "safety".
Making the connection between GEB and AI isn't new, apparently: https://matthodges.com/posts/2025-08-26-music-to-break-model...
If the theorem is truly general ie any algorithm not just certain classes of neural net training methods, then is a moot point. Computers, humans or any other physical system can't solve it.
> the fact that “will this AI cause harm” is, mathematically, an unanswerable question.
No it isn't -- this is a fundamental misunderstanding. What is unanswerable is "For all x where x is an AI, will x cause harm?" ... but there is an infinity of specific AIs that provably will or won't cause harm.
Likewise this a very common misunderstanding of the Halting Problem -- Turing proved that there is no TM that can prove whether m will halt for all possible TMs m ... but there are myriad TMs that provably do halt or provably don't halt.