Turing Completeness of GNU find: From mkdir-Assisted Loops to Standalone Computation

In this paper, we establish three Turing completeness results. Given any instance of a known universal computational model, we show how to construct a fixed sequence of commands (an execution in the sense of Definition 1) whose behavior faithfully simulates that instance. Conversely, execution of any sequence of find and mkdir commands on a file system can clearly be simulated by a Turing machine, so we obtain Turing equivalence; however, we focus on the more surprising direction.

1. 1.

   GNU find + mkdir is Turing complete (Section 3): By encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems. We use options added in GNU find 4.2.12, which was released in 2005.

2. 2.

   GNU find alone is Turing complete (Section 4): By reading and writing to files during traversal, we simulate a two-counter machine without mkdir. This construction utilizes the -files0-from option added in GNU find 4.9.0, which was released in 2022.

3. 3.

   GNU find + mkdir without regex back-references is Turing complete (Section 5 (sketch), Appendix A): By a technique of encoding regex patterns directly into directory names, we achieve the same power even without regex back-references.

Our constructions use $O(1)$-length path components (hence do not assume an increased NAME_MAX). In practice, resource limits such as storage capacity, maximum path length (PATH_MAX, typically 4096 bytes), and finite inodes cap the number of simulation steps that can be realized on a given machine.

These results place find among the “surprisingly Turing-complete” systems, highlighting the hidden complexity within seemingly simple standard utilities.

We implement our constructions and confirm them on toy examples (Appendix B).

We restrict our attention to GNU find, because (1) it is standard in Linux distributions, and (2) our constructions rely on options that are GNU extensions. While the options we use for find + mkdir are also found in BSD find (macOS/FreeBSD), subtle runtime differences prevent our constructions from working as-is, though they may work with some modifications.

Table 1 summarizes the Turing completeness results established in this paper.

The question of whether similar computational universality exists in other implementations, such as BSD, BusyBox, and uutils find, remains an intriguing avenue for future research.

The foundation of our constructions is the ability to create an infinite loop using only find and mkdir. To achieve this, we rely on a specific property of find: child directories created during the traversal of a directory become visible and are subsequently visited in the same execution, provided the traversal is pre-order (the default). When find visits a directory $D$ and an action creates a new subdirectory $C$ inside $D$, $C$ is visible to the subsequent directory enumeration and will be visited in the same find execution. While POSIX leaves this behavior unspecified²²2“If a file is removed from or added to the directory hierarchy being searched it is unspecified whether or not find includes that file in its search.” [14], this behavior is consistent across GNU find versions³³3Verified on GNU find 4.10.0 (Debian) and 4.5.11 (CentOS 7)..

The following code implements an infinite loop. In our code snippets, we do not escape characters like ; (e.g., as \;), which is typically required by a shell. This is to signify shell independence. Note that proper escaping is necessary to execute these snippets in a shell.

mkdir x
find x -execdir mkdir {}/x ;

This code creates x, then find visits x and executes mkdir command in the directory . (the parent of x) with the argument ./x/x, because {} is substituted with ./x, that is the relative path of x from . . This creates x/x. Due to the aforementioned property, find then visits x/x, and it then creates x/x/x, and so on indefinitely.

We use -execdir, which was added in GNU find 4.2.12. While strictly speaking our resource model (Definition 2) does not forbid arbitrary long arguments, using -execdir is practically crucial. If we use -exec, find passes the path of the current file to the command. As the directory structure grows deeper, this path eventually exceeds PATH_MAX (typically 4096 bytes), causing mkdir to fail and find to halt. -execdir avoids this by executing the command in the subdirectory containing the current file, allowing us to pass an argument of constant length.

We prove that find + mkdir is Turing complete by simulating a 2-tag system [12]. The following is a definition of a 2-tag system equivalent to the one given by Rogozhin [13].

It is known that 2-tag systems are computationally universal. Specifically, we can simulate an arbitrary 2-symbol $m$-state Turing machine ($\mathrm{TM}(m,2)$) using a 2-tag system. Combining this reduction with the known existence of a universal Turing machine with 18 states and 2 symbols ($\mathrm{TM}(18,2)$) [10], De Mol [9] constructed a universal 2-tag system with 576 symbols ($\mathrm{TS}(576,2)$).

We prove Turing completeness of find + mkdir by simulating an arbitrary 2-tag system, applying the construction to this 576-symbol universal instance. The high-level idea is:

1. 1.

   Encode each tag-system symbol as a two-letter directory name (e.g., /ab), representing the sequence of words as a growing, nested directory path.

2. 2.

   To compute the next word, iteratively copy the remaining suffix of the previous word symbol-by-symbol: use a regex with a back-reference to verify the progress and locate the next symbol, then use -execdir mkdir to append it to the path.

3. 3.

   Once the suffix is fully copied, use regex matching to identify the first symbol of the previous word, and append its corresponding production string to complete the iteration.

We will encode the input word to an ASCII string and decode the halting word from an ASCII string. Since this mapping is straightforward (clearly computable by a deterministic finite state transducer), we omit a formal proof for the validity of the encoding. We use typewriter font to denote string literals, concatenation (written by placing strings next to each other), and $\epsilon$ for the empty string.

