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 proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with 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的计算能力及其对序列建模的启示