> 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".
- 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".