13 ms·
A proof that Unix utility sed is Turing complete
- kccqzy 8y agosed really is a powerful utility. I once wrote a tool in sed that strips HTML tags leaving just plain text as a fun exercise. Naturally it can't handle complicated cases but for many simple use cases it works. The code, though, is basically unreadable.
- airstrike 8y agoAny chance you could share that? Wouldn't mind giving it a whirl in this one side project I just started...
- james_s_tayler 8y agoI used to write web scrapers with curl/grep/sed back in the day. Fun times.
- saagarjha 8y agoGiven that sed is Turing complete, I'm sure if you tried harder you would have come up with a general solution ;)
- mannykannot 8y agoAbsolutely. One approach would be to take this TM implementation and program it to parse HTML.
- mirimir 8y agoIsn't it more or less a cliche that using sed etc for stripping HTML tags is unreliable and potentially hazardous? I've tried it. I could get it to apparently "work". But then I'd get some input that hosed it. Now I just use "w3m -dump". I mean, it's a browser.
- mannykannot 8y agoThe unreliability follows from it being "basically unreadable", which leads to it probably not doing what you intend. Whether it is hazardous depends on what you use it for.
- noxToken 8y agoThere's the classic Stack Overflow answer[0] about matching HTML tags. If you have a small subset of HTML, it can work out pretty well. [0]: https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 https://stackoverflow.com/questions/1732348/regex-match-open...
- mirimir 8y agoThanks. That's what I was thinking of. Classic "this parrot is dead" riff.
- somacert 8y agosed -e 's/<[^>]*>//g'
- clanrebornsx 8y agoIsn't this the same racist guy who once made a WhatsApp kiosk and was surprised why it's getting popular among the people who really need it.
- voltagex_ 8y agoI vouched for this because even though it's somewhat misguided, I want to know how this person came to this conclusion. This is the event referenced: https://scroll.in/magazine/864603/desperate-for-whatsapp-tens-of-thousands-of-indians-with-cheap-phones-flood-a-us-coders-website https://scroll.in/magazine/864603/desperate-for-whatsapp-ten... He was unintentionally DDoSed. He made it right. What's the problem?
- fouc 8y agoInteresting article! He definitely came across as incredibly ignorant about India in the beginning, and started out with a negative viewpoint. Ultimately he finally figured out what was going on and corrected his views, and was finally able to help indians use whatsapp from their JIO phones. He was almost too honest in the article, since it kind of makes him look bad. But I appreciate that honesty.
- justwalt 8y agoI don’t think he was negative at all. I think his response was one that most everyone would have had. What do you think he could have done better?
- mises 8y agoHow was what he did racist?
- solarkraft 8y agoOh, the Cross-Browser-Testing-Tool-Abused-As-WhatsApp-Proxy guy! Good catch, nice!
- nickdrozd 8y agoHere's a simple infinite loop in sed: echo loop | sed -e ':x' -e 'p ; bx'
- fouc 8y agoThis article was submitted before in 2012. It was recently updated. from 7 years ago: https://news.ycombinator.com/item?id=3855616 https://news.ycombinator.com/item?id=3855616
- wilsonrocks 8y agoHas anyone written a kind of Turing machine gateway API, where people write an adaptor to the API and you can then use the gateway to use any Turing machine backend to run any other(Turing complete) program. Would be interesting to see e.g. how fast Microsoft Word runs on a sed based backend.
- User23 8y agoThis that you describe is essentially a Universal Turing Machine.
- afiori 8y agoYes, but it should be noted that a sed-interpreted word would also need to emulate the OS and the hardware, as I imagine that the syscall you can make from sed are limited
- Quekid5 8y agoThere's been a very weird discussion going on here based on the misconception that TMs are somehow equivalent to Interactive TMs[1]. In the usual theory of TMs there's no idea that there's "input" (e.g. another TM altering the tape) or anything similar. You just give it a starting position and the initial state of the tape and let it go. [1] https://en.wikipedia.org/wiki/Interactive_computation https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)
- daveFNbuck 8y agoYou're basically describing compilers. Microsoft Word probably wouldn't run on sed because it requires things outside of the capabilities of a Turing machine, like being able to produce a GUI.
- ascar 8y agoConsidering a GUI runs on a turing machine, how is it outside the capabilities of one? Isn't everything we do on computers exactly within the capabilities of a turing machine and just about the ingenuity to create a program that does what we want and about its efficiency? In other words, if sed is turing complete, this means you could run any other turing complete program on it. Producing a GUI is also just telling your CPU (a sophisticated turing machine) to format data and how to send the formated data to a display. EDIT: what justifies the downvotes? Sure the display is not part of the turing machine, but the display is also not part of the GUI. The GUI is a software component that can be created by a turing machine. You wouldn't disagree with me for stating a GUI can be created through a C or Java program.
- samat 8y agoIn a course on algorithms I took in Moscow State Uni (Russia), we were told there are two ways to describe a Turing machine: - One with a tape & state transition table - A string & a list of string replacements Then we proved this two definitions being equal. And programmed for each ‘system’ a little. I must admit, programming with ‘string replacements’ is much much more fun than doing ‘tape & table’. Is this just some Russian quirk or the same in the West CS courses, too?
- schoen 8y agoI think the other formalism you're talking about is https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm There are a number of different models of universal computation that were formulated in the 1930s or soon afterward and can all be proven to be equivalent in power. In CS courses in the U.S., people might learn about more than one of these and also prove that they're equivalent. But only the one with the tape and symbols is referred to as a "Turing machine" here; the other ones might be called "computation models", "computation formalisms", or something similar. I don't think that the string-rewriting model is as commonly taught over here, although I'm sure it's alluded to in discussions of rewriting in formal grammars https://en.wikipedia.org/wiki/Rewriting https://en.wikipedia.org/wiki/Rewriting Interestingly, the Markov who devised this model of computation is apparently the son of the Markov who studied Markov chains and Markov processes.
- throwawayRO12 8y agoYou are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
- abhishekjha 8y ago>prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming) Is there a text which guides how to write such a proof?
- gammateam 8y agoWhy is Turing completeness important to anyone? Asking for a friend
- erfgh 8y agoIt is if you can make a paper out of it and increase your publication count.
- maxiepoo 8y agoI highly doubt that you can get a paper at any respectable conference or journal showing something is Turing Complete.
- Zarath 8y agoAsk all the c++ metaprogramming people :)
- cyborgx7 8y agoHere is the (overly) simple explanation: Something being Turing complete means that it can compute anything that can be computed.
- gammateam 8y agoI asked why it was important to anyone, not what it was why is this glorified
- dwrodri 8y agoFrom the security point of view, it means that it can be used execute code from user space. Just about anything that's Turing complete should be on someone's list of potential attack vectors.
- gammateam 8y agoYes, I agree Why is it glorified? Unless all these researchers are really just intentionally giving code word to hackers for a target to exploit or weaponize, but it doesn't really seem like thats the point with these people.
- gonzo41 8y agoIt's not turing complete until someone writes a ray tracer in it!
- easytiger 8y agohttp://funarg.nfshost.com/r2/code/sed/ray/ray.sed http://funarg.nfshost.com/r2/code/sed/ray/ray.sed
- darkkindness 8y agoA 1592-line sed script (incl. comments and blank lines) written in 2005. Most of it defines math functions as well as structures like lists, and there is a hardcoded POW10 function for binary strings, but each section is well commented, and I see optimizations and explanations of optimizations. It seems to output PostScript? That's insane...
- dahart 8y agoTotally crazy. It's helpful to browse up on directory in the URL, then you can see the project page: http://funarg.nfshost.com/r2/code/sed/ray/ray.html http://funarg.nfshost.com/r2/code/sed/ray/ray.html
- otabdeveloper1 8y agoBasically, anything that can recurse is Turing-complete.
- klmr 8y agoNo. Only anything that can perform µ-recursion is Turing complete. Primitive recursion [1] is not enough. In practice virtually all languages that allow recursion allow its Turing complete form but it’s important to realise that other forms exist. [1] https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function
- deytempo 8y agoIt fascinates me how few people can or are willing to explain concepts of computer science without using formal mathematical notational explanations. When asked, often they will say “that’s the only/best way to explain it” then I go and spend a few hours translating said concept from the formal math notational mess, finding that it’s indeed quite possible to explain it simply and even elegantly in either natural language or just a pseudo code example.
- norswap 8y agoCould you give an example of primitive recursion that is not µ-recursion?
- OskarS 8y agoEvery primitive recursive function is also µ-recursive: the primitive recursive functions are a subset of µ-recursive functions. But the converse is not true: there are µ-recursive functions that are not primitive recursive. The canonical example is the Ackermann function. It can be shown that it grows faster than all primitive recursive functions, and is thus in itself not primitive recursive. Since the Ackermann function is obviously computable, and easily computable by a Turing machine, this implies that the primitive recursive functions are not Turing complete, and thus more limited than the µ-recursive functions.
- 8y ago
- qwerty456127 8y agoI really wish there were more Delphi/VB/WinForms-like visual RAD tools for Linux (Lazarus is just a way too primitive, I've tried it and it feels like neither the editor nor the language has undergone any improvement since 90es).
- jim_bailie 8y agoAnd I love Lazarus/FreePascal for those very reasons. A simple and very performant tool set that I use quite extensively for a set of mission critical quantitative financial analysis applications.
- deleted 8y ago[deleted]
- Grue3 8y agoAnd that's a bad thing. It means not only that some sed programs never complete, but it's not even possible to tell whether any given sed program hangs or not. Not something you want from a text substitution utility.
- eponeponepon 8y agoIf you just want a text substitution utility, then this is proof that you can implement that by using sed in a controlled manner. Why bemoan something for doing more things than you need it to right now? This is what general-purpose computing is all about.
- Toenex 8y agoI do like the thought experiment that I might not want Turing completeness from a language in a specific use case.
- jhanschoo 8y agoNo, it's not possible to tell if arbitrary programs hang. But it is possible to tell if a program is of a restricted form that is known to terminate. This is how we know the many standard algorithms we frequently use terminate.
- ben0x539 8y agoNever in my life have I been more concerned about whether a simple text substitution is going to halt than whether I can write it down reasonably concisely without having to resort to a more powerful scripting/programming language.
- dahart 8y agoOut of curiosity, have you ever been concerned to have a guarantee whether any program you’ve written or run would finish, regardless of run time? The halting problem is an abstract theoretical result that I’ve personally never been concerned about, in any language at all. Not even once in practice in 30 years of coding have I worried that I didn’t know whether a correct bug-free program would finish. I worry that programs take too long all the time, but that’s completely separate from the halting problem. If sed is a “bad thing”, just understand that string replacement is a “bad thing” and computers are a “bad thing”. There isn’t an alternative to doing any real computation without having Turing completeness.