So if i'm getting this, they initialise find in some kind of infinite looping state using its own parameters to create and nest directories, and define a halting state from whether it reaches the max number of nested directories where find quits.
Only read the abstract, but if as I suspect it is using nested directories as "cells" in the "tape", the proof will require directories to be able to nest arbitrarily deep (which maybe some filesystems already permit; but even if all existing filesystems have some finite limit, this would not be considered an obstacle to the result, since it's certainly possible to construct a filesystem where directory nesting level is limited only by storage size). That's because it needs to be able to simulate a Turing Machine, which could read and write an infinite amount of storage.
Then, there just needs to be a way to force find to stop in some finite amount of time -- that's the halting state. I don't know what mechanism they use for that, but if I were trying to do this, I would lean towards looking for a way to make it error out.
I don’t think most modern file systems have any limit to the depth of nested directories, that’s not how directory trees work. There are other limits like the number of objects in the file system. The ability to reference an arbitrary path is is defined by PATH_MAX, which is the maximum string length. You can still access paths longer than string length, just not in a single string representation.
If you upload to arxiv, there are explicit instructions which tell you what latex commands work and which don’t for the abstract. The authors didn’t read those instructions.
The fact that they found three independent paths to Turing completeness is what makes this paper fun. Even removing regex back-references doesn't kill it.
At some point you start wondering if there's any tool with conditionals and some form of persistent state that ISN'T Turing complete. The bar seems way lower than most people assume. Reminds me of the mov-is-Turing-complete result from a few years back.
For a TM, you nees the ability to write and read in some kind of list and a finite state automata that is driven by what’s in the list. The bar is very low.
This reminds me of the classic results showing Turing completeness of things like sendmail.cf and CSS+HTML. The trick of using directory nesting depth as a counter is clever — it essentially turns the filesystem into a tape. I wonder if there is a practical upper bound from filesystem limits (e.g. PATH_MAX) that would make this more like a bounded automaton in practice.
So if i'm getting this, they initialise find in some kind of infinite looping state using its own parameters to create and nest directories, and define a halting state from whether it reaches the max number of nested directories where find quits.
I didnt understand the encoding part
Only read the abstract, but if as I suspect it is using nested directories as "cells" in the "tape", the proof will require directories to be able to nest arbitrarily deep (which maybe some filesystems already permit; but even if all existing filesystems have some finite limit, this would not be considered an obstacle to the result, since it's certainly possible to construct a filesystem where directory nesting level is limited only by storage size). That's because it needs to be able to simulate a Turing Machine, which could read and write an infinite amount of storage.
Then, there just needs to be a way to force find to stop in some finite amount of time -- that's the halting state. I don't know what mechanism they use for that, but if I were trying to do this, I would lean towards looking for a way to make it error out.
I don’t think most modern file systems have any limit to the depth of nested directories, that’s not how directory trees work. There are other limits like the number of objects in the file system. The ability to reference an arbitrary path is is defined by PATH_MAX, which is the maximum string length. You can still access paths longer than string length, just not in a single string representation.
Quite interesting, and arxiv seems to have some issues handling \texttt{find}.
If you upload to arxiv, there are explicit instructions which tell you what latex commands work and which don’t for the abstract. The authors didn’t read those instructions.
To be fair, arxiv makes the experience as annoying as possible.
The arctic submission process clearly shows you how the abstract will look. The authors likely didn't care.
As always, the real benchmark will be the ability to run Doom.
Doom Complete
Can Find and Mkdir write to any kind of graphical output? And take any kind of input?
you may be able to create dirs as input, and watch some others as output
We should run Doom on it, then.
The fact that they found three independent paths to Turing completeness is what makes this paper fun. Even removing regex back-references doesn't kill it.
At some point you start wondering if there's any tool with conditionals and some form of persistent state that ISN'T Turing complete. The bar seems way lower than most people assume. Reminds me of the mov-is-Turing-complete result from a few years back.
For a TM, you nees the ability to write and read in some kind of list and a finite state automata that is driven by what’s in the list. The bar is very low.
This reminds me of the classic results showing Turing completeness of things like sendmail.cf and CSS+HTML. The trick of using directory nesting depth as a counter is clever — it essentially turns the filesystem into a tape. I wonder if there is a practical upper bound from filesystem limits (e.g. PATH_MAX) that would make this more like a bounded automaton in practice.