FOM: Re: Application of reverse maths to theoretical physics

[Andrew Boucher]

>
>Another way in which we could get at mathematical truth from physics
is
>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
mathematical
>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 wooly to
assert that there is an experiment which can 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 allow machines to go on forever (and we can judge
their output).  Then *still* you don't need Church's thesis false to
set up your experiment.  That is, it is conceivable that we can
"calculate" physically a definable but noncomputable real number but
that Church's Thesis is still true.  
    Consider two (real) finite-state machines which communicate with
each other.  The second machine alternates writing 0 and 1 on its
tape.  The first machine alternates between state q1 and q2.  When
it's in state q2, it reads  whatever is on the second machine's tape
at that instant.  When it's in state q1, it outputs what it has read. 
In this way an infinite sequence will be generated.  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 reads on the second machine's tape 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 or all
1's.  If r1/r2 = 0.5--i.e. the first machine is exactly twice as
fast--then the sequence will alternate 00's and 11's.)  If one allows
all reals as ratios (and I guess we can suppose this, since it is a
physical machine), then it is easy to see that a non-computable
sequence will be outputted (if the universe does not end).  Does this
imply Church's Thesis is false?  Not at all!  The procedure being used
is not an effective procedure:  it depends on a quantity r1/r2 which
is not effectively determined.
    Sidenote:  it is interesting to note that two finite-state
machines (with infinite input tapes) communicating as indicated still
cannot calculate the palindrome or multiplication functions.  So they
can calculate non-computable functions but not multiplication!