For the research focused, there are some references in my blogpost here on what kinds of computational problems minimally require how much CoT to solve: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ Notably Will Merrill's work: https://arxiv.org/abs/2310.07923 As for how universal transformers (looping transformers, but everyone has since forgotten prior work) will affect this, Will Merrill (again) has a…
Looping the transformer is just as turing complete as CoT. It doesn't fundamentally grant it any new theoretical capabilities. You could just scale the model into infinity with infinite context window.
Turing completeness doesn't care about the efficiency of the underlying implementation, which is fine in theoretical computer science, but if you have a model with a finite computational budget, you do actually care about the differences between write only tape vs read-write tape and single tape vs two tape. Having a fixed number of registers like a CPU also helps with reducing the number of redundant operations.
We see none of that with looped transformers, maybe we do see a fixed number of registers.