alt Hacker NewsThe 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).
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.