Earlier quoted context omitted.
GPQA scores are mostly from pre-training, against content in the corpus. They have gone silent but look at the GPT4 technical report which calls this out. We are nowhere close to what Sam Altman calls AGI and transformers are still limited to what uniform-TC0 can do. As an example the Boolean Formula Value Problem is NC1-complete, thus beyond transformers but trivial to solve with a TM. As it is now proven that the f…
Isn't any physically realizable computer (including our brains) limited to what uniform-TC0 can do?
The default nonuniform circuits classes are allowed to have a different circuit per input size, the uniform types have unbounded fan-in
Similar to how a k-tape TM doesn't get 'charged' for the input size.
With Nick Class (NC) the number of components is similar to traditional compute time while depth relates to the ability to parallelize operations.
These are different than biological neurons, not better or worse but just different.
Human neurons can use dendritic compartmentalization, use spike timing, can retime spikes etc...
While the perceptron model we use in ML is useful, it is not able to do xor in one layer, while biological neurons do that without anything even reaching the soma, purely in the dendrites.
Statistical learning models still comes down to a choice function, no matter if you call that set shattering or...
With physical computers the time hierarchy does apply and if TIME(g(n)) is given more time than TIME(f(n)), g(n) can solve more problems.
So you can simulate a NTM with exhaustive search with a physical computer.
Physical computers also tend to have NAND and XOR gates, and can have different circuit depths.
When you are in TC0, you only have AND, OR and Threshold (or majority) gates.
Think of instruction level parallelism in a typical CPU, it can return early, vs Itanium EPIC, which had to wait for the longest operation. Predicated execution is also how GPUs work.
They can send a mask and save on load store ops as an example, but the cost of that parallelism is the consent depth.
It is the parallelism tradeoff that both makes transformers practical as well as limit what they can do.
The IID assumption and autograd requiring smooth manifolds plays a role too.
The frame problem, which causes hard problems to become unsolvable for computers and people alike does also.
But the fact that we have polynomial time solutions for the Boolean Formula Value Problem, as mentioned in my post above is probably a simpler way of realizing physical computers aren't limited to uniform-TC0.