FOM: Odifreddi on Church's Thesis [long]

Sat Nov 7 19:58:55 EST 1998

The following is a short summary of discussion of Church's Thesis
in Odifreddi's _Classical Recursion Theory_, pp. 101-123. The
list of the 8 versions of the Thesis defined therein is at the
end of the message.

First, the Thesis itself:

   Church's Thesis. Every effectively computable function
   is recursive.

It's important to distinguish between two uses of the Thesis. It's
often used in a relatively unimportant way: instead of formally 
defining a Turing machine or a lambda-calculus term etc. computing
a certain function, we show why it's "obviously" effectively computable,
often by sketching an informal algorithm. When we then conclude that
it's really recursive, we're using the Thesis, but in an inessential
way: all such "shortcuts" can in practice be replaced by strict
formalization which is usually straightforward, though tedious.
The essential use of the Thesis, on the other hand, is when we
declare a problem _unsolvable_ (or the function _uncomputable_)
on the basis of its being _non-recursive_. 

The Thesis, as stated, is ambigious in several ways. First of all,
instead of formulating it for functions, one may formulate a
(possible stronger) version, which Kreisel calls

   Superthesis: Every effective *rule* is intensionally equivalent to
   a program for an idealized computer (say, a Turing machine).

The more important distinctions, however, arise from different
meanings of "effective" that one can consider. Such meanings fall
naturally into two classes: in the first are found different kinds of 
"effective" _physical_ behavior, while in the second "effective"
is taken to mean "computable in principle by human beings". We will
examine both classes in turn, further refining possible meanings
of "effective" inside each of them.

[this high-level division into physical and biological corresponds
to Martin Davis's C_T_1 and C_T_2; Odifreddi also neglects to mention
that the classification itself presumes realism as the underlying
philosophy - AV]

Computers and Physics   [C_T_2 - AV]

Even though we no longer believe that the world around us works
according to the laws of classical mechanics (with or without
relativity; what matters here is determinism), these laws do provide
excellent approximation in most cases; furthermore, it's an easier
case (to argue Thesis's truth in) and deserves to be treated separately.

We thus define

   Thesis M (for 'mechanical'): The behavior of any discrete physical
   system evolving according to local mechanical laws is recursive.

[the word 'local' above is essential; in some strange cases, the
behavior, or a law, may hold locally but not globally. The passage from
local to global involves taking an integral over the universe, and 
it may be consistent that the integral doesn't exist]

Arguments in favor of Thesis M fall into three distinct categories:

a) A general theory of discrete, deterministic devices has been
created; it is based on two chief assumptions, atomism (allows to 
theoretically consider the set of basic constituents) and relativity
(gives an upper bound on the propagation speed of causal changes,
imposes locality of action). Gandy has shown that

  behavior is recursive, for any device with a fixed bound on the
  complexity of its possible configurations, and fixed finite,
  deterministic sets of instructions for local and global action.

His analysis is optimal in the sense that any relaxing of the
conditions above becomes compatible with any behavior. 

b) Kreisel has analyzed Thesis M for systems defined (continuously)
by local differentiable equations. One considers a Hamiltonian of
the system; if the relevant derivatives are assumed to be smooth
enough, Kreisel shows that, after stepping from continuous to
discrete time with any needed precision, one obtains recursively
described system evolution, in the sense of simultaneous recursive
definition of all the parameters describing the system state.

c) In classical mechanics, the laws have traditionally been given
as differential equations in a continuous model, from which 
discrete data is later approximated. If the universe is actually
discrete, this step through continuous may possibly be regarded
as superfluous. In fact, discrete models have been built for classical
mechanics, including special relativity (Greenspan, La Budde); for
computation they rely on high speed arithmetic, the dynamical evolution
is governed by difference (rather than differential) equations. 
Recursiveness of discrete behavior is, naturally, much easier to
conclude for such models.

To sum up the discussion for classical mechanics, it's plausible that
Thesis M holds.

Probabilistic Physics

To generalize to all physical phenomena, and not just those governed
by classical mechanics, we define

   Thesis P (for 'probabilistic'). Any possible behavior of a discrete
   physical system (according to present day physical theory) is recursive.

The word 'possible' is essential because of nondeterminism inherent
in quantum mechanics. A discrete physical system may be viewed
conceptually as an *probabilistic analog computer*, and Thesis P 
then claims that any such computer can be simulated on a usual digital
computer (more precisely, on an idealized computer such as Turing machine).

a) A general theory of analog machines has not been built. Shannon [1941]
has generalized a notion of finite automaton into that of a _general
purpose analog computer_, which consists of electronic circuits and
several possible kinds of "black boxes" which are presumed to react
instanteneously. The black boxes can output constant voltage, add,
multiply and integrate voltage on its inputs. The function that the
device "computes" is the output voltage as a function of time. Such
function have been characterized as being exactly the _differentially
algebraic_ functions; however, even the theoretical details of their
possible simulation by digital devices (which is necessary to
talk about functions from integers (rather than from reals) which is what 
we're interested in in) have not been worked out; and it's obvious that
this model doesn't come close to covering all kinds of analog physical
systems. 

b) _Classical_ probabilistic systems are described by Markov chains;
the behaviour is governed by stochastic matrices. Kreisel shows that
if such a transition matrix is recursive, any sequence of states with
non-zero probability is recursive. This analysis, however, doesn't
apply to quantum physics.

