Softmax Transformers are Turing-Complete

Hongjian Jiang, Michael Hahn, Georg Zetzsche +1

Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are…