FOM: Re: Application of reverse maths to theoretical physics

Andrew Boucher Helene.Boucher at
Sat Sep 18 13:02:47 EDT 1999

>Another way in which we could get at mathematical truth from physics
>if Church's thesis is false and we could set up an experiment to
>calculate a definable but noncomputable real number; the value of any
>digit beyond a certain finite level of precision would be a
>fact independent of ZFC.
>-- Joe Shipman

    First, you need an infinite output for a noncomputable real; any
finite string is of course computable.  So it seems a bit dicey to
assert that there is an experiment which could determine this, or that
a physical machine can calculate a noncomputable real, since
presumably that would mean it would have to output an infinite number
of digits.

    But suppose we go down the rabbit hole and allow machines to go on
forever, etc. etc.  Still you don't need Church's thesis false to set
up your experiment, as we can "calculate" physically a definable but
noncomputable real number even if Church's Thesis is still true.

    Consider two ("real") finite-state machines which communicate with
each other.  The first machine alternates between states q0 and q1, as
does the second.  In state q0 the first machine communicates with the
second and determines what state it is in.  In state q1 it outputs i
if the second machine was in state qi.  Suppose further that the first
machine takes exactly r1 time units to complete every step, and the
second exactly r2 time units.  It is clear that what the first machine
outputs will depend on their respective operating speeds, and indeed
depend on the ratio r1/r2.  For instance, if r1/r2 = 1, then the
sequence will be all 0's.  And if r1/r2 = 0.5--i.e. the first machine
is exactly twice as fast as the second machine--then the sequence will
alternate 0's and 1's. If one allows all reals as ratios (and I guess
we can suppose this, since we're down the rabbit hole), then it is
easy to see that a non-computable sequence can be outputted.  Does
this imply that Church's Thesis--that every (intuitively) effective
procedure is Turing computable--is false?  Of course not!  The
procedure being used is not an effective procedure:  it depends on a
quantity r1/r2 which is not effectively determined. 

More information about the FOM mailing list