FOM: Effective and feasible computability (reply to Davis)

[Joe Shipman]

Martin Davis wrote:

> I am ignorant of this work by Dyson & Tipler, and can't comment on it. I
> have two comments, nevertheless:
> 1. I do not agree that CT can in any way be effected by whether this physics
> is or is not correct.
> 2. Even if there are infinitely long computations being physically realized,
> thta does not in itself imply that there can be a physical device that can
> compute with infinitely many different inputs.
>
> Martin

1. As I stated, the work of Dyson and Tipler allowed for arbitrarily long but not
infinite computations, and it used standard physics.

2. Are there ANY circumstances which would cause you to admit that Church's thesis
was false?  Do you think that an oracle for the halting problem is like a perpetual
motion machine, something that the laws of physics as currently understood rule
out?  It may be that the models of Dyson and Tipler, which use standard physics, do
not affect CT, but standard physics is incomplete and it is logically possible that
some extension or correction of it which is experimentally supported allows for the
construction of a machine which really does do infinite (rather than arbitrarily
long finite) computations.  After all, even in the current best theories "nature"
does infinite computations (adding up terms from infinitely many Feynman diagrams
for example -- even the term from an individual Feynman diagram can be regarded as
the sum over infinitely many paths), and in at least one speculative theory (Hartle
and Hawking's cosmological model) the terms are of an infinite sum are indexed by a
nonrecursive set.

3. I can't understand your point about "a physical device that can compute with
infinitely many different inputs".  The input can be fed in one bit at a time, just
as for Turing machines.  Any arguments of this sort apply equally well to
conventional computers as to the hypothetical ones I am contemplating the
possibility of.

The "discovery" ("invention"?) of quantum computers showed that physics allows for
computations of a very different type than the ones Turing machines do; although it
has been said that "quantum computers do not violate Church's thesis" this has only
been shown for particular models of quantum computation.  Those proofs say nothing
about the possibility of experimentally generating a nonrecursive function using
physical systems more general than the ones discussed in the literature of Quantum
Computation.

-- JS