Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
2026/02/24 by Keigo Oka · 18 voices
#cs.DS
paper · pdf
Abstract
The Unix command find is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that find possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributions). (1) find + mkdir (a system that has only find and mkdir) is Turing complete: by encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems. (2) GNU find 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without mkdir. (3) find + mkdir without regex back-references is still Turing complete: by a trick of encoding regex patterns directly into directory names, we achieve the same power. These results place find among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.
Citations
Discussions
- Turing Completeness of GNU find [hn, 137 points, 26 comments]
- I know I come across as a big fan of Rust, but maybe its time to try `find + mkdir`? GNU find + mkdir is Turing Complete : arxiv.org/pdf/2602.20762 [bsky, 28 points, 2 comments]
- Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation [lobsters, 22 points, 1 comments]
- Turing Completeness of GNU find Unix command: from mkdir-assisted Loops to Standalone Computation #Research #ComputerTheory arxiv.org/abs/2602.20762 [bsky, 3 points, 0 comments]
- The Unix command \texttt{find} is Turing Complete: by reading and writing to files during traversal, a two-counter machine can be simulated. Includes two other TC systems that use \texttt{find} and \t [bsky, 2 points, 0 comments]
- Turing Completeness of GNU find https:// arxiv.org/abs/2602.20762 # arxiv [mastodon, 1 points, 0 comments]
- I'm a simple person with old-fashioned tastes, and I'll always be there for any article about something else that can be proven to be Turing-complete. [bsky, 1 points, 0 comments]
- Turing Completeness of GNU find https://arxiv.org/abs/2602.20762 https://news.ycombinator.com/item?id=47147609 [bsky, 0 points, 0 comments]
- Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput https://arxiv.org/abs/2602.20762 (https://news.ycombinator.com/item?id=47147609) [bsky, 0 points, 0 comments]
- Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation https://lobste.rs/s/qjdakc #pdf #compsci [bsky, 0 points, 0 comments]
- ⚡ Hackernews Top story: Turing Completeness of GNU find [bsky, 0 points, 0 comments]
- Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput https://arxiv.org/abs/2602.20762 [bsky, 0 points, 0 comments]
- Turing Completeness of GNU find https://arxiv.org/abs/2602.20762 (https://news.ycombinator.com/item?id=47147609) [bsky, 0 points, 0 comments]
- "In this paper, we demonstrate that \texttt{find} possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributio [bsky, 0 points, 0 comments]
- 「findはチューリング完全」というarXiv論文がHNで取り上げられてた。find + mkdirと、GNU find単体、find + mkdirその2（構想）、の3とおりの手法。書いたのは日本の人（東大関係？）らしい。 arxiv.org/abs/2602.20762 [bsky, 0 points, 1 comments]
- https://bsky.app/profile/hackernews.com.web.brid.gy/post/3mfobl5xaddx2 [bsky, 0 points, 0 comments]
- Turing Completeness of GNU find [bsky, 0 points, 0 comments]
- Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput #HackerNews https://arxiv.org/abs/2602.20762 [bsky, 0 points, 0 comments]
Related