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