Research Paper: Turing Completeness of GNU find Command - Three Computational Power Results
By
todsacerdoti
A weekday bagel. Dependable, satisfying, no fuss.
Summary
This academic paper demonstrates that the GNU find command, a standard Unix utility, possesses unexpected computational power and is Turing complete. The research establishes three specific Turing completeness results: (1) find + mkdir can simulate 2-tag systems by encoding computational states as directory paths, (2) GNU find 4.9.0+ alone can simulate a two-counter machine without mkdir, and (3) find + mkdir without regex back-references remains Turing complete through clever encoding techniques. The findings place find among other 'surprisingly Turing-complete' systems, revealing hidden complexity within simple standard utilities.
Key quotes
· 4 pulledThe 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.
\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.
These results place \texttt{find} among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.
You might also wanna read
Research Shows All 23-Bit Still Life Patterns in Conway's Game of Life Are Glider Constructible
The article discusses research in Conway's Game of Life about which still life patterns can be constructed by colliding gliders. It explains
mvr.github.io·4mo ago
GitHub Repository Claims Solution to Navier-Stokes Millennium Prize Problem Using Limit Functional Theorem and LLM Collaboration
A GitHub repository claims to present a solution to the Navier-Stokes Clay Math Millennium Prize Problem using a theorem about extending lim
github.com·5mo ago
KC Sivaramakrishnan's Upcoming Academic Talks on Programming Languages and Computer Science Research
This content appears to be a list of upcoming or recent academic talks and presentations by KC Sivaramakrishnan, focusing on programming lan
kcsrk.info·8mo ago
Introduction to Detached Point Arithmetic (DPA) for Exact Numerical Computation
The article introduces Detached Point Arithmetic (DPA), a method for exact numerical computations by separating integer mantissas from their
github.com·10mo ago
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky