FOM: Church-Turing hypothesis -- reply to Vorobey and Davis
Kanovei
kanovei at wminf2.math.uni-wuppertal.de
Wed Nov 4 12:48:51 EST 1998
mellon at pobox.com:
> Suppose that you are facing a physical device that you suspect is the
> oracle for the halting problem.
>
> How, do you think, would you be able to *prove* that it really always
> solves
> the halting problem correctly?
There seem to be no other way as to give a mathematically
full description of the *device* and prove, in mathematically
accepted way, that it really solves the halting problem.
Otherwise it would not count as a mathematical result.
This includes also the case when the *device* is not fully
deterministic, then you may expect theorems that it solves
the halting problem with probability 1 - 2^{-1000}.
If finally the *device* does not admit a full description
(say, it includes observation of some phenomena related to
remote galaxies) then basically this is not a problem for
mathematics, rather for natural science, to explore what
is going on, in particular, could it be a fake of
extraterrestrials.
Vladimir Kanovei
More information about the FOM
mailing list