![proof-that-find-+-mkdir-are-turing-complete-[hackaday]](https://i0.wp.com/upmytech.com/wp-content/uploads/2024/08/201747-proof-that-find-mkdir-are-turing-complete-hackaday-scaled.jpg?resize=800%2C445&ssl=1)
Proof that find + mkdir are Turing-Complete [Hackaday]
Data manipulation is at the heart of computation, and a system is said to be Turing-complete if it can be configured to manipulate data in a way that makes implementing arbitrary computation possible. [Keigo Oka] shared a proof that find and mkdir together are Turing-complete, which is to say, a system with only GNU’s find and mkdir has access to enough functionality to satisfy the requirements of Turing completeness, which ignores questions of efficiency or speed.
[Keigo Oka]’s first attempt at a proof worked to implement Rule 110, an elementary cellular automata configuration that has been shown to be Turing-complete, or ‘universal’, but has been updated to implement a tag system as it’s proof, and you can see it in action for yourself.
Seeing basic utilities leveraged in such a way illustrates how computation is all around us, and not always in expected places. We’ve also seen Turing-complete origami and computation in cellular automata.