The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that \texttt{find} possesses…
Abstract:The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. 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 distributions). (1) \texttt{find} + \texttt{mkdir} (a system that has only \texttt{find} and \texttt{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 \texttt{find} 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without \texttt{mkdir}. (3) \texttt{find} + \texttt{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 \texttt{find} among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.
Read the original article
Comments
So if i'm getting this, they initialise find in some kind of infinite looping state using its own parameters to create and nest directories, and define a halting state from whether it reaches the max number of nested directories where find quits.
I didnt understand the encoding part
By akoboldfrying 2026-02-2510:431 reply Only read the abstract, but if as I suspect it is using nested directories as "cells" in the "tape", the proof will require directories to be able to nest arbitrarily deep (which maybe some filesystems already permit; but even if all existing filesystems have some finite limit, this would not be considered an obstacle to the result, since it's certainly possible to construct a filesystem where directory nesting level is limited only by storage size). That's because it needs to be able to simulate a Turing Machine, which could read and write an infinite amount of storage.
Then, there just needs to be a way to force find to stop in some finite amount of time -- that's the halting state. I don't know what mechanism they use for that, but if I were trying to do this, I would lean towards looking for a way to make it error out.
I don’t think most modern file systems have any limit to the depth of nested directories, that’s not how directory trees work. There are other limits like the number of objects in the file system. The ability to reference an arbitrary path is is defined by PATH_MAX, which is the maximum string length. You can still access paths longer than string length, just not in a single string representation.
By tasty_freeze 2026-02-2515:581 reply Isn't there a max filepath length? Or does find not ever deal with that and just deal in terms of building its own stack of inodes or something like that?
By jonhohle 2026-02-2522:15 That’s what PATH_MAX is. It’s the size of the buffer used for paths - commonly 4096 bytes. You can’t navigate directly to a path longer than that, but you can navigate to relative paths beyond that (4096 bytes at a time).
By HackerThemAll 2026-02-2510:58 We should run Doom on it, then.
By TZubiri 2026-02-2515:32 I think in this case it's more of a critique than an accolade. If something that isn't supposed to be a programming language is turing-complete/can run doom, then it means, then it means that it has bloated and some features are too complex for the domain specific functionality.
At some point, these tools solve a specific problem not by actually solving it within its constraints, but by implementing a programming language.
E.g:
First act:Dev makes a tool to schedule calendars, clients are happy.
Second act: client asks for capacity to send mail, dev includes capacity to send mail, another client asks for capacity to send texts, dev adds capacity to send texts
third act: client asks for capacity to send slack messages, dev is tired of these custom requests and thus embeds a configurable language with ifs and thens that allows the clients to connect its calendar tool with whatever messaging platform or with whatever they want.
Boom X calendar tool is turing complete, it's not a compliment, it's a failure mode.
By ape4 2026-02-258:16 Doom Complete
By voidUpdate 2026-02-259:421 reply Can Find and Mkdir write to any kind of graphical output? And take any kind of input?
By yehoshuapw 2026-02-259:49 you may be able to create dirs as input, and watch some others as output
