Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput
6 hours ago
- #GNU find
- #Unix commands
- #Turing completeness
- The Unix command `find` is demonstrated to have unexpected computational power.
- Three Turing completeness results are established using GNU `find`:
- 1. `find` + `mkdir` is Turing complete by simulating 2-tag systems.
- 2. GNU `find` 4.9.0+ alone is Turing complete by simulating a two-counter machine.
- 3. `find` + `mkdir` without regex back-references is still Turing complete.
- The findings highlight hidden complexity in standard utilities like `find`.