FOM: Church's Thesis -- various versions

Joe Shipman shipman at
Mon Nov 9 12:50:28 EST 1998

Thanks to Vorobey for his summary of Odifreddi's classification.  My own
view of them is:

   Church's Thesis. Every effectively computable function
   is recursive.
Evidence for this is shaky, see "P" below

   Superthesis: Every effective *rule* is intensionally equivalent to
   a program for an idealized computer (say, a Turing machine).
If "rule" means something ordinary, this is similar to "R" below which I
agree with

   Thesis M (for 'mechanical'): The behavior of any discrete physical
   system evolving according to local mechanical laws is recursive.
Yes, key words "discrete" and "local"

   Thesis P (for 'probabilistic'). Any possible behavior of a discrete
   physical system (according to present day physical theory) is
Not clear, physics is definitely nonlocal (Bell, Aspect) even for
discrete systems

   Superthesis B (for 'brain'): The brain is a machine.
It's obviously a physical system, this is too vague unless "machine" is

   Thesis AI (for 'Artificial Intelligence'): The mental functions
   can be simulated by machines.
Again depends what you want to call "machine" -- if you mean Turing
machine the evidence is very scanty.

   Thesis C (for 'constructive'): Any constructive function is
You're right to note the philosophical assumption of psychological
materialism here.  But what you call an  "extraphysical mind" may turn
out to really be physical but nonlocalized (and hence not strictly
contained in the brain).

   Superthesis R (for 'routine'): Any computation performed by an
   abstract human being working in a routine way, is isomorphic to
   a computation performed by a Turing machine.
Sounds very plausible, key words "abstract' and "routine".

If nonrecursive functions are accessible experimentally, it will be
because the universe is either
 1) nonlocally connected
 2) not locally finite.
Feynman put it best: the question is whether it should take a finite
amount of information to describe what is going on in a finite region of
spacetime.  A "yes" answer supports all forms of Church's thesis; but we
have two reasons to suppose the answer might be no.  First, quantum
mechanics appears to involve nonlocal interactions (Bell inequality
violated), and second, the probabilities of some observed phenomena
represent sums over infinitely many scenarios (e.g. Feynman diagrams in

It's a separate question whether the workings of the brain participate
in this nonlocality and nonfiniteness in a way that is relevant to the
mind.  The working assumption that they don't seems reasonable, and
supports B, AI, C, and R -- so the only way we could "get" a
nonrecursive function is by conducting an experiment (building a device
and running it).  But for now that's also the only
way we can get a recursive function that is too complex to be calculated
"by hand".

--Joe Shipman

More information about the FOM mailing list