31–40 of 109 posts
Earlier quoted context omitted.
CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
Earlier quoted context omitted.
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.
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…
Earlier quoted context omitted.
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…
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.
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.
It's not turing complete until someone writes a ray tracer in it!
Earlier quoted context omitted.
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…
CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
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.
In a course on algorithms I took in Moscow State Uni (Russia), we were told there are two ways to describe a Turing machine: - One with a tape & state transition table - A string & a list of string replacements Then we proved this two definitions being equal. And programmed for each ‘system’ a little. I must admit, programming with ‘string replacements’ is much much more fun than doing ‘tape & table’. Is this just so…
I spent months building TMs (also a lot of DFAs) and equivalents as an undergraduate student (which was a lot of fun), and personally I always thought of a TM as a string character replacement machine. The set of alphabet symbols for a TM is of course not restricted to {0, 1}, you can also chose all UTF-8 characters if you like.
Earlier quoted context omitted.
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 y…
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.
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.
Why is Turing completeness important to anyone? Asking for a friend
Earlier quoted context omitted.
CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
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…