FOM: Effective and feasible computability

[Joe Shipman]

In my posting of October 31 I asked for alternative definitions of
"effective computability".  I realize now that there may be some
confusion whether I am actually asking for a definition of "feasible
computability", so I am posting this clarification.

I am looking for an answer that is informed by our knowledge of physics
(and possibly other sciences) -- there must be some dependence of the
answer on our being inhabitants of THIS universe rather than disembodied
intellects.  I see Church's thesis as a statement of physics.  To say
that Ackermann's function or Friedman's function n(k) is computable "in
principle" could mean either
 1) in principle by an idealized machine (finite-state-machine with
external memory = Turing machine for example)
 2) in principle in our physical Universe.
In the first case we apparently get the general recursive functions for
any reasonable idealized machine.  In the second case we may get (if the
Universe is totally finite in some sense) a finite set of finite
functions, or we may get some subclass of the general recursive
functions, or we may even get some superclass of the general recursive
functions if Church's thesis is false.

"Feasibly computable" seems a fuzzier concept than "effectively
computable" -- I am willing to wait "as long as it takes" for the answer
for an effectively computable function.  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.

But even for "feasibly computable" the question is interesting --
various people have proposed PTIME, BPP, and QPTIME (which can be
rigourously defined for one of the standard models of quantum
computation and shown to be within P^(#P) ), but other answers are
possible (for example if you allow exponential classical parallelism
rather than the exponential "quantum parallelism" used in the standard
models of quantum computation; this makes sense in some models of the
universe as a cellular automaton with "free-group" rather than
"free-abelian-group" connectivity).

-- Joe Shipman