points by geraneum 2 days ago | 0 comments
Any basic lookup table is turing complete if you bolt an external infinite tape and read/write head onto it. But then that’s moving the goal post since the context wouldn’t be the “limitless tape” and it’s not a transformer “in the normal way” because turing completeness would be coming from external io and not from auto regressive self attention. Different topic.
The consequence of that is that the original question GuB-42 raised is pretty pointless too. An "inert" transformer effectively has limitations, but as typically used it trivially becomes Turing complete, and so the class of problems it can solve is the exact same class of problems almost any of our other computational devices can solve.
And if you want to point out that this externalises all of what actually matters if we are talking about e.g. intelligence, then yes, it does. But by extension you can trade complexity of the tape for complexity of the machine, and so you can internalise any part of the problem that can be solved with a finite section of tape as a single state transition (trivial proof: For a given machine M with finite state, you can make your machine N execute those steps as a single state transition by having N run M on a state transition.)
To extend that to where I assume they'd want to go in the first place: A transformer wrapped in a loop with access to "just" a "tape head" can "only" be limited from being theoretically able to get all the way to human level intelligence if human brains depend on computations that exceed the Turing computable. But that is no different from any other Turing complete device.
Of course that says nothing of whether it's a practical way of getting there.