FOM: Church's Thesis

Kevin Davey kedst13+ at
Fri Sep 17 16:18:53 EDT 1999

>>The same difficulty you're encountering with a single bit is a
>>(in spades) with a sequence of bits.  The class of noncomputable
>>sequences is stable under recursive (or must we all now say
>>permutations.  Supposing that Church's thesis had failed, yielding a
>>noncomputable sequence, nothing in this scenario prevents an adversary
>>stepping in unbeknownst to you and recursively permuting its bits.
>>Putting it another way, the sequence may be mathematically definable
>>but it doesn't follow that you know the definition.
>My point was that if we could KNOW that Church's Thesis is false, it
>would be in the context of some mathematized physical theory within
>which one could derive an experimental procedure for calculating a
>noncomputable sequence; and the sequence would be definable within this
>mathematized theory and presumably within ZFC.

Perhaps an example might be helpful. Consider a calculation of the
universal gravitational constant G. Let's assume G is non-recursive, i.e.,
that its digits form a non-recursive sequence. If there were a procedure,
uniform in n, for calculating the n-th digit of G, we would have a
counterexample to Church's Thesis (even though i. this consequence may be
open to dispute, and ii. we have to decide what 'uniform' means here.) But
I'm not sure that there is such a procedure for calculating the digits of
G; my suspicion is that the uncertainty-like relations that hold of
classical physics (much discussed by Bohr, etc, when interpreting
Heisenberg's uncertainty relation) prohibit us from calculating G with
arbitrary precision. So my hunch is: it's not clear that one can violate
Church's thesis using classical physics of this sort, and that quantum
physics would make it even harder to violate Church's thesis, because of
the -actual- uncertainty in operators with discrete spectra. (Even though
operators with continuous spectra might offer some hope ...) 

My point: we ought to get some concrete physics to talk about first before
we wax hypothetical.

Kevin Davey.

More information about the FOM mailing list