用对话管理机制让变压器模型实现图灵完备,仅需两个带弹出功能的通道。
Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts
- 设计带通道的对话管理架构,通过入栈、出栈和推送操作控制上下文
- 当通道数≥2时,模型可模拟任意图灵机,达到计算极限
- 适用于研究神经网络可计算性与多智能体系统协同的学者
我们研究固定精度因果变压器中的对话管理机制。对话被划分为有限块的通道,每次转移只查看固定可见后缀并可追加一个块,不改变模型结构、权重和标记协议。操作 $P_c$ 删除通道 $c$ 的最新块并暴露前一个块。层由带控制器的对话管理转换器 $ ext{TMT}_k^n$ 建模:一个有限控制器、$k$ 个通道,每轮在保持、推送、弹出中选择动作,由调用者驱动状态映射。固定可见窗口编码为有限符号。无弹出的受限对话管理转换器 $ ext{RTMT}_k^n$ 是标准追加型层,对任意固定 $k$,恰好实现确定性有限状态转换。对任意固定智能体群体,在单调协议下(追加、路由、复制可见块)亦然。引入 $\\{P_c\ }_{c=1}^k$ 恢复弹出能力。若按最新优先顺序,弹出通道即为栈结构;通过霍普克罗夫特-乌尔曼表示法迁移经典层级:$k=1$ 时为 $\text{DCFL}$,$k\ge2$ 时为 $\text{RE}$。单通道代理与 $k$ 通道控制器的协同,使两个弹出通道(单智能体或双智能体)足以实现通用性。模拟代价及对固定块大小与可见半径的不变性均被给出。边界条件固定精度、字母表、块、可见性、控制器状态与群体规模;扩展精确上下文、隐藏块访问、可写存储与无界 \textbf{Spawn} 可进一步增加状态空间。
原文摘要 · Abstract (English)
We study transcript management for fixed, finite-precision causal Transformers. A transcript is partitioned into channels of bounded blocks. Each transition consults a fixed visible suffix and may append one block, leaving the model, weights, and token protocol unchanged. The operation $P_c:=\PopContext(c)$ deletes the newest block on channel $c$ and exposes its predecessor. We model the layer by the Transcript-Managed Transducer $\TMTn{k}$: one finite controller, $k$ channels, and per-round actions from stay, push, and pop under a caller-driven status map. Fixed visible windows encode as finite symbols. The pop-free Restricted Transcript-Managed Transducer $\RTMTn{k}$ is the standard append-only layer and, for every fixed $k$, realizes exactly the deterministic finite-state transductions. The same holds for every fixed finite agent population under a monotone protocol that appends, routes, and copies visible blocks. Admitting $\{P_c\}_{c=1}^k$ restores pop. Newest-first, a pop-enabled channel is a stack; compiling to the Hopcroft--Ullman presentation transfers the classical hierarchy: $\DCFL$ for $k=1$ and $\RE$ for every $k\ge2$. Orchestrated one-channel agents match one controller with $k$ channels, so two pop-enabled transcripts---in one agent or two---suffice for universality. Simulation costs and invariance to fixed block size and visible radius are stated. The bounds fix precision, alphabets, blocks, visibility, controller state, and population; growing exact context, hidden-block access, writable stores, and unbounded \textbf{Spawn} add further state.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。