Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
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.
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.
