FOM: Church-Turing hypothesis -- reply to Vorobey and Davis

Kanovei kanovei at
Wed Nov 4 12:48:51 EST 1998

mellon at 

> 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 

Vladimir Kanovei

More information about the FOM mailing list