FOM: Church's thesis and complexity

[Anatoly Vorobey]

You, Joe Shipman, were spotted writing this on Mon, Nov 02, 1998 at 04:39:56PM -0500:

> Regarding Church's thesis, I claim it is a statement of physics because
> it is
> potentially empirically falsifiable (if we discover how to physically
> construct
> an oracle for the halting problem for example--this is not ruled out by
> the
> current laws of physics).  

It seems to me, however, that there is a sort of catch-22 here.

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?

Yours,
Anatoly.

P.S. Are you familiar with Penrose's example of tile universe? He outlines
a hypothetical universe (consisting of sets of figures on the plane) which
evolves deterministically but nonrecursively. 

-- 
Anatoly Vorobey,
mellon at pobox.com http://pobox.com/~mellon/
"Angels can fly because they take themselves lightly" - G.K.Chesterton