10 ms·
`find` + `mkdir` is Turing complete
- deleted 2y ago[deleted]
- XorNot 2y agoNeat now we just need a compiler for a scripting language...
- behnamoh 2y agoWhat's the implication of this for users of these commands?
- langcss 2y agoNot much practically other than watch out for non-terminating find queries.
- PokestarFan 2y agoI mean I had never thought about the case where the command that find executes creates subfolders of the directory it's executed in.
- aabhay 2y agoI thought that this was going to use some interesting form of lambda calculus but instead it simply relies on the regex parser of find to compute things.
- userbinator 2y agoNot the first time someone has coerced a regex into doing some nontrivial computation; here's a memorable example: http://realgl.blogspot.com/2013/08/battlecode.html http://realgl.blogspot.com/2013/08/battlecode.html (scroll down to "Regular Expression Pathfinding"
- usr1106 2y agoOf course no implementation is infinite, but in this case PATH_MAX with 4096 as a typical value seems particularly low.
- Arch-TK 2y agoThe blog post addresses this by using relative paths. Tested up to a path length of 30k apparently.
- omoikane 2y agoI believe somewhere after 30k is when they will run into file system limits. Despite being able to create directories nested to arbitrary depth with short file names, find() might not be able to read a directory if the total path length is too long. I found this out when I couldn't open a file with the path "./././name.h" where there are lots of "./" in front. And the reason why I got so many "./" was due to a clang preprocessor bug that modifies __FILE__: https://github.com/llvm/llvm-project/issues/43825 https://github.com/llvm/llvm-project/issues/43825
- Bootvis 2y agoCheck out section “Expected questions and answers”. For GNU it seems to work with path lengths larger than 4096.
- peter_d_sherman 2y agoObservation: Any piece of software/service or piece of software/service used in a software/service chain which implements and/or consumes Regular Expressions (aka RE's, RegExp's) -- is potentially Turing Complete, and should be audited for Turing completeness if security in that context is a concern...
- acchow 2y agoSpeaking strictly, the original definition of Regex required only a finite state machine with zero stacks. You need 2 stacks for Turing completeness. Tho a lot of regex libraries can support much more than just “regex”
- peter_d_sherman 2y ago>"You need 2 stacks for Turing completeness." I am not completely sure about that assertion... We know that Rule 110 is Turing complete: https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 >"Rule 110 with a particular repeating background pattern is known to be Turing complete.[2]" So if Rule 110 = Turing completeness, then we could either prove Turing completeness by proving Turing completeness OR we could prove Turing completeness by proving Rule 110 equivalence... Next we have Markov algorithms: https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm >"a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete , which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation." (Note that Markov algorithms do not use stacks (nor do Turing machines, nor does Rule 110, nor do stackless "Turing tarpit" esoteric languages, nor does Langton's Ant or other Turing complete cellular automata).) RegExp's are basically a "string rewriting system that uses grammar-like rules to operate on strings of symbols" So if a such a string rewriting system used in conjunction with a Regular Expression functionality can be proved to be a Markov algorithm, then we have automatic proof that it is also Turing complete, with no need for stacks! Why not read the following: Simplest Turing-complete ruleset for Markov algorithm https://cs.stackexchange.com/questions/44717/simplest-turing-complete-ruleset-for-markov-algorithm https://cs.stackexchange.com/questions/44717/simplest-turing... And possibly this: https://esolangs.org/wiki/Nopfunge https://esolangs.org/wiki/Nopfunge >"Nopfunge is a fungeoid designed by Hubert Lamontagne in 2015. It is a two-dimensional esoteric programming language based on a severely restricted subset of the well known Befunge language. Its goal is to show that having access to a sufficiently flexible program geometry is indeed the only thing that is needed to achieve Turing completeness." [...] >"The ONLY valid commands in Nopfunge are the PC direction change commands < > v ^ and empty space (which are the same as in Befunge). This means that Nopfunge has no stack, no numbers and no conditionals: there are NO stack manipulation commands and NO commands to store or retrieve data from the program grid. There are no variables or data storage or functions or objects of any kind. The ONLY thing that ever happens in Nopfunge is PC movement. In spite of this, Nopfunge is Turing complete." Point is: If it were me, and I were designing a system, then I'd be highly careful (perhaps "circumspect" is a better word) about code that implements or evaluates, produces or consumes Regular Expressions (or implements any text rewrite rules for that matter!) if the system which that code was to be part of, was intended to be as secure as possible...
- adrian_b 2y agoI have found interesting this in the parent article: "The proof leverages a common technique: showing the system can execute Rule 110." because I was not aware about "Rule 110". Nevertheless, reading the Wikipedia page about "Rule 110", I find it astonishing that "Rule 110" not only has been the subject of a research paper, but that paper has been even the ground for a legal affair based on a non-disclosure agreement with Wolfram Research, which has blocked the publication of the paper for several years. The demonstration that "Rule 110" is capable of universal computation is completely trivial and it requires no more than a sentence. It cannot be the subject of a research paper of the last decades. There are several known pairs of functions that are sufficient for computing any Boolean functions, for example AND and NOT, OR and NOT, OR and XOR, AND and XOR. The last pair is a.k.a. multiplication and addition modulo 2. Whenever there is a domain where all the possible functions can be expressed as combinations of a finite set of primitives, it is also possible to express all the members of the finite set of primitives by using a single primitive function that combines all the other primitives in such a way that composing that function with itself in various ways can separate each of the original primitives from the compound primitive. Applying this concept to Boolean functions it is possible to obtain various choices for a single primitive function that can generate all Boolean functions, for instance NAND, which combines NOT and AND or NOR, which combines NOT and OR. In general all the ado about how various kinds of computational domains can be reduced to a single primitive function is not warranted and it is not interesting at all. The reason is that such combined primitives do not change in any way the actual number of primitives. They just replace N distinct simple primitives with 1 compound primitive that must be used in N distinct ways. This does not change in any way the complexity of the domain and it does not make it easier to understand in any way. "Rule 110" is just another banal example of this technique. Like NAND combines NOT and AND in a separable way, "Rule 110" combines multiplication and addition modulo 2, a.k.a. AND and XOR, in a separable way. Therefore it can express any Boolean function, therefore, by encoding, also any computable function. There is absolutely no advantage in showing that some system can compute "Rule 110". It is simpler and clearer to show that it can compute AND and XOR, or AND and NOT.
- eigenket 2y agoAs far as I can tell from your comment you have the terms "functional complete" and "Turing complete" confused. These are emphatically not the same thing. A circuit of (e.g.) NAND gates defines a mathematical function over a fixed, finite number of variables (the number of input wires to your circuit) and with a fixed number of outputs (likewise the output wires). A Turing complete computer accepts inputs which are unbounded in length, I.e. it accepts an input of at least length n for any natural number n. It can also output unbounded strings. These two are fundamentally completely different. Functional completeness for a set of gates doesn't tell you much about Turing completeness. For all of the interesting stuff to do with Turing machines you need this unbounded input size so you can do things like consider descriptions of other Turing machines as inputs to your Turing machine. Essentially what you need is something equivalent to looping or recursion. Note that the Halting problem is completely trivial for NAND circuits, exactly because there is no looping.
- zmmmmm 2y agowell, it also supports `-exec` so it would imply rather a big problem with the host OS if that wasn't turing complete
- kachnuv_ocasek 2y agoWhy would an OS need to be Turing complete?
- eru 2y agoYes, that wouldn't necessarily be a problem. Of course, getting a computer that's useful in practice out of this would require some thought. A simple model: you could only allow programs written in Coq (or similar), ie progams that come with a proof of termination (or a slight generalisation, that allows for infinite event loops, as long as each run threw the loop behaves well, in some sense). There's a trivial escape hatch, where you just take your normal unproven program but forcefully terminate it after 2^64 steps. That's strictly speaking not Turing complete, but you wouldn't be able to tell the difference during the lifetime of the computer.
- niederman 2y agoI suspect this proof could be greatly simplified by the use of tag systems (https://en.m.wikipedia.org/wiki/Tag_system https://en.m.wikipedia.org/wiki/Tag_system) rather than cellular automata.
- deredede 2y agoI don't understand how this shows Turing completeness. The implementation of the rule 110 automaton seems to be limited by both width (not Turing complete because there is a finite number of states of a given width) and iteration limit (not be Turning complete because it always terminates). Can you write an implementation of rule 110 with arbitrary (i.e. unbounded) width and depth?
- viraptor 2y agoIt's still ok if the implementation limits it rather than the concept. I mean, your computer has finite memory rather than infinite tape, so it doesn't meet that requirement either regardless of language/method.
- deredede 2y agoI am not talking about limitations of find or mkdir like other commenters are. I can write a Python program that simulates rule 110 with unbounded state width and unbounded iteration depth. I might not be able to execute it on any computer (it's going to run out of memory at some point), but I can still reason about it and its behavior with a (theoretical) infinite memory. After reading the blog post, I am not convinced I can write such a program using `find` and `mkdir`, since the provided example uses explicit limits for WIDTH and ITER in the program itself.
- camel-cdr 2y agoThe same argument would make C non turing complete. Because the size of pointers is a compile time constant and because everything needs to have an address that puts a large, but hard limit on tape length. There are ways to argue arround that, e.g. C might be able to interface with a infinite tape file via the stantard library, and maybe strict aliasing and pointer provenance let's you create a system where bit identical pointers can be different. But the mental model most people have of C wouldn't be turing complete.
- tomsmeding 2y ago
- vanderZwan 2y agoSo can you implement Folders with it? https://www.danieltemkin.com/Esolangs/Folders/ https://www.danieltemkin.com/Esolangs/Folders/
- Moosturm 2y agoThis is phenomenal
- dspillett 2y ago> In Windows, folders are entirely free in terms of disk space! For proof, create say 352,449 folders and get properties on it. To be that guy for a moment: well, hackchewally…¹ Directory entries do take up space in the MFT, but that doesn't show up in explorer which is only counting allocated blocks elsewhere. You will eventually hit a space issue creating empty directories as the MTF grows to accept their allocation. You can do similar tricks with small files. Create an empty text file and check, it will show 0 bytes size and 0 bytes on disk. Put in ~400 bytes of text and check again: explorer will show 400 bytes in length but 0 size on disk because the data is in the directory entry in the pre-allocated MFT. Double up that data, and it will be big enough that a block on the disk is allocated: in properties in Explorer you'll now see 800 bytes length and 4,096 bytes (one block) on disk. Drop it back to 400 bytes and it won't move the data back into the MFT, you'll now see 400 bytes length, 4096 bytes consumed on disk. -- [1] though don't let this put you off enjoying the splendid thing overall!
- lelandfe 2y agoMaster File Table
- vanderZwan 2y agoRemember that esolangs are arguably the "purest" medium of artistic expression for programming, and that artworks often are about challenging or confronting implicit assumptions. Or to put it differently: yes, that is indeed the joke :). Thank you for elaborating the technical details though (plus I did not know the small file trick, that's a neat bit of trivia).
- 2y ago
- indigo0086 2y agoRetracted >The proof is flawed and I retract the claim that I proved that find + mkdir is Turing complete
- marvinborner 2y agoI believe that if you could also move and link files, you could actually simulate lambda calculus with a similar technique. I imagine something like this would work, where applications are described by shared prefix in same directory depth and order of application is encoded in lexicographical name order: λx.x: $ tree . . └── x └── a -> ../x/ λsz.(s (s (s z))): $ tree . . └── s └── z ├── a -> ../../s/ ├── b -> ../../s/ ├── ca -> ../../s/ └── cb -> ../z/
- IncRnd 2y agoFrom the top of the page: find + mkdir is Turing complete (retracted) The proof is flawed and I retract the claim that I proved that find + mkdir is Turing complete. See https://news.ycombinator.com/item?id=41117141 https://news.ycombinator.com/item?id=41117141. I will update the article if I could fix the proof.
- ogiekako2 2y agoIt's already fixed.
- nibbula 2y agoMy find is not only provably Turing complete, but not even a Turing tarpit and compiles to native code.