OpenAI图灵机模拟结果被指隐含RAM空间复杂度新推论

OpenAI 近期发布的单带图灵机模拟结果引发理论界关注。复杂度理论学者 Ryan Williams 指出，若该结果正确，可直接推出一个未被论文提及的结论：RAM 模型下时间为 t 的算法，其空间复杂度可落入 SPACE[t^(4/5)]。他进一步解释，对于字长 O(log t) 的 Word RAM，可将内存的（地址, 字）对存放在图灵机带上约 t·poly(log t) 的空间内实现模拟。此前网友 KortenOliver 也独立发现了这一推论，引发社区讨论。

2026-10-07 ~ 2026-10-07 · 3 条相关

• OpenAI 单带图灵机模拟可推出新结论:RAM 时间 t 落入 SPACE[t^4/5] — rrwilliams · 2026-10-07
• 理论学家拆解：如何用单带图灵机模拟对数字长 RAM — rrwilliams · 2026-10-07

另有 1 条近重复转述:KortenOliver