But then, the same can be said of a computer with a finite-sized memory. I think the real thing in the paper is the computational complexity of calculations. W

But then, the same can be said of a computer with a finite-sized memory. I think the real thing in the paper is the computational complexity of calculations. With turing machines, each step is O(1), with transformers it's at least O(n), where n is memory size.