FOM: Church's thesis: reply to Pratt

Vaughan Pratt pratt at CS.Stanford.EDU
Fri Sep 17 03:27:42 EDT 1999

Joe Shipman:
>I can't think of a plausible way to get the value of Con(ZFC) from
>nature, except as part of a general solution to the halting problem
>my point was that ANY mathematically rigorous physical theory in which
>Church's thesis fails will involve the experimental accessibility of a
>mathematically definable but noncomputable sequence; and ANY such
>sequence has bits which ZFC does not decide the value of.

The same difficulty you're encountering with a single bit is a difficulty
(in spades) with a sequence of bits.  The class of noncomputable
sequences is stable under recursive (or must we all now say computable?)
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.

Vaughan Pratt

More information about the FOM mailing list