Let $\mu =576$, and $\mathrm{\Sigma }=\{s_1,\mathrm{\dots },s_{\mu },s_{\mu +1}=H\}$. We encode each symbol as a directory name: let $A$ be a set of lowercase ASCII letters, and choose distinct strings $s_1^{\prime },\mathrm{\dots },s_{\mu +1}^{\prime }\in A^2$ (possible because ). Define ${\sigma }_k=\text{/}{s}_k^{\prime }$, where / is the directory separator. The encoding of a symbol $s_k$ is thus a three-character string like /ab. We let ${\mathrm{\Sigma }}^{\prime }=\{{\sigma }_1,\mathrm{\dots },{\sigma }_{\mu },{\sigma }_{\mu +1}=\eta \}$ and $\varphi :\mathrm{\Sigma }\to {\mathrm{\Sigma }}^{\prime }$ be a function that maps $s_i$ to ${\sigma }_i$. We also define $\mathrm{\Phi }:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\prime \ast }$ so that $\mathrm{\Phi }(\epsilon )=\epsilon$ and $\mathrm{\Phi }(s_1\mathrm{\cdots }{s}_k)=\mathrm{\Phi }(s_1\mathrm{\cdots }{s}_{k-1})\varphi (s_k)$ for $k\ge 1$. We define $\pi (s_i)=\mathrm{\Phi }(P(s_i))$ for $i\le \mu$.

We first run the following command to embed the initial word $w_1$. We use spaces to separate command arguments, distinguishing them from concatenation.

The idea for the following computation is to iteratively append the file path representing the next word to it using /_ as a separator. During the computation, the working directory should contain exactly one directory _, each of whose descendants is a directory containing at most one directory. We call the path to the empty directory at a point of the computation the state of the system at that point. After the computation halts, the state of the system should be $\text{\_}\mathrm{\Phi }(w_1)\text{/\_}\mathrm{\Phi }(w_2)\text{/\_}\mathrm{\cdots }\text{/\_}\mathrm{\Phi }(w_t)\text{/\_}$, and during the computation the state should be a prefix of it. Let ${\mathrm{\Theta }}_{i,j}$ be the following state. Our initial state is ${\mathrm{\Theta }}_{1,0}$ and the last state will be ${\mathrm{\Theta }}_{t,0}$.

At ${\mathrm{\Theta }}_{i,j}$, if $j=0$ and $w_i$ is a halting word, we stop the computation. Otherwise, (1) if $\varphi (x_{i+1,1})\mathrm{\cdots }\varphi (x_{i+1,j})$ equals $\varphi (x_{i,3})\mathrm{\cdots }\varphi (x_{i,j+2})$ and $x_{i,j+3}$ exists, we append $\varphi (x_{i,j+3})$ to the state, and (2) otherwise (if we have copied the last alphabet of the previous word), we append $\pi (x_{i,1})\text{/\_}$ to the state.

Let the regex pattern $\lambda =\text{/[a-z][a-z]}$. Since [a-z] matches any lowercase ASCII letter but not / or _, $\lambda$ matches exactly the strings in ${\mathrm{\Sigma }}^{\prime }$ (encoded symbols). Let $\mathrm{\Lambda }=\text{(}\lambda \text{)*}$ be a regex that matches any (possibly empty) sequence of encoded symbols. \( and \) are escaped because a backslash before parentheses is required by find’s default regex type (emacs regex). The same applies for \| (OR operator) below. Define the following regex patterns:

We run the following as the second command. Newlines are for readability and have the same meaning as spaces.

Finally we run the following command to output the encoded result.

We show that the output of the last command is $\mathrm{\Phi }(w_t)$ if the original 2-tag system halts with $w_t$, and the second command does not halt if the original does not halt, proving Theorem 3.

The foundation of our constructions is the ability to create an infinite loop using only find. We utilize -files0-from file, which lets find read NUL-separated starting points from a file rather than the command line (where nul is the ASCII null character). find’s -fprintf can write nul to a file provided \0 verbatim. By updating this file while the find command is running, we can supply an infinite stream of starting points, thereby creating a loop.

We first introduce a way of encoding a non-negative integer as a file. Let $\iota =\text{.}\text{nul}$ (a two-byte string). If the content of a file $f$ is the string $\iota$ repeated $n$ times (i.e., $2n$ bytes), we say the value of $f$ is $n$. For example, a file of value 3 contains the 6-byte string .nul .nul .nul. If $f$ does not exist, its value is 0; in other cases the value is undefined. We will use files a, b, s, t and represent their values with $a,b,s,t$ respectively. We use $t$ for temporary storage. We construct our program so that throughout the computation $a,b,s$ are always defined.

Notice that the code like find -files0-from s -prune expr evaluates expr $s$ times, and it exits with non-zero exit code if $s=0$ (s does not exist).

For loop construction, we first initialize $s$ (for stream) with 1.

We define an expression which increments $s$ when evaluated as follows, and call this $\text{inc}(\text{s})$. We similarly define $\text{inc}(\text{a})$ and $\text{inc}(\text{b})$ for later use, in which s is replaced with a or b.

