Comment by GuB-42
8 hours ago
I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.
Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.
Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?
For the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).
A single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.
Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.
The context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.
The context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.
So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).
1 reply →
It's not contradictory at all. The dfa at each step of the turing machine model is also o(1).
1 reply →