Manuscript circulated privately since 1982. Written September 19, 1982; reset May, 1994. \begin{matrix}c \\ ◯ \end{matrix}1982, 1994 by Jon Doyle. All rights reserved.

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