We know or have strong hints at the limits of math/computation related to LLMs + CoT
Note how PARITY and MEDIAN is hard here:
https://arxiv.org/abs/2502.02393
We also know HALT == open frame == symbol grounding == system identification problems.
The definition of AGI is also not well defined, but given the following:
> Strong AI, also called artificial general intelligence, refers to machines possessing generalized intelligence and capabilities on par with human cognition.
We know enough for any mechanical methods with either current machines or even quantum machines, what is needed is impossible with the above definition.
Walter Pitts drank himself to death, in part because of the failure of the perceptron model.
Humans and machines are better at different things, and while ANNs are inspired by biology, they are very different.
There are some hints that the way biological neurons work is incompatible with math as we know it.
https://arxiv.org/abs/2311.00061
Computation and machine learning are incredibly powerful and useful, but are fundamentally different, and that different is both a benefit and a limit.
There are dozens of 'no effective procedure', 'no approximation', etc .. results that demonstrate that ML as we know it today is possible of most definitions of AGI.
That is why particular C* types shift the goal post, because we know that the traditional definition of strong AI is equivalent to solving HALT.
https://philarchive.org/rec/DIEEOT-2
There is another path following PAC Learning as compression an NP being about finding parsimonious reductions (P being in NP)
It is invoked because LLM+CoT requires a polynomial amount of scratch space to represent P, which is in NP.
I didn't suggest that it was a definition of Intelligence.
The Church–Turing thesis states that any algorithmic function can be computed by a Turing machine.
That includes a human with a piece of paper.
But NP is better though of the set of decision problems verifiable by a TM in polynomial time. Any TM or equivalently lambda calculus or algorithm can solve the Entscheidungsproblem, which was used by Turing to define Halt.
PAC Learning depends on set shattering, at some point it has to 'decide' if an input is a member of a set, no matter how complicated the parts are on top of that set, it is still a binary 'decison'
We know that is not how biological neurons work exclusively. They have many features like spike trains, spike retiming, dendritic compartmentalization etc...
Those are not compatible with the fundamental limits of computation we understand today.
HALT generalizes to Rice's theorm, which says all non-trivial symantic properties of programs are undecidable.
Once again, as NP is the set of decision problems verifiable by a DTM in poly time, that is why NP is important.
Unfortunately the above is also a barrier to formal definition of the class of AI-complete.
While it may not be sufficient to prove anything about the vague concept of intelligence, understanding the limits of computation is important.
We do know enough to say that the belief that AGI being obtainable without major discoveries is blind hope.
But that due to the generalization concept, which is a fundamental limit of computation.
