Proof that find + mkdir are Turing-Complete
![](../themes/icons/grey.gif)
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.