Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A proof that Unix utility sed is Turing complete

catonmat.net

Post reply on HN
Print view View original

71–80 of 109 posts

Re: A proof that Unix utility sed is Turing complete

#71

Post by OskarS »

norswap wrote: post #60
klmr wrote: post #41

Earlier quoted context omitted.

No. 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

Could you give an example of primitive recursion that is not µ-recursion?

Every 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.

Re: A proof that Unix utility sed is Turing complete

#72

Post by zeroonetwothree »

norswap wrote: post #60
klmr wrote: post #41

Earlier quoted context omitted.

No. 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

Could you give an example of primitive recursion that is not µ-recursion?

Primitive recursion is a subset of µ-recursion so there is no such example. I assume you just want an example of primitive recursion.

The term is confusing if you are used to “recursion” in the context of programming. Primitive recursion basically corresponds to programs that don’t use recursion or unbounded loops. For example “compute the factorial of 55” or “sort this input list of at most 10000 integers”.

Re: A proof that Unix utility sed is Turing complete

#73

Post by gammateam »

cyborgx7 wrote: post #39
gammateam wrote: post #18

Why is Turing completeness important to anyone? Asking for a friend

Here is the (overly) simple explanation: Something being Turing complete means that it can compute anything that can be computed.

I asked why it was important to anyone, not what it was

why is this glorified

Re: A proof that Unix utility sed is Turing complete

#74

Post by mirimir »

noxToken wrote: post #65
mirimir wrote: post #58

Earlier quoted context omitted.

Isn'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.

There'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...

Thanks. That's what I was thinking of. Classic "this parrot is dead" riff.

Re: A proof that Unix utility sed is Turing complete

#75

Post by ascar »

saagarjha wrote: post #51
ascar wrote: post #49

Earlier quoted context omitted.

at that point we are only speaking about access control. It's very well possible to run sed in a context, so the bytes it outputs can be used to display information. In fact that's exactly what the console does. It interprets the output of sed as text and displays it on the screen. Nothing forces you to display the sed output in a console. Digital displays only get bytes as input and output visible light for humans.…

> at that point we are only speaking about access control That’s the entire point. sed cannot run Microsoft Word because it cannot control the hardware in the right way. Sure, you could hook up sed to do this, but that would be kind of stupid and useful only in a purely academic sense.

Of course it's purely academic. The whole point of proving sed is turing complete is purely academic. It's interesting to know that other tools, which were designed for a very specific task in a very specific context, can be used as general purpose programming languages. There is no point discussing this in a practical context.

Re: A proof that Unix utility sed is Turing complete

#76

Post by dahart »

Grue3 wrote: post #63

And 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.

Out 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.

Re: A proof that Unix utility sed is Turing complete

#77

Post by daveFNbuck »

chrisweekly wrote: post #56
saagarjha wrote: post #51

Earlier quoted context omitted.

> at that point we are only speaking about access control That’s the entire point. sed cannot run Microsoft Word because it cannot control the hardware in the right way. Sure, you could hook up sed to do this, but that would be kind of stupid and useful only in a purely academic sense.

I'm with @ascar on this. The discussion started with an assertion (paraphrased) "Word couldn't run on sed because it requires things beyond a turing machine". This seems nonsensical to me; turing-complete, by definition, means it can represent any software program or set of programs, including of course an operating system, compiler, etc. To claim that MS Word somehow exists outside this context, because it happens t…

My original point was that you couldn't write sed code that would result in a Word window opening up. This would certainly be possible if you wrote a sophisticated series of drivers and adapters around sed, but sed alone isn't going to get you there. Just being Turing-complete doesn't get you to the ability to run something like Word.

I'd also note that because physical computers have finite storage, you could by the same logic implement Word in a finite-state machine. You could implement the transitions of a finite-state machine using symbolic links in the filesystem. With enough of a surrounding framework, ls -l could be used to do transitions between machine states and drive the program.

So you can write Word in ls in the same way you can write it in sed.

Re: A proof that Unix utility sed is Turing complete

#78

Post by jim_bailie »

qwerty456127 wrote: post #42

I 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).

And 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.

Re: A proof that Unix utility sed is Turing complete

#79

Post by ascar »

daveFNbuck wrote: post #77
chrisweekly wrote: post #56

Earlier quoted context omitted.

I'm with @ascar on this. The discussion started with an assertion (paraphrased) "Word couldn't run on sed because it requires things beyond a turing machine". This seems nonsensical to me; turing-complete, by definition, means it can represent any software program or set of programs, including of course an operating system, compiler, etc. To claim that MS Word somehow exists outside this context, because it happens t…

My original point was that you couldn't write sed code that would result in a Word window opening up. This would certainly be possible if you wrote a sophisticated series of drivers and adapters around sed, but sed alone isn't going to get you there. Just being Turing-complete doesn't get you to the ability to run something like Word. I'd also note that because physical computers have finite storage, you could by the…

> Just being Turing-complete doesn't get you to the ability to run something like Word.

In fact it does. That's the whole point of turing-completeness. It is actually possible to create output with sed that results in executable bytecode similar to C. You would need a sed to bytecode compiler. You could even write this compiler in sed (once you have something else that can compile sed). Why? Because sed is turing complete. Yes, it's very unpractical to do so, but you could do it even on current hardware.

> I'd also note that because physical computers have finite storage, you could by the same logic implement Word in a finite-state machine.

actually you can't. Word itself is turing complete, i.e. you can theoretically program with Word. So no you can't implement word with a finite-state machine, because it can't reflect the theoretically infinite states an arbitrary input program can create. You need a turing machine for that.

> So you can write Word in ls in the same way you can write it in sed.

No. That's missing the point of sed being turing complete.

Re: A proof that Unix utility sed is Turing complete

#80

Post by daveFNbuck »

ascar wrote: post #79
daveFNbuck wrote: post #77

Earlier quoted context omitted.

My original point was that you couldn't write sed code that would result in a Word window opening up. This would certainly be possible if you wrote a sophisticated series of drivers and adapters around sed, but sed alone isn't going to get you there. Just being Turing-complete doesn't get you to the ability to run something like Word. I'd also note that because physical computers have finite storage, you could by the…

> Just being Turing-complete doesn't get you to the ability to run something like Word. In fact it does. That's the whole point of turing-completeness. It is actually possible to create output with sed that results in executable bytecode similar to C. You would need a sed to bytecode compiler. You could even write this compiler in sed (once you have something else that can compile sed). Why? Because sed is turing com…

> It is actually possible to create output with sed that results in executable bytecode similar to C.

The executable bytecode for Word is a constant. cat can output that.

> Word itself is turing complete

Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fidelity.

Post reply on HN