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

81–90 of 109 posts

Re: A proof that Unix utility sed is Turing complete

#81

Post by csomar »

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.

Full simulation is reality. A reality that you can not see (through your screen) but a reality indeed; on its own box.

Re: A proof that Unix utility sed is Turing complete

#82

Post by dahart »

darkkindness wrote: post #43
easytiger wrote: post #34

Earlier quoted context omitted.

http://funarg.nfshost.com/r2/code/sed/ray/ray.sed

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

Totally 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

Re: A proof that Unix utility sed is Turing complete

#83

Post by astrobe_ »

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 think for the display a Turing machine can simulate a kind of video RAM on a specific location of the tape ; but I guess a single pixel would need a significant amount of cells.

For inputs one could introduce memory-mapped peripheral registers, like the M68K does.

The original definition of TM can be preserved if you consider that you are introducing the notion of an outside world that would look at the tape at the end of the TM run (for display etc.) and feed another tape with different initial cell states (peripheral register values) for the next run.

> simulation is not reality.

Virtual machines and emulators are however quite useful ; and it seems that for some people, simulating human intelligence is the Graal.

Re: A proof that Unix utility sed is Turing complete

#84

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…

we reached the depth limit of comments on the other answer. This will be my last reply, but you can still reply to this:

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

I didn't mean output in the sense of printing it to a screen. What I wanted to say is that you can write anything in sed that you can write in C and that you could create a compiler for sed like you can create a C compiler, to run arbitary sed programs on current hardware.

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

No, I'm pretty sure you can't. A finite-state machines can not even parse context-free (Chomsky type-2) languages, so it definitely can not execute a general purpose program written in Word, even with a finite amount of memory. And as we can write general purpose programs in Word (and in sed, because they are both turing complete), you could never create a finite-state machine that can do everything that Word can do.

But yes, we usually ignore that our computers don't have infinite tape, as even the possible permutations for input programs of just 1kb are for our purposes basically endless (2^1024).

The point with C, C++, Java, Python, Word and sed being turing complete is that you can write general purpose programs for them to execute. You can not write general purpose programs for finite-state machines, you can not even create finite-state machines for every program. That's the interesting part of identifying if something is turing complete, even though it has no practical use it's not, because there isn't the necessary envrionment and it's never as efficient as the general purpose programming languages we built.

Re: A proof that Unix utility sed is Turing complete

#85

Post by c22 »

ascar wrote: post #75
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.

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.

It's not entirely academic, though, because surprise turing machines often lead to weird bugs or failures in assumptions about security.

Re: A proof that Unix utility sed is Turing complete

#86

Post by dwrodri »

gammateam wrote: post #18

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

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

Re: A proof that Unix utility sed is Turing complete

#87

Post by c22 »

saagarjha wrote: post #46
baddox wrote: post #44

Earlier quoted context omitted.

So a display is simply a device you plug into some pins on the computer to format the computer’s state in a more human-friendly way. You could do the exact same thing with a Turing machine.

Yeah, but you don't with sed. Hence why it can't be used to run Microsoft Word.

Why not? While sed is chuggng away at assembling your instructions you will have plenty of time to work on the problem. Just bulid a device that plugs into the serial port of your computer, run your sed-word amalgamation in a shell on the serial tty. Configure your device to interpret the ascii sequences from the serial terminal as pixels and output them as physical dots of light. Now for bonus points you can redesign the communication protocol to be more compact.

Re: A proof that Unix utility sed is Turing complete

#88

Post by c22 »

daveFNbuck wrote: post #80
ascar wrote: post #79

Earlier quoted context omitted.

> 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 fideli…

Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?

Re: A proof that Unix utility sed is Turing complete

#89

Post by daveFNbuck »

ascar wrote: post #84
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…

we reached the depth limit of comments on the other answer. This will be my last reply, but you can still reply to this: >> 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. I didn't mean output in the sense of printing it to a screen. What I wanted to say is that you can write anything in sed that…

> What I wanted to say is that you can write anything in sed that you can write in C

This actually doesn't follow from sed being Turing-complete, and I don't think it's true. The construction to show that sed is Turing-complete requires transforming the input into one that sed can then perform computations on. I think a more clear example is Lambda calculus.

You can't write a Lambda calculus expression that increments a binary number. Lambda calculus can only operate on lambda expressions. Turing-completeness just means it's capable of computing the same sort of functions, not that it can match the input and output formats.

> you could create a compiler for sed like you can create a C compiler, to run arbitary sed programs on current hardware.

My point is that no input to sed will result in a Word window opening. sed can perform all the same calculations, but there's more to Word than that. I think we're agreed on this point. We're also agreed that you could embed sed in an appropriate framework and produce that window. I think our disagreement between these is mostly semantics, so I'm happy to stop arguing about it if you're done.

> No, I'm pretty sure you can't. A finite-state machines can not even parse context-free (Chomsky type-2) languages, so it definitely can not represent a general purpose program written in Word, even with a finite amount of memory.

Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10. There are only 2047 strings of parentheses of length up to 10, so you can have a state for each one and mark the valid ones as accepting states.

If we model the state of your computer, including every bit in ram, storage, caches, etc., then we know which state your computer will be in after the next clock cycle. We can therefore model your computer as a finite state machine, where each state represents the state of your computer at a given moment, and the transition is the result of your computer operating for a clock cycle.

There are a finite amount of possible states, and the transitions are deterministic. This defines a finite state machine.

You can't define a finite-state machine that can do everything that Word can do in principle, but you can define one that can do everything that Word can do on your computer, or in a VM. There would be way more states in this machine than there are atoms in the universe, but it's within the power of this theoretical construct.

Re: A proof that Unix utility sed is Turing complete

#90

Post by theonemind »

abhishekjha wrote: post #45
throwawayRO12 wrote: post #17

Earlier quoted context omitted.

You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)

>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?

i remember covering this sort of thing in my automata theory class. we used this textbook: https://www.amazon.com/Automata-Computability-Complexity-The...

I can't remember if it specifically shows such a proof in there, but you might look at courseware for automata theory and such.

In general, from what I remember, you would use a general technique called "reduction", where you try to make two problems equivalent, "reducing" solving one to the problem of solving the other one, kind of mapping one problem on to another, so that solving one solves them both. So, you reduce running an arbitrary Turing machine, to say, lambda calculus, almost like you write a "compiler" from a Turing machine with lambda calculus as the target language. Then, you reduce computing in lambda calculus to a Turing machine. So, then you know that each can compute what the other computes, and they can only compute the same things. If you only did one half, one reduction, you would only know, say, that a Turing machine could do everything you could do in lambda calculus, but it would leave the possibility that the Turing machine could compute things lambda calculus can't.

Post reply on HN