✳flâneur — a map of the web's best reading

`find` + `mkdir` is Turing complete

ogiekako.vercel.app · 1,522 words · saved by 1 readers

It is well known that the sed and awk commands are Turing complete on their own, but I could not find any reference of find + mkdir being Turing-complete. The proof leverages a common technique: showing the system can execute Rule 110. We will look at the implementation of a loop, FizzBuzz, and the Rule 110 in this order. The following code recursively creates directories and enters an infinite loop: find x lists files under x, including x. When x is listed, it runs mkdir to create x/x, and then it's included in the next find iteration, leading to the creation of x/x/x, and so on. To limit the depth of directory creation, we can employ the -maxdepth option: This code will terminate after creating x/x/x/x/x. Replacing 3 3 with 𝑁 N will result in the 𝑁 + 2 N+2 levels of x directories. The -regex option of find allows you to filter filenames that will be subject to subsequent actions. Using this, we can filter out the x/s with multiples of 3, 5, and 15, and by combining this with a l

`find` + `mkdir` is Turing complete ← Home find + mkdir is Turing complete Japanese version (日本語版) Update history 2026-05-24 The paper Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation has been accepted to FUN with Algorithms 2026 . ( slides ) 2024-08-02 Fixed a proof error that existed in the first version. The first version claimed to have shown Turing completeness by implementing Rule 110, but there was an issue that it cannot handle an unbounded number of iterations. The current version implements the Tag system instead of Rule 110, and the issue should h

Explore this link on the map →

saved by

related reading