Response to Authors
I thank the authors for their thoughtful response.
**Clarity of Lemma 4.1:** The clarity of the presentation of this lemma needs further improvement. $H_s$, $\phi$, $C'''$ are undefined. The "empirical tape space" is also undefined. Though not as major, the writing could also be further improved: e.g., line 241 is missing a period. Is $\mathcal{M}$ the same as $M$?
**Proof of Lemma 4.1:** The mapping $\phi$ is not, strictly speaking, surjective. For example, if $H_s$ did not consist of one-hot vectors, it would not correspond to any input Turing machine state. For a fixed $d$, there is a maximum number of tape symbols $\Gamma_t$ that can be encoded in the hidden state, right?
However, the clarity of the proof of Lemma 4.1 is much improved (perhaps the additional background on the transformer self-attention mechanism is unneeded, but not unwelcome). One thing that is not completely clear is whether the entire Turing machine state is encoded in the embedding of a single token, or across the embeddings of all tokens (such as by having each tape position correspond to a token). The equation on line 785 suggests everything is concatenated into a single large vector, but the equation on line 774 suggest each token encodes one tape position and its value. But judging from the construction's use of multi-head attention, it seems that each token encodes one tape position and its value. It is also not clear whether the concatenation operator $\oplus$ refers to vector concatenation or token concatenation.
Why use the attention mask to implement the computation in the MHA block? This is rather unrepresentative of real-world transformer models which rely on the projection matrices $W_Q$, $W_K$, $W_V$ (and possibly biases) to implement the computation in this layer (and they either use a causal attention mask as in decoder-only models, or none at all, as in encoder-only models). I don't think this is fatal to the proof as I think it is possible to implement the same computation using the projections, but I strongly recommend the authors re-write this construction.
The output of the attention layer (after residuals) is identical at position $0$ and $i_h$ (i.e., $u_0 = u_{i_h}$), and therefore $FFN(u_0)$ must be equal to $FFN(u_{i_h})$. $\gamma_{h_t}'$ is also undefined.
I don't see how the construction of one MHA layer helps to implement a single step in a Turing machine. One construction that may work is to have the attention mechanism shift the tape by one position to the left or right, depending on the state and value at the head position. The FFN would then need to implement the state transition function and perform any write operation to the tape at the head position. But it seems from the current description in the proof, the MHA layer aims to swap the states at position $0$ and $i_h$ (but the aim of the FFN layer seems to align with this suggested construction).
Line 1022: "In particular, if represented in binary rather than one-hot, the lower bound of d can be further
compressed to..."
This would make the construction in Section A.2 invalid, and you would need to define a new construction to work with the non-one-hot encodings.
How does the construction here relate to that of [1]? They similarly show that transformers with chain-of-thought can simulate Turing machines.
[1] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. ICLR 2024.
Overall I think the premise of the work is interesting and the portions on learnability are potentially very impactful. However, I do think the paper needs an additional round of revision to further tighten the arguments and the writing. As such, I will maintain my overall score, but I will slightly increase the presentation score in recognition of the improved clarity so far.