4 ms·

Is there a known example of something a digital computer can do that a Turing machine cannot?

by wbhart 8y ago

your-nanny 8y ago
overheat.
Retra 8y ago
Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
pmiller2 8y ago
In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
- kps 8y ago
  Real computers generally have external storage and/or network interfaces, which makes them unbounded.
  - pmiller2 8y ago
    No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.
wolfgke 8y ago
> Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".

Is there a known example of something a digital computer can do that a Turing machine cannot?

by wbhart 8y ago

Is there a known example of something a digital computer can do that a Turing machine cannot?

your-nanny 8y ago

overheat.

Retra 8y ago

Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.

pmiller2 8y ago

In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.

kps 8y ago
Real computers generally have external storage and/or network interfaces, which makes them unbounded.
- pmiller2 8y ago
  No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.

wolfgke 8y ago

> Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".