13 ms·

Has anyone written a kind of Turing machine gateway API, where people write an adaptor to the API and you can then use the gateway to use any Turing machine bac

Has anyone written a kind of Turing machine gateway API, where people write an adaptor to the API and you can then use the gateway to use any Turing machine backend to run any other(Turing complete) program. Would be interesting to see e.g. how fast Microsoft Word runs on a sed based backend.

User23 8y ago
This that you describe is essentially a Universal Turing Machine.
- afiori 8y ago
  Yes, but it should be noted that a sed-interpreted word would also need to emulate the OS and the hardware, as I imagine that the syscall you can make from sed are limited
- Quekid5 8y ago
  There's been a very weird discussion going on here based on the misconception that TMs are somehow equivalent to Interactive TMs[1]. In the usual theory of TMs there's no idea that there's "input" (e.g. another TM altering the tape) or anything similar. You just give it a starting position and the initial state of the tape and let it go. [1] https://en.wikipedia.org/wiki/Interactive_computation https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)
daveFNbuck 8y ago
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.
- adriveatrain 8y ago
  Word is a set of COM objects, you can run it server side without the UI.

User23 8y ago

This that you describe is essentially a Universal Turing Machine.

afiori 8y ago
Yes, but it should be noted that a sed-interpreted word would also need to emulate the OS and the hardware, as I imagine that the syscall you can make from sed are limited
Quekid5 8y ago
There's been a very weird discussion going on here based on the misconception that TMs are somehow equivalent to Interactive TMs[1]. In the usual theory of TMs there's no idea that there's "input" (e.g. another TM altering the tape) or anything similar. You just give it a starting position and the initial state of the tape and let it go. [1] https://en.wikipedia.org/wiki/Interactive_computation https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)

daveFNbuck 8y ago

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.
adriveatrain 8y ago
Word is a set of COM objects, you can run it server side without the UI.