7 ms·

I never said something contrary to what you describe. The display or the mouse or keyboard is not part of the turing machine. But we communicate with these devi

by ascar 8y ago

I never said something contrary to what you describe. The display or the mouse or keyboard is not part of the turing machine. But we communicate with these devices through a turing machine, e.g. the CPU. We interpret the signals or create visual output using a turing machine. A GUI is a software component and not some hardware. So if sed is turing complete, why shouldn't it be able to run Word, which is also running only on a turing machine. In other words: if sed is turing complete and C is turing complete, we could write a compiler from C to sed and thereby run any program written in C on sed (definitely with abysmal performance, but that's not the point). I'm not saying it's easy, efficient or even desirable to do so, but if sed is turing complete this means we could write a compiler to run any other turing complete program on it. That this process might need basically recompiling a whole operating system might be true, but it doesn't contradict the theory. I don't understand the downvotes here. I might very well be wrong, but your answer isn't giving an explanation for that.

saagarjha 8y ago
CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
- basementcat 8y ago
  Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
  - saagarjha 8y ago
    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.
    - baddox 8y ago
      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.
      - saagarjha 8y ago
        Yeah, but you don't with sed. Hence why it can't be used to run Microsoft Word.
        c22 8y ago
        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.
- 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.
adrianN 8y ago
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.
- ascar 8y ago
  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.

by ascar 8y ago

saagarjha 8y ago

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

basementcat 8y ago
Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
- saagarjha 8y ago
  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.
  - baddox 8y ago
    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.
    - saagarjha 8y ago
      Yeah, but you don't with sed. Hence why it can't be used to run Microsoft Word.
      - c22 8y ago
        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.
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.

adrianN 8y ago

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.

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