We study the sequence-to-sequence mapping capacity of transformers by relating them to finite transducers, and find that they can express surprisingly large classes of transductions. We do so using variants of RASP, a programming language designed to help people "think like transformers," as an intermediate representation. We extend the existing Boolean variant B-RASP to sequence-to-sequence functions and show that it computes exactly the first-order rational functions (such as string rotation). Then, we introduce two new extensions. B-RASP[pos] enables calculations on positions (such as copying the first half of a string) and contains all first-order regular functions. S-RASP adds prefix sum, which enables additional arithmetic operations (such as squaring a string) and contains all first-order polyregular functions. Finally, we show that masked average-hard attention transformers can simulate S-RASP. A corollary of our results is a new proof that transformer decoders are Turing-complete.

通过与有限转导器的关系，我们研究了变压器的序列到序列映射能力，并发现它们能够表达出令人惊讶的大类转导。我们使用RASP的变体作为中间表示形式，该编程语言旨在帮助人们“像变压器一样思考”。我们将现有的布尔变体B-RASP扩展到序列到序列函数，并且表明它计算了一阶有理函数（如字符串旋转）。随后，我们引入两个新的扩展。B-RASP[pos]允许在位置上进行计算（如复制字符串的前一半），并且包含所有一阶正则函数。S-RASP添加了前缀和，它使得额外的算术运算成为可能（如字符串的平方），并且包含了所有一阶多正则函数。最后，我们展示了掩码平均硬注意力变压器可以模拟S-RASP。我们结果的一个推论是变压器解码器是图灵完备的的新证明。

变压器作为传感器