FOM: Church's Thesis

[Vaughan Pratt]

>From: Stephen Fenner <fenner at cs.sc.edu>
>I think what Joe might mean (correct me, Joe) is that if we find that
>Church's Thesis is false, it will come from a physical theory (expressed
>mathematically) which not only allows us to build a physical device 
>to compute some definable
>non-Turing computable sequence, but also GIVES US a concrete definition of
>the sequence as well, so that one could conceivably infer from this
>definition that Con(ZFC) is
>coded in, say, its 217th bit (a low-ball estimate).

That was what I was assuming when I commented in the first place that
Joe's asking nature for an entire noncomputable sequence seemed like
overkill when you could just as well ask nature for a single bit answering
"Con(ZFC)?".  But then Joe replied that the reason he wanted the whole
thing was because "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;".

Fenner:
>If the device is run
>long enough, then more bits would emerge, but we need only run the device
>a finite amount of time to get the 217th bit.

Right, and Joe makes this point too.  But this doesn't require a device
that contradicts Church's Thesis, it merely requires a device whose
217th bit answers whatever question you thought it answered.  Which of
course can easily be constructed from a device whose first and only bit
does that job.

Joe went on to say (in his reply to me)

>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.

This falls short of knowing what those bits are.  You say explicitly,
and perhaps Joe has in mind implicitly, that some physical theory tells
us what all those bits are.  It is that additional step of knowing the
bits that I was pointing out seemed like overkill, since it is already
impressive enough if that 217th bit tells you this otherwise inaccessible
fact.  Suppose that after accessing bit 217, bits 218 onwards turned out
to be all zero.  You wouldn't have your counterexample to Church's Thesis
after all, but you'd still have that astonishingly informative 217th bit.
I don't understand the logic behind Joe's "how else could you get that
bit unless the remaining bits turned out to be uncomputable?"

Vaughan Pratt