find plus mkdir Is Turing Complete

find + mkdir is Turing complete (retracted) The proof is flawed and I retract the claim that I proved that find + mkdir is Turing complete. See https://news.ycombinator.com/item?id=41117141. I will update the article if I could fix the proof. Japanese version (日本語版) Overview We show that a system that has only GNU's find and mkdir commands is Turing-complete. 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. References https://manpages.org/find https://manpages.org/mkdir

A browser window shows a technical article titled “find + mkdir is Turing complete,” followed by a retraction explaining that the proof is flawed. The joke is that even simple Unix commands unexpectedly turn out to have Turing-complete computational power, making this a reaction to absurdly complicated or overpowered software behavior. EN: A browser window shows a technical article titled “find + mkdir is Turing complete,” followed by a retraction explaining that the proof is flawed. The joke is that even simple Unix commands unexpectedly turn out to have Turing-complete computational power, making this a reaction to absurdly complicated or overpowered software behavior.

• @ithueti / 13667 2024-08-01