6 ms·
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 word
by 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 agoI 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 agoCPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
- basementcat 8y agoPractically realizable CPU’s are just deterministic finite state automata with a very large number of states.
- saagarjha 8y agoSure, 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 agoSo 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 agoYeah, but you don't with sed. Hence why it can't be used to run Microsoft Word.
- c22 8y agoWhy 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 agoTuring 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 agoNo, 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 agoOh 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 agoNot 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.
- basementcat 8y agoYou can define certain tape positions to be i/o ports.
- yason 8y agoTuring 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 agoFull simulation is reality. A reality that you can not see (through your screen) but a reality indeed; on its own box.
- astrobe_ 8y agoI 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.