Pour El and Richards [1979] show a computable differential equation
(i.e. with computable parameters), the solutions to which aren't
recursive. However, Kreisel [1982] argues that such equations are
sufficiently twisted so that they do not arise as descriptions of
real physical phenomena, under current physical theories.

c) Finally, Odifreddi talks about deterministic models of quantum
mechanics, describing the work of Bell which exhibited strong
evidence against such _hidden-variables_ theories. Odifreddi does
not, however, attempt to deal with possibility of proving
nonrecursive behavior in a strictly quantum-mechanical system. 
The conclusion is

   We have only scarce evidence in favour of Thesis P and despite the
   fact that no outright refutation exists, there's plenty of room to
   doubt its validity.

Computers and Thought   [C_T_1 - AV]

The first global approach to the Church's Thesis as applied to human
thought is to look at the brain:

   Superthesis B (for 'brain'): The brain is a machine.

The possibility has been first raised, it would seem, by Descartes.

It seems that due to our very scarce knowledge about how the human
brain works, we are forced to suspend judgement on Superthesis B.
One curious possibility is that, due to the enormous complexity
involved, the brain's workings, though describable mechanically,
couldn't be described feasibly; in terms of Kolmogorov complexity,
the brain might turn out to be a random object.

[Some thinkers have stressed the importance of limimation results,
such as undecidability of the halting problem, or Godel's
incompleteness theorems, as refuting any purely deterministic 
model of brain. Especially known lately are Roger Penrose's books;
his arguments, however, are definitely not regarded generally
as conclusive, and in fact regarded by some as incoherent]. 

After a discussion of current advances in neural nets and other
similar ways to simulate brain's workings, Odifreddi notes that 
all such attempts aren't necessarily related to the brain itself
(after all, artificial "neurons" in neural nets aren't anything
like real neurons in the brain, etc.) but may be regarded as
contributing (however scarce) evidence to another version of the
Thesis, namely

   Thesis AI (for 'Artificial Intelligence'): The mental functions
   can be simulated by machines.

Finally, in an attempt to isolate what really interests us, namely,
_mathematical thought_ (and not just any mental functions), we 
formulate

   Thesis C (for 'constructive'): Any constructive function is
   recursive.

"Constructive" here is not to be taken in the intuitionistic sense,
but rather as broadly as possible: any function we can imagine
ourselves as being able to compute.

Note that even establishing Superthesis B (that brain is a machine)
proves automatically Thesis C; an additional philosophical assumption
of _psychological materialism_ is needed: namely, that human thought
is determined solely by the brain, with no intervention of any
extraphysical mind. On the other hand, only if Thesis C fails and
Superthesis B holds are we able to prove that some kind of extraphysical
mind does exist (and contributes to nonrecursiveness of constructive
functions). Godel, on the other hand, has suggested a curious 
possibility which would prove existence of extraphysical mind: the case
in which we would be able to show that there isn't sufficient structure
(at the nerve level in the brain) to account for all mental activity
performed by humans.

As to Thesis C itself, the direct approach to it isn't easy because
"constructive" is a very vague notion. It is possible, however, to prove
recursiveness of a completely *routine* computation by a human agent;
such an analysis has been carried out by Turing and Post. 

[Odifreddi does it in an earlier section, by abstracting away all
the activity of a human agent performing a completely routine computation,
until he's reduced to a role of a Turing machine head, and at this point
he might as well be replaced by that head; Shoenfield does it in his
logic book, if I recall correctly, by considering any computation carried
in a routine way using pen and paper - AV]

What is actually *proved* by such analysis is

   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.

Superthesis R, however, is a far cry from Thesis C; especially since
_constructive and routine/mechanical are apparently independent 
concepts_: we understand easily (by grasping abstract objects) 
nonmechanical rules, and do not understand rules which, although
mechanical and routine, are too long or too detailed.

Therefore, our only means to analyzing Thesis C seem to be by
analyzing contructive mathematical thought. This leads us to
a discussion of formalism, finitism, platonism and intuitionism.

Strict formalism and strict finitism are easily seen to imply
Thesis C, since functions defined finitistically or by formal
axiomatic systems are recursive. Platonism is essentially
non-constructive, so the remaining problem is to decide what
to think of Thesis C in context of intuitionism. We concentrate
on formal systems, and note that since recursive functions are
exactly those representable in formal systems (by arithmetization),
Thesis C could actually be proved by exhibiting a formal system
corresponding to our constructive mathematical intuition [doesn't
this somehow ring a bell with feasibilists' efforts? - AV]. 

[Odifreddi then spends some time to ponder at length at various
possibilities of analysis of intuitionistic formal systems (without
any really interesting results) which to me seem marginal at best, 
so I omit them. He's also gravely mistaken, in my opinion, in his 
dismissing platonism in the analysis of constructive functions
in the broad sense of the word]

The conclusion we have for Thesis C is that

  we have collected very weak, and certanly inconclusive, evidence
  in favor of Thesis C, and its validity must therefore remain
  as unproved (which isn't surprising given the fact that we only
  have a very partial grasp of what 'constructive' means).

[I stress that views expressed are Odifreddi's, not mine; I've
merely summarized. Any distortions are mine and unintended].

For reference, here're again the versions of the Thesis defined
above: