What a wonderful text. Easy to read, concise, clear, interesting -- and above all, important.
I would add context for 2025 about the fundamental limits this places on what (modern) AI is in principal capable of. Perhaps some "non-computable" features would need to be hard-coded into AI, so that it could at least better approximate the types of incomputable problems we might ask it to do?
Also, a search of the text for "conscious" does not yield anything, which is probably a good thing. This text also reminds me of the questions like, "What does it mean to be conscious?" and, "How are human brains able to reason about (things like) incomputability, which in some sense, computers as we currently understand them could never do?" and, "What specifically beyond pure mathematics does a brain have or need in order to be conscious enough to reason about such things?"
Gödel's Incompleteness Theorem places a limit on what you can prove within a formal system. Neither humans nor LLMs are a formal system, so it says nothing about them.
Someone's going to think that, since you can formally model computer programs (and thus formally model how an LLMs runs), that means that Gödel's Incompleteness Theorem applies to computer programs and to LLMs. But that's irrelevant; being model-able doesn't make something a formal system!
"Formal system" has a very technical meaning: it has a set of consistent axioms, and the ability to enumerate formal proofs using those axioms. For example, Zermelo-Fraenkel set theory is a formal system [1]. It has nine formal axioms, which you can see listed in its Wikipedia article. Utterly different kind of thing than humans or LLMs. Comparing an LLM to ZFC is like comparing a particular watermelon to the number 4.
This is unnecessary nitpicking. You can easily derive a logical contradiction of your choice by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system. If a specific theorem doesn't prove that, a simple corollary will.
If you want to escape the limits of computability, you have to assume that the physical Church–Turing thesis is false. That the reality allows mechanisms that cannot be modeled formally or simulated on any currently plausible computer.
> by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system
Something that cannot be proven within which formal system? Every true statement can be proven by some formal system. No formal system can prove all true statements.
(This is all about Godel incompleteness. Turing incomputability does apply though, see the sibling comments! It's important to keep them separate, they're saying different things.)
Oof, I pattern matched OP to a different argument I've seen a lot. That's embarrassing.
Yes, that's correct, it's provably impossible to construct an LLM that, if you ask it "Will this program halt? <program>", answers correctly for all programs. Likewise humans, under the assumption that you can accurately simulate physics with a computer. (Note that QM isn't an obstacle, as you can emulate QM just fine with a classical computer with a mere exponential slowdown.)
While it's true that LLMs are not strictly a formal system, they do operate on Turing-complete hardware and software, and thus they are still subject to the broader limitations of computability theory, meaning they cannot escape fundamental constraints like undecidability or incompleteness when attempting formal reasoning.
LLMs don't do formal reasoning. Not in any sense. They don't do any kind of reasoning - they replay combinatorics of the reasoning that was encoded in their training data via "finding" the patterns in the relationships of the tokens at different scales and then applying those to the generation of some output triggered by the input.
That's irrelevant. They have an "input tape" and an "output tape" and whatever goes on inside the LLM could in principle be implemented in a TM (of course that wouldn't be efficient but that's besides the point).
Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere
While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time.
For Pi as an example: f(3) = 4 (from 3.14)
Almost all applies to the elements of an uncountable set except for countable subset.
As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction.
Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable)
It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc....
But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one.
So right there is an uncountable infinity of non-computable numbers.
What a wonderful text. Easy to read, concise, clear, interesting -- and above all, important.
I would add context for 2025 about the fundamental limits this places on what (modern) AI is in principal capable of. Perhaps some "non-computable" features would need to be hard-coded into AI, so that it could at least better approximate the types of incomputable problems we might ask it to do?
Also, a search of the text for "conscious" does not yield anything, which is probably a good thing. This text also reminds me of the questions like, "What does it mean to be conscious?" and, "How are human brains able to reason about (things like) incomputability, which in some sense, computers as we currently understand them could never do?" and, "What specifically beyond pure mathematics does a brain have or need in order to be conscious enough to reason about such things?"
Gödel's Incompleteness Theorem places a limit on what you can prove within a formal system. Neither humans nor LLMs are a formal system, so it says nothing about them.
Someone's going to think that, since you can formally model computer programs (and thus formally model how an LLMs runs), that means that Gödel's Incompleteness Theorem applies to computer programs and to LLMs. But that's irrelevant; being model-able doesn't make something a formal system!
"Formal system" has a very technical meaning: it has a set of consistent axioms, and the ability to enumerate formal proofs using those axioms. For example, Zermelo-Fraenkel set theory is a formal system [1]. It has nine formal axioms, which you can see listed in its Wikipedia article. Utterly different kind of thing than humans or LLMs. Comparing an LLM to ZFC is like comparing a particular watermelon to the number 4.
[1] https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...
This is unnecessary nitpicking. You can easily derive a logical contradiction of your choice by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system. If a specific theorem doesn't prove that, a simple corollary will.
If you want to escape the limits of computability, you have to assume that the physical Church–Turing thesis is false. That the reality allows mechanisms that cannot be modeled formally or simulated on any currently plausible computer.
> by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system
Something that cannot be proven within which formal system? Every true statement can be proven by some formal system. No formal system can prove all true statements.
(This is all about Godel incompleteness. Turing incomputability does apply though, see the sibling comments! It's important to keep them separate, they're saying different things.)
I'm confused by this. Why are you talking about Gödel?
LLMs, like any model of computation, are subject to the limits of Turing Machines, so they cannot for example solve the halting problem.
Oof, I pattern matched OP to a different argument I've seen a lot. That's embarrassing.
Yes, that's correct, it's provably impossible to construct an LLM that, if you ask it "Will this program halt? <program>", answers correctly for all programs. Likewise humans, under the assumption that you can accurately simulate physics with a computer. (Note that QM isn't an obstacle, as you can emulate QM just fine with a classical computer with a mere exponential slowdown.)
While it's true that LLMs are not strictly a formal system, they do operate on Turing-complete hardware and software, and thus they are still subject to the broader limitations of computability theory, meaning they cannot escape fundamental constraints like undecidability or incompleteness when attempting formal reasoning.
LLMs don't do formal reasoning. Not in any sense. They don't do any kind of reasoning - they replay combinatorics of the reasoning that was encoded in their training data via "finding" the patterns in the relationships of the tokens at different scales and then applying those to the generation of some output triggered by the input.
That's irrelevant. They have an "input tape" and an "output tape" and whatever goes on inside the LLM could in principle be implemented in a TM (of course that wouldn't be efficient but that's besides the point).
corollary: Numberphile (with Matt Parker of Stand Up Maths) - "All the Numbers". Most are incomputable, of course :)
[0] https://www.youtube.com/watch?v=5TkIe60y2GI&t=1s
Other than Chaitin's constant(s), name a few that aren't computable.
Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere
While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time.
For Pi as an example: f(3) = 4 (from 3.14)
Almost all applies to the elements of an uncountable set except for countable subset.
As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction.
Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable)
It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc....
But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one.
So right there is an uncountable infinity of non-computable numbers.
Another excellent book is Tom Stuart's Understanding Computation : From Simple Machines to Impossible Programs - https://computationbook.com/