Transformers are being used extensively across several sequence modeling
tasks. Significant research effort has been devoted to experimentally probe the
inner workings of Transformers. However, our conceptual and theoretical
understanding of their power and inherent limitations is still nascent. In
particular, the roles of various components in Transformers such as positional
encodings, attention heads, residual connections, and feedforward networks, are
not clear. In this paper, we take a step towards answering these questions. We
analyze the computational power as captured by Turing-completeness. We first
provide an alternate and simpler proof to show that vanilla Transformers are
Turing-complete and then we prove that Transformers with only positional
masking and without any positional encoding are also Turing-complete. We
further analyze the necessity of each component for the Turing-completeness of
the network; interestingly, we find that a particular type of residual
connection is necessary. We demonstrate the practical implications of our
results via experiments on machine translation and synthetic tasks.

这篇论文研究了变形金刚网络的计算能力与图灵完备性，得出了只有通过位置掩蔽而没有位置编码的变形金刚同样具有图灵完备性，而某些残差连接是必需的结论，并通过机器翻译和合成任务的实验说明了结果的实际应用。

关于 Transformer 的计算能力及其对序列建模的启示

On the Computational Power of Transformers and its Implications in  Sequence Modeling

This paper describes how to apply self-attention with relative positional
encodings to the task of relation extraction. We propose to use the
self-attention encoder layer together with an additional position-aware
attention layer that takes into account positions of the query and the object
in the sentence. The self-attention encoder also uses a custom implementation
of relative positional encodings which allow each word in the sentence to take
into account its left and right context. The evaluation of the model is done on
the TACRED dataset. The proposed model relies only on attention (no recurrent
or convolutional layers are used), while improving performance w.r.t. the
previous state of the art.

本文提出如何在关系抽取任务中使用自注意力和相对位置编码。使用一个位置感知的注意力层，利用相对位置编码使每个单词考虑其左右上下文，仅使用注意力机制，在 TACRED 数据集上表现显著提升。