It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.

In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.

Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?