5 ms·

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 t

by ascar 8y ago

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.

saagarjha 8y ago
No, because the two Turing machines run in different contexts, one of which is unable to access a graphical display.
- ascar 8y ago
  < 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.
  - saagarjha 8y ago
    > 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.
    - chrisweekly 8y ago
      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.
      - foldr 8y ago
        >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.
      - daveFNbuck 8y ago
        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.
JdeBP 8y ago
"automata" is already plural, note.

by ascar 8y ago

saagarjha 8y ago

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

ascar 8y ago
< 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.
- saagarjha 8y ago
  > 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.
  - chrisweekly 8y ago
    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.
    - foldr 8y ago
      >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.
    - daveFNbuck 8y ago
      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.

JdeBP 8y ago

"automata" is already plural, note.