arXiv cs.AI· Sergey Salishev·· 10 小时前AI 评分18
从工程视角解读有界停机问题与通用机器的可观测性质
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
AI 导读
论文将停机问题重新定义为有限步预算 T 下的有界停机问题，并用带显式加法开销的对角线论证证明：不存在固定确定性检查器能在低于 T 的任意固定比例内判定所有实例。
正文 · AI 翻译
摘要：停机问题问的是程序在资源不受限的情况下最终是否会停机。工程系统则转而认证有界停机：给定一个程序、一个输入和一个步数预算 T，判定该程序是否在 T 步内停机。本文研究它的两种用途。第一，它定义了一个精确的有限预算问题，将模拟程序与检查器置于同一单位成本时间尺度上，从而使检查器能够嵌入对抗性程序中。一个带有显式加性开销的对角论证表明，对于足够大的 T，不存在固定的确定性检查器能在任何低于 1 的固定 T 比例内判定每个实例。在非确定性情形下，T 界定了为获得稳定可观测判定所允许的分支深度。第二，有界停机实例为有限论域通用性提供了对抗性测试，因为通用模型必须随着 T 增长支持任意有限计算。这些测试检查资源随 T 的增长、不存在固定的深思界限，以及对中间数据的后续访问。它们区分了具有可扩展外部资源的固定模型、随 T 增长的模型族，以及围绕固定组件构建的更大系统。对于机器学习系统，这识别出通用性主张所假设的资源增长，以及该主张对已部署模型是否失效。
| 评论： | 9 页，1 张表 |
| 主题： | 计算复杂性（cs.CC）；人工智能（cs.AI）；形式语言与自动机理论（cs.FL）；逻辑（math.LO） |
| 引用为： | arXiv:2611.06303 [cs.CC] |
| （或 arXiv:2611.06303v1 [cs.CC] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.06303 由 DataCite 颁发的 arXiv DOI（待注册） |
|
| 期刊 参考： | S. Salishev, CYBERNETICS AND PHYSICS, VOL. 15, NO. 2, 2026, 234-242 |
| 相关 DOI： | https://doi.org/10.35470/2226-4116-2026-15-2-234-242
链接到相关资源的 DOI |
提交历史
来自：Sergey Salishev [查看电子邮件]
[v1]
2026 年 11 月 4 日星期三 10:36:39 UTC（34 KB）
来源：arXiv cs.AI · arxiv.org