8 ms·

You're basically describing compilers. Microsoft Word probably wouldn't run on sed because it requires things outside of the capabilities of a Turing machine, l

You're basically describing compilers. Microsoft Word probably wouldn't run on sed because it requires things outside of the capabilities of a Turing machine, like being able to produce a GUI.

ascar 8y ago
Considering a GUI runs on a turing machine, how is it outside the capabilities of one? Isn't everything we do on computers exactly within the capabilities of a turing machine and just about the ingenuity to create a program that does what we want and about its efficiency? In other words, if sed is turing complete, this means you could run any other turing complete program on it. Producing a GUI is also just telling your CPU (a sophisticated turing machine) to format data and how to send the formated data to a display. EDIT: what justifies the downvotes? Sure the display is not part of the turing machine, but the display is also not part of the GUI. The GUI is a software component that can be created by a turing machine. You wouldn't disagree with me for stating a GUI can be created through a C or Java program.
- adrianN 8y ago
  Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.
  - 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.
  - basementcat 8y ago
    You can define certain tape positions to be i/o ports.
  - yason 8y ago
    Turing machines don't have displays or keyboards or network adapters. Nor do processors these days. To the cpu, keyboards, networks, and displays are just electronic signals and the cpu drives a logic to interpret and control those signals. The logic could as well be driven by a program running on a Turing machine, albeit awkwardly of course. You could also argue that a Unix tool that reads stdin and writes to stdout doesn't have displays or keyboards, and is limited in what it can do. Yet the input/output streams are an abstraction: if we hook the output stream to drive a display and connect the input stream to keyboard event generator the program can certainly drive a graphical interface even if particular Unix tool itself has absolutely no notion of a keyboard nor a display. It just sees bytes in, bytes out, as programmed. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. Turing machine is a theoretical model of a computing machine as far it goes to reality itself, but the model does involve the bare essentials to do meaningful work such as input and output. And it is that input and output are what would allow it to be hooked into something that is real. Given the realism of that we don't actually have infinite tapes either, any hypothetical application of a Turing machine would obviously manipulate the tape to give the program initial input and interpret the tape to read output in order to have the program do useful work. The notation of an infinite tape is just Turing machine's only way to handle input and output, but it is really an abstraction for any input and output. The Turing machine doesn't care where the data on the tape came from or if the output is interpreted as letters, pixels, or audio.
  - csomar 8y ago
    Full simulation is reality. A reality that you can not see (through your screen) but a reality indeed; on its own box.
  - astrobe_ 8y ago
    I think for the display a Turing machine can simulate a kind of video RAM on a specific location of the tape ; but I guess a single pixel would need a significant amount of cells. For inputs one could introduce memory-mapped peripheral registers, like the M68K does. The original definition of TM can be preserved if you consider that you are introducing the notion of an outside world that would look at the tape at the end of the TM run (for display etc.) and feed another tape with different initial cell states (peripheral register values) for the next run. > simulation is not reality. Virtual machines and emulators are however quite useful ; and it seems that for some people, simulating human intelligence is the Graal.
- jhanschoo 8y ago
  Note that Turing completeness says nothing about efficiency. It is possible that some models experience exponential slowdown or worse.
adriveatrain 8y ago
Word is a set of COM objects, you can run it server side without the UI.

You're basically describing compilers. Microsoft Word probably wouldn't run on sed because it requires things outside of the capabilities of a Turing machine, like being able to produce a GUI.

ascar 8y ago

Considering a GUI runs on a turing machine, how is it outside the capabilities of one? Isn't everything we do on computers exactly within the capabilities of a turing machine and just about the ingenuity to create a program that does what we want and about its efficiency? In other words, if sed is turing complete, this means you could run any other turing complete program on it. Producing a GUI is also just telling your CPU (a sophisticated turing machine) to format data and how to send the formated data to a display. EDIT: what justifies the downvotes? Sure the display is not part of the turing machine, but the display is also not part of the GUI. The GUI is a software component that can be created by a turing machine. You wouldn't disagree with me for stating a GUI can be created through a C or Java program.

adrianN 8y ago
Turing machines don't have displays or keyboards or network adapters. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.
- 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.
- basementcat 8y ago
  You can define certain tape positions to be i/o ports.
- yason 8y ago
  Turing machines don't have displays or keyboards or network adapters. Nor do processors these days. To the cpu, keyboards, networks, and displays are just electronic signals and the cpu drives a logic to interpret and control those signals. The logic could as well be driven by a program running on a Turing machine, albeit awkwardly of course. You could also argue that a Unix tool that reads stdin and writes to stdout doesn't have displays or keyboards, and is limited in what it can do. Yet the input/output streams are an abstraction: if we hook the output stream to drive a display and connect the input stream to keyboard event generator the program can certainly drive a graphical interface even if particular Unix tool itself has absolutely no notion of a keyboard nor a display. It just sees bytes in, bytes out, as programmed. They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them. Turing machine is a theoretical model of a computing machine as far it goes to reality itself, but the model does involve the bare essentials to do meaningful work such as input and output. And it is that input and output are what would allow it to be hooked into something that is real. Given the realism of that we don't actually have infinite tapes either, any hypothetical application of a Turing machine would obviously manipulate the tape to give the program initial input and interpret the tape to read output in order to have the program do useful work. The notation of an infinite tape is just Turing machine's only way to handle input and output, but it is really an abstraction for any input and output. The Turing machine doesn't care where the data on the tape came from or if the output is interpreted as letters, pixels, or audio.
- csomar 8y ago
  Full simulation is reality. A reality that you can not see (through your screen) but a reality indeed; on its own box.
- astrobe_ 8y ago
  I think for the display a Turing machine can simulate a kind of video RAM on a specific location of the tape ; but I guess a single pixel would need a significant amount of cells. For inputs one could introduce memory-mapped peripheral registers, like the M68K does. The original definition of TM can be preserved if you consider that you are introducing the notion of an outside world that would look at the tape at the end of the TM run (for display etc.) and feed another tape with different initial cell states (peripheral register values) for the next run. > simulation is not reality. Virtual machines and emulators are however quite useful ; and it seems that for some people, simulating human intelligence is the Graal.
jhanschoo 8y ago
Note that Turing completeness says nothing about efficiency. It is possible that some models experience exponential slowdown or worse.

adriveatrain 8y ago

Word is a set of COM objects, you can run it server side without the UI.