How many of you like HP41C calculators?

From: der Mouse <mouse_at_Rodents.Montreal.QC.CA>
Date: Fri Nov 21 04:39:51 2003

> No, Turing showed that if it can be computed, it is computable on a
> TM.

Not quite, unless you define "can be computed" in terms of Turing
machines or something provably equivalent to Turing machines, in which
case it becomes a tautology.

What Turing showed is that certain other, intuitively plausible, models
of (discrete) computation are all equivalent to Turing machines in
terms of what they can compute. He did not show that there are no
other possible models of computation, not even of discrete computation;
indeed, without a precise definition of what "computation" means,
nobody can. (As I remarked in this connection in a different message,
there are operations describable in the language of analysis and
calculus that no discrete device, including a Turing machine, can ever
carry out, so I suspect it is already false. However, I also suspect
this is not often realized, because our notion of what constitutes
computation is so bound up with discrete devices.)

> There is no machine existing, no machine which may exist, that can
> compute a computation which is not also computable on a TM.

This statement amounts to stating that nobody will ever develop a
notion of computability that includes things TMs cannot compute. While
this may be true, it is a prediction, not a statement of current fact.
(As I noted above, I suspect it is a statement of current non-fact.)

/~\ The ASCII der Mouse
\ / Ribbon Campaign
 X Against HTML mouse_at_rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Received on Fri Nov 21 2003 - 04:39:51 GMT