To understand this, remember that the file given to -fprintf is truncated or created to 0 bytes as soon as the find command starts, regardless of whether its predicate ever matches (as documented). Line 1 is evaluated to true if and only if $s\ne 0$. Line 2 (where $s>0$) creates an empty file first (because of -quit, -fprintf is not evaluated). Line 3 updates t with . nul repeated $s+1$ times and removes first (first evaluation matches with both . and ./first, removing first with -delete), effectively meaning $t\leftarrow s+1$. Line 4 updates s with . nul repeated $t$ times ($s\leftarrow t$), and line 5 deletes t ($t\leftarrow 0$). If $s=0$, line 6 updates s with . nul ($s\leftarrow 1$).

The loop is constructed as follows. Remember we start with $s=1$.

This works because GNU find reads s as a stream. When the first . nul is read, find still has not read the EOF (end of file). It then executes $\text{inc}(\text{s})$ to extend the file so that it still has the next . nul, and this process continues indefinitely. The fact that this works depends entirely on the implementation of GNU find, but this has been empirically confirmed on GNU find 4.10.0 and rigorously confirmed to work by reading the source code of GNU find 4.9.0.

The following definition for 2-counter program machine is equivalent to the one given by Minsky [8]. 2-counter program machines are known to be Turing complete.

To simulate 2-counter program with find, we create expressions to simulate the instructions. We have already seen inc expressions. We define the following expression as $\text{dec}(\text{a})$, and $\text{dec}(\text{b})$ analogously.

When the expression is evaluated, it sets $a$ to $\max (a-1,0)$ as follows: Line 1 evaluates to true and deletes a ($a\leftarrow 0$) if and only if $a=1$ (since the file size is 2 bytes, checked via -size 2c). Line 2 evaluates to false if $a=0$. Line 3 (with $a\ge 2$) creates first. Line 4 sets $t$ to $a-1$, which happens as follows: (1) Due to -fprintf t, t exists as an empty file as soon as the find starts. (2) In the first iteration of . from a, because of -delete implying -depth, ./first (being deleted) and ./t are iterated before . and it causes either .skip nul or skip. nul to be written to t. (3) In the following $a-1$ iterations, since first no longer exists, $a-1$ repeat of . nul is appended to t. In line 5, since neither file .skip nor skip. exists, it is skipped with an error message written to standard error (which we do not use), causing -fprintf a .\0 to be evaluated $a-1$ times ($a\leftarrow a-1$). Line 6 deletes t ($t\leftarrow 0$). Line 7 exists to make $\text{dec}(\text{a})$ always true.

The program counter is represented by the file pc, but unlike $a$ and $b$, we directly encode the value $n$ as a string of $n$ ones (ASCII character 1). For example, the program counter being 3 means pc’s content is 111. pc will be initialized to an empty file with find -quit -fprintf pc not-written, and the program counter will always be defined hereafter. Let ${\text{1}}^n$ denote a string of $n$ ones.

We define the expression $\text{j}(q)$ for $q\in \{0,\mathrm{\dots },m\}$ as follows. If an empty string is a concern, we can make it -exec find -quit -fprintf pc x ; for $q=0$. It is clear that it is evaluated to true and sets $\mathrm{pc}$ to $q$.

We define the expression $\text{jz}(\text{a},q)$ for $q\in \{0,\mathrm{\dots },m\}$ as follows, and $\text{jz}(\text{b},q)$ analogously. It is clear that $\text{jz}(\text{a},q)$ is evaluated to true and sets $\mathrm{pc}$ to $q$ if and only if $a=0$.

Finally, we define the expression $\text{ispc}(q)$ for $q\in \{0,\mathrm{\dots },m-1\}$ as follows. Unlike other expressions, it assumes the current file is pc, and is evaluated to true if and only if $\mathrm{pc}=q$. $q$ in the code is substituted to the corresponding decimal number represented in ASCII.

The commands to simulate a given 2-counter program $P=(I_0,\mathrm{\dots },I_{m-1})$ and initial configuration $(0,c_0,c_1)$ is as follows. We let ${\gamma }_0=\text{a}$ and ${\gamma }_1=\text{b}$.

Our first command to run is find -quit -fprintf pc x, which initializes $\mathrm{pc}$ to 0. The next command to run is the following, where $\text{inc}(\text{a})$ is repeated $c_0$ times and $\text{inc}(\text{b})$ is repeated $c_1$ times. This initializes $s$, $a$, and $b$ with 1, $c_0$, and $c_1$ respectively.

The next command is the main loop. Let $\varphi$ be a mapping from $\{I_0,\mathrm{\dots },I_{m-1}\}$ to find expressions defined by the following.

The main loop is as follows.

Finally, the following two commands allow us to directly output the value of $a$. The first command writes $a$ 1s to count. The second command outputs the byte count of count, which is $a$.

find -files0-from a -fprintf count 1 -prune
find count -printf %s

We show that by running the above commands from the first to the last, we get the same output as the original 2-counter machine if the machine halts, and it does not halt if the machine does not halt, completing the proof of Theorem 5. It is enough to show that the main loop works as expected.