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。我们结果的一个推论是变压器解码器是图灵完备的的新证明。

变压器作为传感器

Transformers as Transducers

Recently regular decision processes have been proposed as a well-behaved form
of non-Markov decision process. Regular decision processes are characterised by
a transition function and a reward function that depend on the whole history,
though regularly (as in regular languages). In practice both the transition and
the reward functions can be seen as finite transducers. We study reinforcement
learning in regular decision processes. Our main contribution is to show that a
near-optimal policy can be PAC-learned in polynomial time in a set of
parameters that describe the underlying decision process. We argue that the
identified set of parameters is minimal and it reasonably captures the
difficulty of a regular decision process.

本文探讨了如何在正则决策流程中实现强化学习，并提出了在一组参数中可以 PAC - 学习这一流程的最优策略。