[FOM] On Physical Church-Turing Thesis
toby.ord at philosophy.oxford.ac.uk
Tue Feb 10 16:47:20 EST 2004
On 8 Feb 2004, at 22:55, Dmytro Taranovsky wrote:
> In this posting I discuss the physical Church thesis and its relation
> 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
> 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
> 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
> a demonstration of its negation would require not only observations of
> non-recursive physical phenomena, but also a philosophical argument
> 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
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
> with new scientific discoveries and theories, and a revolution in
> knowledge in general, may resolve the status of the physical Church
I hope so.
More information about the FOM