GNU find 的图灵完备性

Source: Hacker News

摘要

Unix 命令 find 是教给初学者的第一批命令之一，却仍然是有经验的工程师不可或缺的工具。本文展示了 find 具备出人意料的计算能力，并使用 GNU 实现（Linux 发行版的标准实现）给出三个图灵完备性的结果。

1. find + mkdir（仅包含 find 与 mkdir 的系统）是图灵完备的：通过将计算状态编码为目录路径，并利用正则表达式的反向引用复制子串，我们可以模拟 2‑tag 系统。
2. 仅使用 GNU find 4.9.0+ 即可实现图灵完备：在遍历过程中读取并写入文件，我们在没有 mkdir 的情况下模拟两计数器机器。
3. find + mkdir 在不使用正则反向引用的情况下仍然图灵完备：通过将正则模式直接编码进目录名的技巧，获得相同的计算能力。

这些结果将 find 纳入“出人意料的图灵完备系统”之列，凸显了看似简单的标准工具中隐藏的复杂性。

主题

• 数据结构与算法 (cs.DS)

引用

• arXiv:2602.20762 (cs.DS)
• (或 arXiv:2602.20762v1 (cs.DS) 以获取此版本)

DOI

https://doi.org/10.48550/arXiv.2602.20762

提交历史

来自：Keigo Oka 查看邮件

[v1] Tue, 24 Feb 2026 10:41:47 UTC (18 KB)