Manuscript circulated privately since 1982. Written September 19,
1982; reset May, 1994. © 1982, 1994 by Jon Doyle.

# What is Church's Thesis? An Outline

Jon Doyle

September 19, 1982

In memory of Henry Aloysius Miller

What is Church's thesis? In bald statement, that the effectively
compatable functions are the same as the recursive functions. But
thinking carefully about this and other issues has led me to suspect
both the formulation and accuracy of this thesis. This paper sketches
my doubts.

The first three characters on the stage are **RF**, the recursive
functions; **OP**, the physics of our universe; and
**E**_{1}, the functions computable by (say) the physical
operations described by Turing (that is, writing symbols from a finite
set of rules.)

The first formulation of Church's thesis is *The functions*
**E**_{1} *computable *in principle* by Turing's
operations in* **OP** *are the same as* **RF**. By ``in
principle'' we mean to neglect the (supposed) finiteness of matter in
our universe.

There are many reasons for thinking the identity of
**E**_{1}(**OP**) and **RF** to be a (fortuitous)
accident of our universe. Gandy attempts to describe, in his Kleene
symposium paper, ways in which slight variations in **OP** make
**E**_{1} include non-recursive functions, simply by
allowing the ``same'' physical operations to involve more information
or information paths than usual. It is also to imagine variations in
**OP** so that **E**_{1} is a proper subset (even
empty!) of **RF**. For example, if physics allowed no matter, or
only gases, the Turing's operations would not be physically
realizable, so **E**_{1} would be empty.

The fourth character of our story, **E**_{2}, is the set of
functions computable by an extension of Turing's operations. That is,
**E**_{2} embodies a different notion of what are
``elementary effective operations''. My idea is this. One of the
most common abstract phenomena in our world is that of equilibriating
systems: parts of the universe that settle into one of a spectrum of
equilibrium states often certain boundary conditions are imposed.
There are, in fact, many equilibriating systems with discrete spectra,
for example the quantum states of molecules. Given the definiteness
of these systems, we might take the operation of equilibriating as an
effective one. Note carefully, I do not mean that equilibria are
computable by Turing's operations, but that equilibriating can be so
easily, reproducibly, and mindlessly accomplished that we grant it
equal status with marking and moving slips of paper.

My suspicion is that physics is easily rich enough so that
**E**_{2},
the
functions compatable *in principle* given Turing's operations and
equilibriating, include non-recursive functions. For example, I think
that chemistry may be rich enough that given a diophantine equation,
we can recursively compute a molecular structure (teflon, DNA,
proteins, etc.) that has been a quantum level within some interval iff
the diophantive equation has a solution. That is, we plug values into
the molecule as boundary conditions, and solve the equation iff the
molecule finds an equilibrium. Of course, we must still have ``in
principle'' in our claim, since matter is still finite, and possibly
because engineering limitations may prevent successful manipulation of
arbitrarily sized molecules. But I think it reasonable to change our
accepted definition of ``elementary effective operation'' to include
equilibriating, and to investigate the inequality of
**E**_{2}
and **RF**.

I have heard of proofs announced that differential equations can
transform states with recursive sets of state-variable values into
states with non-recursive sets of values. My suggestion, if valid, is
a special case of those proofs. But the ``effectiveness'' of
equilibriating seems much more acceptable than that of arbitrary
differential equations.

As a final footnote, observe that if the natural numbers and
arithmetical operations can be embedded in chemistry, then the theory
of chemistry, and of the physical world, is incomplete and cannot be
consistently made so. Necessary incompleteness need not be an
affliction suffered only by mathematics.