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

21–30 of 109 posts

Re: A proof that Unix utility sed is Turing complete

#21

Post by ascar »

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.

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

Re: A proof that Unix utility sed is Turing complete

#23

Post by Cu3PO42 »

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…

In my formal languages course in Germany we covered various computational models and showed the equivalences to Turing Machines. We never built complex TMs by hand, only describing how they would work.

I did, however, build larger TMs by hand in a high school course.

Re: A proof that Unix utility sed is Turing complete

#24

Post by adrianN »

ascar wrote: post #21
daveFNbuck wrote: post #15

Earlier quoted context omitted.

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.

Considering 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 y…

Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them.

You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.

Re: A proof that Unix utility sed is Turing complete

#26

Post by ascar »

adrianN wrote: post #24
ascar wrote: post #21

Earlier quoted context omitted.

Considering 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 y…

Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.

I never said something contrary to what you describe. The display or the mouse or keyboard is not part of the turing machine. But we communicate with these devices through a turing machine, e.g. the CPU. We interpret the signals or create visual output using a turing machine. A GUI is a software component and not some hardware. So if sed is turing complete, why shouldn't it be able to run Word, which is also running only on a turing machine. In other words: if sed is turing complete and C is turing complete, we could write a compiler from C to sed and thereby run any program written in C on sed (definitely with abysmal performance, but that's not the point).

I'm not saying it's easy, efficient or even desirable to do so, but if sed is turing complete this means we could write a compiler to run any other turing complete program on it. That this process might need basically recompiling a whole operating system might be true, but it doesn't contradict the theory.

I don't understand the downvotes here. I might very well be wrong, but your answer isn't giving an explanation for that.

Re: A proof that Unix utility sed is Turing complete

#27

Post by saagarjha »

ascar wrote: post #26
adrianN wrote: post #24

Earlier quoted context omitted.

Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.

I never said something contrary to what you describe. The display or the mouse or keyboard is not part of the turing machine. But we communicate with these devices through a turing machine, e.g. the CPU. We interpret the signals or create visual output using a turing machine. A GUI is a software component and not some hardware. So if sed is turing complete, why shouldn't it be able to run Word, which is also running…

CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.

Re: A proof that Unix utility sed is Turing complete

#28

Post by saagarjha »

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.

Given that sed is Turing complete, I'm sure if you tried harder you would have come up with a general solution ;)

Re: A proof that Unix utility sed is Turing complete

#29

Post by basementcat »

adrianN wrote: post #24
ascar wrote: post #21

Earlier quoted context omitted.

Considering 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 y…

Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.

You can define certain tape positions to be i/o ports.

Re: A proof that Unix utility sed is Turing complete

#30

Post by basementcat »

saagarjha wrote: post #27
ascar wrote: post #26

Earlier quoted context omitted.

I never said something contrary to what you describe. The display or the mouse or keyboard is not part of the turing machine. But we communicate with these devices through a turing machine, e.g. the CPU. We interpret the signals or create visual output using a turing machine. A GUI is a software component and not some hardware. So if sed is turing complete, why shouldn't it be able to run Word, which is also running…

CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.

Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
Post reply on HN