FOM: Church's thesis and complexity theory

[Joe Shipman]

The class of recursive functions has many natural and equivalent
definitions and possesses a sort of absoluteness.  But I am a little
troubled by the identification of this class with "effectively
computable functions".

After all, any recursive function we can compute in practice is
primitive recursive, in fact elementary recursive, which suggests
Church's thesis is too broad.

On the other hand, "polynomial time" may be too narrow a class to
capture all that is "effectively computable", because there is no proof
it includes all functions feasibly calculable by probabilistic
algorithms or by quantum computation.

This posting is to solicit suggestions for a sharper definition of
"effective computability".  Given the current theories of fundamental
physics, I would think it most unlikely that any (informally)
effectively computable function is not in EXPSPACE; I'd like to see
arguments based on sound physics that a smaller complexity class than
EXPSPACE also includes everything that deserves to be called
"effectively computable".

Coming from the other direction, it is *conceivable* that some
nonrecursive (but mathematically well-defined) functions ARE effectively
computable; the reigning physical theories are not formulated precisely
enough that this can be ruled out.  Hartle and Hawking's cosmological
model involves sums over homeomorphism classes of 4-dimensional
manifolds; since these classes form a nonrecursive set there is no
obvious way to calculate what the model predicts.  This is not yet a
violation of Church's thesis, but it does show that the processes by
which nature "computes" are not necessarily recursive.

-- Joe Shipman