用PyTorch构建可精确模拟图灵机的神经网络，无需训练。
A PyTorch Library of Turing-Complete Neural Networks
- 从图灵机转移函数直接构造神经网络，前向传播即一步计算
- 实现两种架构：基于注意力的Transformer与基于康托集的递归网络
- 展示神经网络如何模拟布尔电路与位置查找，为符号-神经桥梁提供实证
我们提出一个PyTorch库，能将图灵机的描述（包括转移函数和终止状态）编译为神经网络及其权重，生成的模型在不进行任何训练的情况下精确模拟指定的图灵机。该包构建的模型在前向传播中对应图灵机的一次计算步骤。实现了两种架构：(1) 基于Wei、Chen和Ma（2021）的Transformer，包含自注意力、交叉注意力和前馈层；(2) 基于Siegelmann和Sontag（1995）的递归网络，通过康托集编码栈。研究从基础出发，证明了ReLU网络可实现布尔电路（如与、或、非、异或门及合取范式公式、二进制加法器），而硬注意力可实现磁带上位置的查找。该工具为符号-神经融合提供了可运行的实例，也为未来研究梯度优化下解的稳定性奠定基础。代码开源地址：https://github.com/jonrbates/turing。
原文摘要 · Abstract (English)
We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training. Given a transition function and a set of terminal states, the package constructs a model whose forward pass corresponds to one step of the Turing machine. Two architectures are implemented, each realizing a different theoretical result: (1) a transformer with self-attention, cross-attention, and feedforward layers based on Wei, Chen, and Ma (2021), and (2) a recurrent network based on Siegelmann and Sontag (1995) that encodes the stack in a Cantor set. We develop the constructions from first principles, showing how ReLU networks implement Boolean circuits (AND, OR, NOT, XOR gates and their composition into DNF formulas and binary adders) and how hard attention implements positional lookup on the tape. The package serves as a concrete, runnable reference for the symbolic-neural bridge, and as a foundation for future work on the stability of constructed solutions under gradient-based optimization. Code is available at https://github.com/jonrbates/turing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。