Alternatives to recurrent neural networks, in particular, architectures based
on attention or convolutions, have been gaining momentum for processing input
sequences. In spite of their relevance, the computational properties of these
alternatives have not yet been fully explored. We study the computational power
of two of the most paradigmatic architectures exemplifying these mechanisms:
the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever,
2016). We show both models to be Turing complete exclusively based on their
capacity to compute and access internal dense representations of the data. In
particular, neither the Transformer nor the Neural GPU requires access to an
external memory to become Turing complete. Our study also reveals some minimal
sets of elements needed to obtain these completeness results.

本文讲述了研究者探讨替代循环神经网络的新架构（如基于注意力或卷积的架构）的计算能力，通过研究 Transformer 和 Neural GPU 的计算能力，发现这两种模型都可以纯粹依靠计算和访问数据的内部密集表示而成为图灵完备的，而不需要外部存储器。

现代神经网络结构的图灵完备性

On the Turing Completeness of Modern Neural Network Architectures

Algorithm learning is a core problem in artificial intelligence with
significant implications on automation level that can be achieved by machines.
Recently deep learning methods are emerging for synthesizing an algorithm from
its input-output examples, the most successful being the Neural GPU, capable of
learning multiplication. We present several improvements to the Neural GPU that
substantially reduces training time and improves generalization. We introduce a
new technique - hard nonlinearities with saturation costs- that has general
applicability. We also introduce a technique of diagonal gates that can be
applied to active-memory models. The proposed architecture is the first capable
of learning decimal multiplication end-to-end.

介绍一种提高训练效率和泛化能力的神经 GPU 算法，该算法利用新的技术和对活动存储结构的对角门技术来学习十进制乘法。

改进基于神经网络 GPU 的算法学习架构

Improving the Neural GPU Architecture for Algorithm Learning

The Neural GPU is a recent model that can learn algorithms such as
multi-digit binary addition and binary multiplication in a way that generalizes
to inputs of arbitrary length. We show that there are two simple ways of
improving the performance of the Neural GPU: by carefully designing a
curriculum, and by increasing model size. The latter requires a memory
efficient implementation, as a naive implementation of the Neural GPU is memory
intensive. We find that these techniques increase the set of algorithmic
problems that can be solved by the Neural GPU: we have been able to learn to
perform all the arithmetic operations (and generalize to arbitrarily long
numbers) when the arguments are given in the decimal representation (which,
surprisingly, has not been possible before). We have also been able to train
the Neural GPU to evaluate long arithmetic expressions with multiple operands
that require respecting the precedence order of the operands, although these
have succeeded only in their binary representation, and not with perfect
accuracy.
In addition, we gain insight into the Neural GPU by investigating its failure
modes. We find that Neural GPUs that correctly generalize to arbitrarily long
numbers still fail to compute the correct answer on highly-symmetric, atypical
inputs: for example, a Neural GPU that achieves near-perfect generalization on
decimal multiplication of up to 100-digit long numbers can fail on
$000000\dots002 \times 000000\dots002$ while succeeding at $2 \times 2$. These
failure modes are reminiscent of adversarial examples.

本文介绍了两种方式来改进神经 GPU 模型，包括设计课程和增加模型大小，在 10 进制表示下解决所有算术操作并学习执行多操作数算术表达式，同时调查其故障模式与对手示例相似。

神经 GPU 的扩展和限制

Extensions and Limitations of the Neural GPU

Learning an algorithm from examples is a fundamental problem that has been
widely studied. Recently it has been addressed using neural networks, in
particular by Neural Turing Machines (NTMs). These are fully differentiable
computers that use backpropagation to learn their own programming. Despite
their appeal NTMs have a weakness that is caused by their sequential nature:
they are not parallel and are are hard to train due to their large depth when
unfolded.
We present a neural network architecture to address this problem: the Neural
GPU. It is based on a type of convolutional gated recurrent unit and, like the
NTM, is computationally universal. Unlike the NTM, the Neural GPU is highly
parallel which makes it easier to train and efficient to run.
An essential property of algorithms is their ability to handle inputs of
arbitrary size. We show that the Neural GPU can be trained on short instances
of an algorithmic task and successfully generalize to long instances. We
verified it on a number of tasks including long addition and long
multiplication of numbers represented in binary. We train the Neural GPU on
numbers with upto 20 bits and observe no errors whatsoever while testing it,
even on much longer numbers.
To achieve these results we introduce a technique for training deep recurrent
networks: parameter sharing relaxation. We also found a small amount of dropout
and gradient noise to have a large positive effect on learning and
generalization.

本研究提出一种神经网络结构 —— 神经 GPU 来解决 Neural Turing Machine 中存在的训练难题，实现了对于尺寸不确定的输入进行算法训练，并能成功地推广到更长的算法实例中。通过参数共享放松、少量的 dropout 和渐变噪声的技术应用，神经 GPU 在训练和泛化方面收到了显著的正面效应。