I think in this case it's more of a critique than an accolade. If something that isn't supposed to be a programming language is turing-complete/can run doom, then it means, then it means that it has bloated and some features are too complex for the domain specific functionality.
At some point, these tools solve a specific problem not by actually solving it within its constraints, but by implementing a programming language.
E.g:
First act:Dev makes a tool to schedule calendars, clients are happy.
Second act: client asks for capacity to send mail, dev includes capacity to send mail, another client asks for capacity to send texts, dev adds capacity to send texts
third act: client asks for capacity to send slack messages, dev is tired of these custom requests and thus embeds a configurable language with ifs and thens that allows the clients to connect its calendar tool with whatever messaging platform or with whatever they want.
Boom X calendar tool is turing complete, it's not a compliment, it's a failure mode.
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.
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.
They explicitly state that using `-execdir` to change the working directory avoids issues with PATH_MAX; though I didn't see any mention of the working directory itself having a limit (which I assume it does, for Linux processes?)
10 comments
[ 2.7 ms ] story [ 40.9 ms ] threadAt some point, these tools solve a specific problem not by actually solving it within its constraints, but by implementing a programming language.
E.g:
First act:Dev makes a tool to schedule calendars, clients are happy.
Second act: client asks for capacity to send mail, dev includes capacity to send mail, another client asks for capacity to send texts, dev adds capacity to send texts
third act: client asks for capacity to send slack messages, dev is tired of these custom requests and thus embeds a configurable language with ifs and thens that allows the clients to connect its calendar tool with whatever messaging platform or with whatever they want.
Boom X calendar tool is turing complete, it's not a compliment, it's a failure mode.
I didnt understand the encoding part
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.