Turing Completeness of GNU find

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

Quite interesting, and arxiv seems to have some issues handling \texttt{find}.

We should run Doom on it, then.

As always, the real benchmark will be the ability to run Doom.

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.

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.