[FOM] On Physical Church-Turing Thesis

[Dmytro Taranovsky]

In this posting I discuss the physical Church thesis and its relation to
physical theories.  The physical Church thesis claims that every
physically realizable machine is recursive but for the ability to pick
random numbers.  A related claim is that every mental process is
recursive (but for random choices).  

These claims are *not* due to Church or Turing.  The thesis as
formulated by Church and Turing involves finite computation by human
mind without insight or ingenuity and without use of non-recursive
physical machinery.  That thesis is vague because of ambiguities in
"without insight or ingenuity"; if these terms are defined narrowly,
then the thesis essentially becomes vacuously true.

----------
The scenario in "Non-Turing computations via Malament-Hogarth
spacetimes" by Etesi and Nemeti involves traveling into a rotating black
hole through the inner horizon.  In that scenario, the observer reaches
the inner horizon in finite proper time but an infinite amount of time
elapses outside the black hole, allowing arbitrarily long calculations. 
Thus, a computer outside the black hole could check for consistency of
ZFC and if an inconsistency is found, send a signal to the observer. 
The observer after reaching the inner horizon would conclude that ZFC is
consistent iff no signal is received.  That scenario would allow
resolution of all Sigma-0-1 questions, but reaching a higher level would
require a different scenario.

I suspect that the scenario is unphysical because it involves crossing
Cauchy horizon and what happens after an infinite amount of time has
elapsed.  In most models, the observer would encounter infinite blue
shift and a deadly singularity at the inner horizon.  Because as the
observer approaches the horizon the blue shift approaches infinity,
there is likely a practical limit on how late a signal can be sent
without destroying the observer.

Although general relativity does not rule out non-Turing computations,
under reasonable assumptions, it allows for the initial value problem. 
An exact description of the initial state gives exact (up to a choice of
coordinates) time evolution of the state up to the Cauchy horizon, which
in the scenario above coincides with the inner horizon.  Past the Cauchy
horizon, general relativity does not predict time evolution of the
state, but according to the strong cosmic censorship hypothesis the
Cauchy horizon does not exist or cannot be crossed alive, so absence of
Cauchy horizon is a reasonable assumption.  

Given a sufficiently precise but finite description of the initial state
one can obtain an approximation for time evolution of the system along
with upper bounds on the error.  As the description becomes arbitrary
precise, the predicted time evolution becomes increasingly accurate,
with the known upper limit on error approaching zero.  Thus, traversal
of Cauchy horizons aside, and assuming that measurement in finite time
can be done only to a finite accuracy (example:  the measured length of
a rod can be 3.14159 plus or minus 0.00001 meters but not pi meters), a
non-recursive computation in general relativity is possible only if
there is a method for non-recursive computations not involving general
relativity.
----------

I suspect that all widely used physical theories that do not suffer from
internal inconsistencies or absence of a rigorous formulation admit a
mathematical proof whose physical interpretation is impossibility of
non-recursive computation. (If the theory, like general relativity,
depends on external parameters or fields, recursiveness of the
parameters is part of the hypotheses of such theorems).  

It would be interesting to hear from a specialist whether the Standard
Model allows only recursive computation.  If so, then any hope of
physical realization of non-recursive computation would require
currently unknown physical phenomena (or non-recursiveness in parameters
such as the fine structure constant).

Although the physical Church Thesis may appear to be an empirical claim,
a demonstration of its negation would require not only observations of
non-recursive physical phenomena, but also a philosophical argument that
the observable pattern is in fact non-recursive rather than being
produced by a complicated and unknown but recursive rule set.  For
example, if some physical constant turns out to equal 0# (a
non-recursive real number), a philosophical argument is needed to show
that the constant is actually 0# rather than a different real number
masquerading as 0#:  Comparison of data with theory is possible only if
one can compute the theoretical prediction, which is problematic if the
theory makes non-recursive predictions.

I personally believe that not everything we do and observe is
recursive.  For example, the search for axioms of set theory can be
fully successful only if it is non-recursive.  The twenty-first century,
with new scientific discoveries and theories, and a revolution in
knowledge in general, may resolve the status of the physical Church
thesis.


Dmytro Taranovsky