Oh I see, you want to add an interpretation level that takes the state tuple of the TM and translates it to pixels or your screen and patches the inputs like keyboard and mouse back into the TM. You can do that of course.

Not really the sate tuple. More like writing to certain positions of the tape results in physical I/O, e.g sending the bitstream over a cable to the display. This phyiscal I/O is outside of the capabilities of the turing machine, but it controls it through writing/reading from the tape.

A turing machine is simplified a finite state automata with random access memory and you can use that memory to setup communication. Yes the communication isn't part of the turing machine anymore, but our computer programs dictate what to communicate and we know what to send to create a certain output. That's what I meant with ingenuity to create these programs.

There is no real difference between any turing complete programming language or program apart from the libraries that help us do what we want.

That Word uses a GUI and sed uses a terminal/console is no difference at all in that regard. Both are a graphical user interface. It's just that Word dictates exactly what it wants to display, while sed just sends text and lets the console dictate how to display that text. Both is using a turing machine to create the data that finally creates an image on our display.

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

Turing machines are finite state automatas with random read and write access to a tape (i.e. memory).

One turing machine can write to a certain position on a tape, while another turing machine can read from that position on the tape. At that point we communicated between two turing machines. Add some electric engineering to allow this tape position to send electrical signals from one place to another other a wire and you have peripheral devices. Yes actually displaying something through a display is thus more than a turing machine.

But the topic at hand was between the different capabilities of one turing complete program/language (Word) and another turing complete program/language (sed) executing on the same turing machine. The definition of turing complete is that anything the first program can do, the second can do too.

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

< 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. These bytes are mostly an arbitrary format optimized for performance. Sed can output arbitrary bytes too based on an input program. That's what "sed is turing complete" tells us.

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.

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.

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

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

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

It's a model. The phrase is meaningful as far as its features correspond well to features of the thing you're trying to model. Turing machines are pretty good models for which functions are computable on something like a model computer. They're not good models for interactive graphical applications.

Technically, yes.

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.

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

> I think our disagreement between these is mostly semantics

Yes. I agree.

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

I already typed something similar before I changed my comment. I basically wanted to argue that it's theoretically correct, but we even dismiss it in computation theory, because modeling every state of a turing machine with just a few kilobyte of input is physically impossible.

But I was so unsure if that was actually true or there was a more fundamental problem that I convinced myself the "finite input" isn't the only thing that limits the capabilities of finite-state automatons vs pushdown automatons vs turing machines. I'm still not entirely sure, but I was thinking exactly the same as you explained.

I don't think HN has a depth limit. Sometimes I find the reply link doesn't show up under a comment, but I can usually see it if I refresh the page or click the permalink.

Yea, reply showed up later ¯\_(ツ)_/¯ i'll try the permalink next time

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

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.

"automata" is already plural, note.

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

Sure, but their states aren't quite what you'd consider to be states for an abstract Turing machine. There's a CPU state that also happens to set some pixels on a display to a certain value, for example.

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.