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.
But will it run Doom?
So … how long till some runs doom with it?
Why isn’t there a command to create dir and step into it at the same time?
Why is mkdir longer than needs to be (md).
Now I cannot unthink this Zoe!
Why DOESN’T it drop me into that new folder?
On the other, I just make a md link to mkdir. (Because rd)
In Unix terms, the current working directory is a state variable of each process. If `mkdir` is an executable, it gets its own process and a copy of the parent process’s state. Thus, `mkdir` could change its own working directory or other state all it wants but it can’t change the parent’s state. All processes follow that paradigm. You’d need some special unusual agreement between child and parent to communicate a change, or merge `mkdir` into the shell parent process like `cd` is, and make it really clear how it doesn’t follow the now-50-year tradition.
Just use GW-Basic..
The latest Futurama episode had an ancient Mayan system of data storage using beads on a string, which was read by a futuristic Turing machine. Great math and science trivia gets thrown in, I enjoyed that immensely. Pop culture rarely understands CS
this seems like a good way to detect bugs. makes you wonder if the practice could be applied to the kernel.
This is kind of clever, but by the time you introduce “-exec” and “egex support, you’ve kind of conceded the game.
This is beautiful.
And it has a halt, unlike 110 as I understand it.
It’s pretty wild how many combinations of computation elements are Turing complete.