How many of you like HP41C calculators?

From: Andy Holt <andyh_at_andyh-rayleigh.freeserve.co.uk>
Date: Fri Nov 21 05:09:38 2003

> No, Turing showed that if it can be computed, it is computable
> on a TM. There is no machine existing, no machine which may
> exist, that can compute a computation which is not also
> computable on a TM.
>
Close - but to be precise you need the word "deterministic" in there
somewhere (which is where quantum computers show specific promise).

Essentially, the set of "computable functions" (I forget the precise
technical term); the set of results that can by computed by a Universal
Turing Machine; and the set of results that can be computed by a computing
system that meets a remarkably small set of requirements are all identical
(given infinite time and memory :-)

"If it is powerful enough to be useful, it is powerful enough to write a
self-reproducing program" - I think, but am not sure that I can prove, that
this translates to "if it is powerful enough to be useful then it can have a
virus"

Andy
Received on Fri Nov 21 2003 - 05:09:38 GMT