FOM: Church's thesis and complexity
mellon at pobox.com
Tue Nov 3 12:42:09 EST 1998
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
> an oracle for the halting problem for example--this is not ruled out by
> 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?
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.
mellon at pobox.com http://pobox.com/~mellon/
"Angels can fly because they take themselves lightly" - G.K.Chesterton
More information about the FOM