Abstract page for arXiv paper 2602.20762: Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation

Hacker News is a community-driven platform for sharing and discussing technology news, startups, and programming-related topics. Through user submissions and comments, Hacker News offers insights into emerging technology trends, industry developments, and entrepreneurial ventures. Readers can participate in discussions, share their insights, and stay informed about the latest advancements in technology and innovation.

Hacker News

A research paper proves that GNU `find` is Turing complete through three distinct results: (1) `find` combined with `mkdir` is Turing complete by encoding computational states as directory paths and using regex back-references to simulate 2-tag systems; (2) GNU `find` 4.9.0+ alone is Turing complete by reading/writing files during traversal to simulate a two-counter machine; (3) `find` + `mkdir` without regex back-references is still Turing complete by encoding regex patterns directly into directory names. These findings place `find` among the class of 'surprisingly Turing-complete' systems, revealing unexpected computational power hidden in a ubiquitous Unix utility.

[2602.20762] Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation