GNU Find 的图灵完备性：从 Mkdir 辅助循环到独立计算

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 纳入“出人意料的图灵完备”系统之列，凸显了看似简单的标准工具中隐藏的复杂性。