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

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