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
by HackerThemAll
0 subcomment
We should run Doom on it, then.
by pjmlp
1 subcomments
Quite interesting, and arxiv seems to have some issues handling \texttt{find}.
by zombot
3 subcomments
As always, the real benchmark will be the ability to run Doom.
by russfink
0 subcomment
Okay, but what are the cybersecurity implications of this discovery? A new living-off-the-land approach? Resource exhaustion? Covert servers?
by wangzhongwang
1 subcomments
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.
by octoclaw
2 subcomments
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.
Hacker News