> In either case I believe people who can put AI to the most value are the mathematicians themselves
The net output of math will increase, and mathematicians have more work now to unravel all this, and make it useful. AI plays the role of a monkey in the infinite monkey theorem [1]. We now need an LLM corollary - Something like: A finite number of LLM agents will almost surely find all theorems given an infinite token budget.
It's impossible for finite number of LLMs to solve all theorems. This would imply that the busy beaver sequence is computable which implies the halting problem is decidable.
For any finite program (eg some LLMs), there is a true math theorem which they cannot prove or disprove (given fixed input of the statement with no other information sources). If that weren’t true, BB would be computable.
Math is beyond computation. Since AI is just bits in bits out, it has this fundamental limitation.
Any magic of AI systems comes from the transformed meaning of its input data. With fixed weights any LLM is just an artifact. For example a human prompting an LLM constitutes an extra information source, which removes the above limitations. In theory any input from the natural world would remove the limitations too. The natural world is a black box and we don't know what kind of meaning or intelligence could underly it.
> Math is beyond computation.
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.
> Computation and computability is "the final frontier". Math is a "subset" of that.
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.
[0] https://wiki.bbchallenge.org/wiki/Beeping_Busy_Beaver
> Computation and computability is "the final frontier". Math is a "subset" of that.
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?
Well, I only know how to define computability in terms of Turing machines.
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
> if humans (or any intelligent physical entity) are at most Turing-complete
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
> What does it mean for a "thought" to be computable?
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.
> But would that be the limits of its capabilities? It's far from certain.
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?
> any physical system can be evaluated to any degree of accuracy by a computer
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...
I agree that physics being simulated is not that easy to handwave away. That's why I mention that brains probably don't "depend" on some quantum-level behavior and a more macro view of physics could be enough. What I mean here is that while there are obviously quantum effects in play at the atomic/molecular levels, if we take the cells as a black box and replace them with statistical processes, we would probably still get a human intelligence as a result - but of course I can't prove it. As a hunch, the 100 billion neurons and their 100 trillion connections, and of course their environment (glial cells are important)'s proper Simulation is enough.
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.
> given that we don't yet have a mathematical model of all of physics as we know it
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?
Let me illustrate with an example. Are you familiar with with the Collatz conjecture? It's an example of a system with only one variable, and two simple rules. Are you certain that there exists a computer program that in finite time can compute where any given integer ends up?
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.
> There are models, but the fact of those models is that they do not apply to "any degree of accuracy", as you claim.
Are you sure?
https://preposterousuniverse.com/blog/2010/09/23/the-laws-un...
Friend, I'm not going to chase your ever changing text. Please just use the reply button.
> For everyday-life purposes, we can’t get around the fact that quantum mechanics makes it impossible to predict the future robustly.
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.
PLEASE just stop complaining about "moving the goalposts" when the issue is your own lack of clarity of both expression and reasoning. WHAT is the distinction between "simulate" and "predict"? You said neither by the way, you said "evaluate".
> 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 said neither by the way, you said "evaluate".
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.
Re: Collatz - you've moved the goalposts. Answering Collatz requires solving a halting problem. I didn't claim that I could find the end of an infinite computation. I claimed to be able to simulate a finite one.
And - you should reply to my comments rather than edit your old ones.
No
HEH. Well... the only other option is supernatural. Is that what you mean?
Does that mean that humans could produce mathematical proofs that are entirely logical and verifiable by other humans, but that cannot be formalised in any automatically verifiable language such as lean?
You need to do some studying _without_ chat gpt if you like math.
Care to give some explanation and correction then?
Even if the busy beaver sequence were computable and the halting problem were decidable, Gödel's incompleteness theorems would still prevent all theorems from being solved, regardless of if one used LLMs or not.
I think there's a really important sense in which Godel's argument is not the full story.
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.
But a 432-state TM is a problem that we would like to "prove" is it not? It's not even a particularly complex one to begin with, my smartwatch has orders of magnitude more state then that and yet here we see that all of our math "fails" at it.
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?
Even more concretely, the halting problem for turing machines with halting problem oracle would be undecidable for them. And if you could solve that you won't believe what problem would be undecidable. It's turtles all the way up.
Pretty sure Gödel’s theorems imply the halting problem if you squint hard enough.
The problem with what you're saying is that any old random true proposition about the integers is not necessarily interesting enough to be called a theorem. GIT (or the uncomputability of the Busy Beaver problem) does not establish a limitation on proving theorems, but rather on determining whether a proposition is true or not. Most propositions are ugly and irrelevant. So GIT/Busy Beaver is irrelevant.
-----
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 are ugly and irrelevant.
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?
> It's impossible for finite number of LLMs to solve all theorems. This would imply that the busy beaver sequence is computable which implies the halting problem is decidable
LLMs use RNG for sampling, so they are not pure computers.
Computable includes BPP
Not sure if GPT based LLMs are polynomial time.
lol same with people.
"Given infinite thinking time a finite number of humans will solve all theorems"
I also love the angle that this was not intelligence just brute force. As if the mathematicians didn't reeaaally want to solve this they were just too lazy to give it a good try.
What does AI have to actually do before you realize these things are actually smart?
Machines have a much higher capacity for work than human beings. Saying that these proofs did not require equivelant intelligence, but benefitted from sheer volume, does not strike me as unreasonable.
Yes my only point here is that you can argue about the semantics of how smart they really are but they are undeniably smart.
Today it cost massive effort but it's possible 10-20yrs from now an AI could solve a problem like this in under an hour with a single thread on a free subscription paid for by serving an ad.
These arguments are so weak because you'll then have to make the same one a few years from now when it does something else impossible. The argument only stands if we assume no progress will occur.
Funny that you imagine a future where AI can solve complex math quickly, but humans are still watching ads, for some reason.
I just think you and the other guy have different definitions of "smart". There's no denying that LLMs are useful, but I don't know if I'd classify them as "smart". There were probably people in the 80s saying computers were "smart" because they could compute 78971 * 12341 faster than a human.
In what sense is a LLM "undeniably smart" but a CPU from the 80s isn't? Or would you define such a CPU as "smart"?
ASI may kill us all 100yrs from now but ads are forever my friend.
You're right though they largely are "smart" in the 80's computer sense. This is largely due to continual learning being unsolved.
BUT the more you look at them, research, and try experiments there's something there not in a 80s computer. If I had to guess maybe 1-5% of a humans ability but it's there. They are able to do novel things but ever step outside of their distribution takes exponential effort for every small addition. There is a true ability to adapt and learn new things on the fly, things never seen before. That is the the smart part. There something hidden in these things we don't understand that allows novel insights built from in context learning.
It's actually measurable in experimental settings but even there it's hard to tease out. I saw it mostly while doing CL training experiments. But I also see it while working with them for coding novel things.
But the more power we provide and farther down the road of this we go those 1-5% are things like solving unsolved math problems. No human solved these things. You say brute force, I say it needed massive effort to break out of it's distribution and get those small insights. It's very human like when taken at scale. The scary thing is that scale is getting smaller every day.
It feels goalpost-movey to downplay exploring a large search space efficiently in regards to "intelligence". If we dug into a human genius's brain and found it was somehow trying out a million ways to solve a a problem at once, no one would seriously suggest the person isn't actually intelligent.
And our brains must something like that at some physical level. You can't have a "turtles all the way down" of reasoning - the building blocks must be simpler. It must reduce to something like pathfinding and brute force at some point, weighted by factors in the system and maybe some randomness.
We have a romantic view of intelligence, perhaps stemming from intuition within the context of scientific discovery. Given enough intelligence, and enough context, a brilliant person can have a stroke of inspiration that allows them to make a major leap (a-la General Relativity or Fermats last theorem). We haven't seen THAT same capacity from a machine, but we see the more ordinary, unsexy grinding type of progress that represents 99.9% of scientific reality.
I would find it very interesting to train a model on information only available prior to the discovery of e.g. relativity or calculus and see if it can invent it. My intuition is that modern frontiers absolutely could. Not to take away from their brilliance, but Newton and Einstein were brilliant people who also happened to be in the perfect place at the perfect time - there's not so much "low hanging (i.e. approachable by one brilliant individual) but immensely valuable fruit" anymore.
Is there truly anything new under the sun? Hasn't all of existence alway been here? All math, all physics? We could have merely discovered it. Intuition might be nothing more than combinations of what already exists rather than some sort of divine insight that unlocks previously unknowable mysteries.
Agreed. I don't believe intuition and creativity would be more than pattern recognition, remixing ideas, and trial and error combined with a kind of "genetic algorithm" approach if you deconstructed them into what the brain is actually doing.
This isn't necessarily true. There may be proofs so complex, they could exceed the limit of human cognition.
There certainly are such proofs. Even for simple decidable theories we have very large lower bounds on decision complexity (like double exponential), which implies large lower bounds on the function from "length of theorem statement" to "length of shortest proof".
For undecidable theories, there is no computable function bounding this blowup from theorem length to proof length (otherwise, the theory would be decidable.)