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

51–60 of 109 posts

Re: A proof that Unix utility sed is Turing complete

#51

Post by saagarjha »

ascar wrote: post #49
saagarjha wrote: post #40

Earlier quoted context omitted.

No, because the two Turing machines run in different contexts, one of which is unable to access a graphical display.

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.

Re: A proof that Unix utility sed is Turing complete

#52

Post by agumonkey »

samat wrote: post #13

In 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 so…

my brain always preferred rewriting systems to naive TM interpretation

anybody else ?

Re: A proof that Unix utility sed is Turing complete

#54

Post by deytempo »

klmr wrote: post #41
otabdeveloper1 wrote: post #35

Basically, anything that can recurse is Turing-complete.

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

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

Re: A proof that Unix utility sed is Turing complete

#55

Post by adriveatrain »

daveFNbuck wrote: post #15
wilsonrocks wrote: post #10

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

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

Word is a set of COM objects, you can run it server side without the UI.

Re: A proof that Unix utility sed is Turing complete

#56

Post by chrisweekly »

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.

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 to produce ones and zeros corresponding to a GUI rather than a CLI, is clearly incorrect. Of course it's "purely academic"! Nobody said it'd be smart or efficient to implement. But that's not the question under discussion! No fair shifting the argument / moving the goalposts like that.

Re: A proof that Unix utility sed is Turing complete

#57

Post by maxiepoo »

erfgh wrote: post #19
gammateam wrote: post #18

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

It is if you can make a paper out of it and increase your publication count.

I highly doubt that you can get a paper at any respectable conference or journal showing something is Turing Complete.

Re: A proof that Unix utility sed is Turing complete

#58

Post by mirimir »

kccqzy wrote: post #5

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

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.

Re: A proof that Unix utility sed is Turing complete

#59

Post by foldr »

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…

>turing-complete, by definition, means it can represent any software program or set of programs, including of course an operating system, compiler, etc.

Turing-complete just means that it can compute any function that a Turing machine can compute. Turing machines are universal computers, not universal machines.

My computer can compute F ⇒ a Turing machine can compute F (assuming the Church-Turing thesis).

My computer can do X ⇏ a Turing machine can do X.

Re: A proof that Unix utility sed is Turing complete

#60

Post by norswap »

klmr wrote: post #41
otabdeveloper1 wrote: post #35

Basically, anything that can recurse is Turing-complete.

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?
Post reply on HN