4 ms·

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 sophistica

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.

ascar 8y ago
> 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.
- daveFNbuck 8y ago
  > 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.
  - c22 8y ago
    Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?
    - saagarjha 8y ago
      Technically, yes.
    - daveFNbuck 8y ago
      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.
ascar 8y ago
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.
- daveFNbuck 8y ago
  > 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.

ascar 8y ago

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

daveFNbuck 8y ago
> 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.
- c22 8y ago
  Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?
  - saagarjha 8y ago
    Technically, yes.
  - daveFNbuck 8y ago
    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.

ascar 8y ago

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.

daveFNbuck 8y ago
> 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.