IIUC, Godel's incompleteness is less about theorems and more about axiomatic systems. Given an axiomatic system, there are statements within it which cannot be proven or disproven. It's relatively unrelated to the platonic ideal of the theorem itself. The statements it considers are axiomatic-system-specific.
Another way to view it is, who cares if we can't prove or disprove "This statement is false". Ok, the axiomatic system is incomplete; fine. What's important is can the system prove a real theorem that I care about.
The busy beaver computability argument addresses these issues. The problem format is always "For Turing machine T with no input, does T halt?". This format can encode many math problems. And we know already that BB(432) is independent of ZF, aka, there is a 432-state TMs which ZF can't prove or disprove the halting behaviour of.
So BB looks at real theorems, ranks them, and we can ask what axiomatic systems can solve them or not. Godel looks at 1 axiomatic system and produces a toy theorem which the system can't solve. That's an extremely important difference!
The core issue is that any fixed LLM can only encode so many axiomatic systems in its states, and the fixed systems implies an upper bound in terms of the BB number which it can solve. Godel is only looking at one system at a time, while BB is a way to use a common problem format to rank every axiomatic system on an infinite number line.
I'm no mathematician, but this is also the crux of Gödel's theorem, he just showed it in a more "hacky" and clever way - but BB(432)'s relation to ZF is also a consequence of Gödel's more general idea, is it not?
-----
Oh, and: All proofs are conditional on axioms. If those axioms are computably enumerable, then all of their consequences are computably enumerable too.
Most propositions may be ugly and irrelevant, but how do you know how many are not so and we just can't prove it? Also, what about stuff like Continuum Hypothesis, would you add it or not?
We are talking about the same thing, but I would actually put this the other way around.
Computation and computability is "the final frontier". Math is a "subset" of that. Doesn't matter if we choose ZFC or in the future discover some "better" subset of core axioms, we will always hit limits where BB will trivially skip over whatever we could prove (let alone Gödel's theorems).
> given fixed input of the statement with no other information sources
Also, this is just trivially avoidable, so not sure if we really should be concerned about this limitation. An LLM in a loop where it can write on a tape can be Turing complete, ergo it can compute anything computable and is "bigger" than math at that point.
Maybe I'm misunderstanding you point, but I don't know how widely this would be held as true. Are you defining "math" as _only_ what can be proven under some particular formal system?
For math I don't have a fix definition, but it's surely a bit more specific than that (e.g. I wouldn't consider the computation that prints a 0 at the same place for infinity math) - but of course I do see the circularity in my argument: a Turing machine is a mathematical object in and of itself. Though being able to talk about something doesn't necessarily change which is "bigger".
As for the other direction, this gets a bit more into the philosophy behind math itself. Constructive math's territory is "easy" - but I am on the opinion that if humans (or any intelligent physical entity) are at most Turing-complete [1], then any non-constructive math "steps" or thoughts must also be at most computable. Well, unfortunately I can't prove whether math done by transcendent entities are also computable, though.
In any case, I am no mathematician, so whatever I think regarding this topic may not have much relevance to anyone, only done CS course with quite a bit of math, but that's obviously not the same.
[1] I believe religion is an escape hatch here from an argument perspective
This is a bit of a strange assumption to make. I do agree that a human, if it had infinite memory, would be an universal machine, i.e. capable of computing any given Turing machine [0]. But would that be the limits of its capabilities? It's far from certain.
You'll get into the philosophy of free will (funnily enough, a sort of inverted Turing test), i.e. for a given human with infinite memory, is there a Turing machine that exactly replicates the behavior of that human? Is our behavior governed entirely by rules? Would that imply that a human themselves is a kind of Chinese room [1]?
> any non-constructive math "steps" or thoughts must also be at most computable.
What does it mean for a "thought" to be computable? Compare to Gödel's incompleteness theorem. Clearly the act of stating the thought, or writing down the theorem, is computable. But proving it to be true or false may very well be impossible.
[0] https://en.wikipedia.org/wiki/Universal_Turing_machine [1] https://en.wikipedia.org/wiki/Chinese_room
Well, given our scientific knowledge it's a molecule-level (only important to disregard quantum physics to make the case easier) physical/chemical process, that we should in principle be able to simulate on any other medium, including a Turing machine.
Nonetheless, I can accept the definition of math where it's about "truths" and truths can obviously exist without being computable.
Do you agree that humans are physical systems?
My understanding is that any physical system can be evaluated to any degree of accuracy by a computer, no?
That's an interesting hypothesis, but I don't know why you'd assume it to be true at face value. It's a bit unclear how you would even define "evaluated", given that we don't yet have a mathematical model of all of physics as we know it. [0] And then consider unknown unknowns.
> Do you agree that humans are physical systems?
Do you consider humans _with infinite memory_ as physical systems? Do you consider computers _with infinite memory_ as physical systems?
[0] https://en.wikipedia.org/wiki/Physics_beyond_the_Standard_Mo...
As for the infinite memory, Turing machines have this nice property that they can only visit a finite amount of memory after finite steps, no matter what. A Turing machine running for a finite time (we got this) will surely use a finite space, so being "a bit short" on infinite space is not a problem, I believe.
Yes... but that's in the area of the big bang and black holes. My understanding is that the chemistry of the brain is very well modeled.
So, unless we find unknown physics, and unless that physics behaves differently than every other known physics, humans are computable?
Do I have that right?
Now consider throwing a ball in the air. Can you even write down the rules that each of the ball's subatomic particles obeys? How can you be certain there exists a computer program that in finite time can predict where any of the particles, for any ball, ends up?
> the chemistry of the brain is very well modeled
There are models, but the fact of those models is that they do not apply to "any degree of accuracy", as you claim.
Consider the ball thrown in the air again. Is the ball affected by what happened 100 years ago, inside of a black hole 100 light years away? Why would it not be affected by that? Or if you grant that it is affected by that, do we then need a model to predict those effects before we can "evaluate" them?
EDIT regarding the below linked blog post: Did you read the rest of my comment? Did you even read the blog post you linked to?
> We certainly don’t have anything close to a complete understanding of how the basic laws actually play out in the real world — we don’t understand high-temperature superconductivity, or for that matter human consciousness
Can you try to consider my central point before replying: Are the rules governing physical reality simpler or more complex than the Collatz conjecture? Does there exist a (theoretical) computer that can "evaluate the Collatz conjecture to any degree of accuracy"?
EDIT 2: I'm not the one moving goalposts. On what grounds are you classifying the question whether a given number ends at 1 or not for the Collaz conjecture as an "inifite" computation? It's a simple boolean question, yes or no. All you have to do is build a computer that can answer yes or no for each integer. Isn't that simpler than answering the position of each atom in the ball after the throw? Each is just a function, what makes one more infinite than the other?
Also, regarding determinism, just read this article by the same guy you linked: https://preposterousuniverse.com/blog/2011/12/05/on-determin...
> For everyday-life purposes, we can’t get around the fact that quantum mechanics makes it impossible to predict the future robustly.
Are you sure?
https://preposterousuniverse.com/blog/2010/09/23/the-laws-un...
You've moved the goalposts again. I said simulate, not predict. It is possible to simulate the entire Schrödinger wavefunction.
And PLEASE - just use the reply button. It is impossible to track every time you edit your comment.
> ANY physical system can be evaluated to ANY DEGREE of accuracy by a computer
It's completely SENSELESS to claim that they are distinct, because in order to EVALUATE or SIMULATE the physical system you will need a FUNCTION which COMPUTES the STATE of the system at a given point in time. The only POSSIBLE distinction between SIMULATING and PREDICTING would be the time taken for the computation, but that is COMPLETELY IRRELEVANT as long as it is finite.
Again, your own source says:
> We CERTAINLY don’t have ANYTHING CLOSE to a complete UNDERSTANDING of how the basic laws actually play out in the real world
How does that square with your claim above?
You are entirely correct. I was sloppy in my first comment. I should have said simulate. My sincere apologies if that's been the crux of our dispute.
> The only POSSIBLE distinction between SIMULATING and PREDICTING would be the time taken for the computation
No. The distinction is in determining which "you" is you. When simulating the wavefunction, every you is simulated.
> We CERTAINLY don’t have ANYTHING CLOSE to a complete UNDERSTANDING of how the basic laws actually play out in the real world
It's very understandable if you include his following sentence:
> But these are manifestations of the underlying laws, not signs that our understanding of the laws are incomplete
He's saying we don't understand emergent behavior produced by the laws - not that the laws themselves are incomplete. E.g. we don't know how/why a bag of neurons turns into a person.
And - you should reply to my comments rather than edit your old ones.
Or a program that knocks out a bottle when it finds a counter example for whatever . U can’t tell whether it will spill the liquid.
And you have as well the problems of approximating the continuous with bits, you’ll always lose information
I hear how passionately you want to believe these things. Unfortunately they're not true. I suggest you look into it.
In what sense? BB(n) is a prime example of an object that can be mathematically defined, yet is not computable. Or see BBB(n) for an "even more" uncomputable function. [0]
> An LLM in a loop where it can write on a tape can be Turing complete
What does this mean? A given LLM, like a given C program, can't really be Turing complete or not in a meaningful sense. The C programming language, or the concept of LLMs in general can be said to be Turning complete or not. Do you mean to state that LLMs in general are not Turing complete, but being "in a loop" somehow makes a difference?
> it can compute anything computable and is "bigger" than math at that point
Again, in what sense is it "bigger" than math? Lots of things are Turing complete, I wouldn't classify lambda calculus as "bigger" than math.
I don’t know what correction to make because you are not even wrong. You are _kinda_ wrong in comparing math and computing via a subset of relation, but it also doesn’t make much sense. If you consider computing as constructive math it should be a subset, but those are not sets, so it doesn’t really help.
LLMs use RNG for sampling, so they are not pure computers.