FOM: Effective and feasible computability

[Martin Davis]

At 11:52 AM 11/2/98 -0500, Joe Shipman wrote:

>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.
>

Since in all likelihood no physical device is capable of dealing with more
than a finite number of inputs (because the universe is likely finite),
Church's Thesis is not a "statement of physics".

I think (idiosyncratically) that talk about feasible computation as
identifiable with PT-computability is fundamentally flawed because of the
strong finiteness of everything real. Although I do not care for Sazonov's
philosophical ideas, I think that from a technical side, these might be a
much more promising approach to computational feasibility.

Martin