FOM: Church's thesis and complexity -- reply to Sazonov

[Joe Shipman]

> > Both Freeman Dyson (in the case
> > of an open Universe) and Frank Tipler (in the case of a closed
Universe)
> > have argued that arbitrarily long computations are permitted by the
laws
> > of physics.
>
> What do they mean by "arbitrarily long computations are permitted
> by the laws of physics"? Say, as long as 2^{2^{2^1000}}? Is this
number
> "permitted" if it is known (from physics!) to be much-much bigger
> than the number of electrons? Can anybody comment?

Yes, they do mean as long as 2^2^2^1000.  The large numbers can be
"coded" by
energy levels if there are a finite number of particles (this is the way
Tipler
accomplishes it but he needs a closed universe -- as the Universe speeds
toward
the Big Crunch more and more things can happen in each increment of time

(subjective time speeds up)), or represented by very large numbers of
very very
low-energy photons (this is the way Dyson accomplishes it but he needs
an open
universe -- as the Universe expands and cools fewer and fewer things can
happen
in each increment of time (subjective time slows down)).

Regarding Church's thesis, I claim it is a statement of physics because
it is
potentially empirically falsifiable (if we discover how to physically
construct
an oracle for the halting problem for example--this is not ruled out by
the
current laws of physics).  Universes in which there is an effective
procedure
for determining whether Diophantine equations have solutions are
certainly
*imaginable*, so it is a real empirical question whether we live in such
a
Universe.

My distinction between "effective" and "feasible" is not related to
Friedman's
between mathematical and physical theories -- both concepts are meant to
refer
to the physical universe we live in, with a feasible computation being
something that gives an answer within our lifetimes (using some
physically
plausible model of computation such as TM's, probabilistic TMs, Quantum
Computers as formalized by Yao, or something more exotic) and an
effective
computation being something that is possible in principle as in Dyson's
and
Tipler's models.  I am soliciting sharper definitions for both of these
concepts.

You may believe that Church's thesis is correct or that all feasible
computations are actually in PTIME, but these are statements about the
physical
universe and "pure thought" arguments which make no reference to actual
physics
(or any other empirical science) cannot settle them.

-- JS