Turing Completeness of GNU find(arxiv.org)
135 pointsby todsacerdoti3 days ago7 comments
  • tetris113 days ago
    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

    • akoboldfrying3 days ago
      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.

      • jonhohle2 days ago
        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.
        • tasty_freeze2 days ago
          Isn't there a max filepath length? Or does find not ever deal with that and just deal in terms of building its own stack of inodes or something like that?
          • jonhohle2 days ago
            That’s what PATH_MAX is. It’s the size of the buffer used for paths - commonly 4096 bytes. You can’t navigate directly to a path longer than that, but you can navigate to relative paths beyond that (4096 bytes at a time).
  • HackerThemAll3 days ago
    We should run Doom on it, then.
  • zombot3 days ago
    As always, the real benchmark will be the ability to run Doom.
    • TZubiri2 days ago
      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.

    • ape43 days ago
      Doom Complete
    • voidUpdate3 days ago
      Can Find and Mkdir write to any kind of graphical output? And take any kind of input?
      • yehoshuapw3 days ago
        you may be able to create dirs as input, and watch some others as output
  • pjmlp3 days ago
    Quite interesting, and arxiv seems to have some issues handling \texttt{find}.
    • Jaxan2 days ago
      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.
      • suddenlybananas2 days ago
        To be fair, arxiv makes the experience as annoying as possible.
        • emil-lp2 days ago
          The arctic submission process clearly shows you how the abstract will look. The authors likely didn't care.
  • russfink2 days ago
    Okay, but what are the cybersecurity implications of this discovery? A new living-off-the-land approach? Resource exhaustion? Covert servers?
  • wangzhongwang3 days ago
    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.
    • chriswarbo2 days ago
      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?)
  • octoclaw3 days ago
    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.

    • FergusArgyll2 days ago
      This llm has 147 karma, incredible
      • ok1234562 days ago
        LLM yet, and seems to have the most insightful comments here about the paper.
        • russfink2 days ago
          Sorry for the novice question, but how do you determine this is AI?
          • mistrial92 days ago
            the only submission from that 8 day old account is about OpenCLAW dot ai
          • ok1234562 days ago
            *claw and recently registered
    • skydhash2 days ago
      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.
      • chriswarbo2 days ago
        Turing's "On Computable Numbers" paper is credited with inventing the Universal Turing Machine; but really it lays out many remarkable things:

        - Undecidability: that there are mathematical/logical questions whose answers cannot be calculated by any (formal/logical/physical) system

        - Universal computation: there exist systems which can answer all decidable questions

        - Universal Turing Machine: an incredibly simple example of such a universal system

        Of course, these are inter-related and inevitable (otherwise they wouldn't be provable!); but at first glance it feels like these could have gone either way: Maybe all questions could be calculated, given sufficient cleverness (as Hilbert expected)? Maybe different systems would be required for different sorts of question? Maybe a universal system would be too outlandishly elaborate to make sense in our universe (as existence proofs often are)?

        Yet here we are, discussing multiple ways to perform universal computation with GNU find!