[FOM] On Physical Church-Turing Thesis

[Toby Ord]

On 8 Feb 2004, at 22:55, Dmytro Taranovsky wrote:

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

Do you have any references to precise formalizations of this kind? In 
my experience it is quite difficult to distinguish random non-recursive 
computation from the non-random kind. For example, consider the 
(admittedly hand-waving) case of a universe in which recursive 
computation is physically possible, as is fair coin tossing and every 
computation formed by combining them. In this case, one could imagine a 
machine that takes n as input and flips a coin, adding one to n if it 
is heads and leaving n unchanged otherwise. This computes a 
non-recursive function (with probability one), yet I imagine you would 
not want to count it as non-recursive computation.

One way to approach this is to say that it is not replicable, but 
consider the alternate formulation in which we have one machine that 
does the coin flipping and produces an ever growing table of flips. 
Then other machines can use this table as many times as they want, 
computing the same non-recursive function every time. It is not obvious 
exactly how to rule out this class of computations.

My preferred option is to speak of 'harnessable' computations, saying 
that 'All harnessable (deterministic) physical computation is 
recursive' and holding that a computation is harnessable iff the 
function it computes can be known by some precise finite description. 
By this I would include the halting function and all functions finitely 
specified in first order arithmetic and many others, but I don't know 
how to make this more precise (as it needs to be).

I do think that there are separate hypotheses regarding:

a recursive universe
a recursive universe + a certain type of randomness
a non-recursive universe

but I don't know how these can be precisely formalized.

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

I am not so sure and know that some suspect the opposite. For example, 
Newtonian mechanics was recently shown to be much stranger than we 
suspected, with infinite travel in finite time and so on. There is also 
a paper on doing infinite computation via a succession of increasingly 
small machines (E. Brian Davies, Building Infinite Machines, BJPS). 
Perhaps you would say that Newtonian Mechanics is not internally 
consistent, but in this case, the set of all widely used physical 
theories that satisfy your constraints is no doubt empty at the moment. 
(This is not a problem per se, but worth pointing out).

> (If the theory, like general relativity,
> depends on external parameters or fields, recursiveness of the
> parameters is part of the hypotheses of such theorems).

One would want to justify such hypotheses...

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

Tien Kieu is such a specialist whom I have worked with extensively on 
this topic and cannot see any reason at all as to why QM would prohibit 
non-recursive computation. Indeed, he has suggested how it can allow 
the solving of hilbert's tenth problem (and thus all Sigma_1 and Pi_1 
problems) via the Quantum Adiabatic Theorem. There has been a technical 
criticism of Kieu's method, but he believes it to be satisfactorily 
answered. See Kieu, 'Computing the Noncomputable'.

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

As has been pointed out in another current post, this problem (as put) 
is no different from knowing whether or not a given computer (with 
unbounded memory) is computing multiplication. In all such cases, an 
infinite amount of functions are compatible with our (at any stage) 
finite data. I don't see any new problem here and think that we should 
(and would) be entirely prepared to accept the halting problem answers 
given by a machine that our physics led us to believe could indeed 
solve the halting problem.

Also, the same argument can be put in terms of the rationals and an 
alleged physical quantity of pi units (such as in the ratio of the 
length of a physical circle to its diameter).

> I personally believe that not everything we do and observe is
> recursive.

I am unsure. I don't see any great evidence either way, but think that 
there should be more realization that this is one of the great unsolved 
questions in physics with potentially very large implications.

There are also many rather bizarre limitations that recursive physics 
would place upon the universe. For example, it would mean that no 
measurable quantity (in some currently under specified sense) could 
grow faster than the busy beaver function or slower than the inverse of 
the busy beaver function. It also means that no measurable quantity 
could converge to a value faster than the reciprocal of the busy beaver 
function or slower than the reciprocal of the inverse of the busy 
beaver function. I am currently unaware of any result remotely like 
this in physics, but it is the type of thing that falls out for free if 
we find that physics is (in some appropriate sense) 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.

I hope so.

Toby.