[FOM] Re: A Newtonian computing design
toby.ord at philosophy.oxford.ac.uk
Fri Feb 13 16:28:26 EST 2004
On 12 Feb 2004, at 21:48, Timothy Y. Chow wrote:
> I believe that the same sort of considerations should apply to almost
> kind of thought-experiment of this type, regardless of whether
> or modern physics underlies the experiment. Trying to "solve the
> unsolvable" is probably going to involve extrapolating physics to
> arbitrarily extreme limits, beyond what we can measure. Even if we
> had physics that was stable for 1000 years that we had tested over and
> over again, the testing would take place within finitely measurable
> and our confidence could not justifiably be extended to realms in which
> we had no ability to confirm the theory experimentally.
Perhaps Harvey Friedman's suggestion (in another post) can do more to
convince you here. If this alleged hypercomputer was used to test a
slew of halting problems whose answers we knew but were very hard won
(does the TM that halts if and only if Fermat's Last Theorem is true
halt?) then this would count as testing the theory in this domain.
Assuming, of course, that we had some understanding of the workings of
the machine. If it were just a friend coming up to us with a black box,
we might have reason to believe it contained a TM with many Sigma-0-1
theorems coded into it. We would have to have some reason to believe
the machine wasn't so rigged, but I don't think this is that hard to
> Let me switch gears slightly by making a more positive suggestion that
> just occurred to me yesterday. Instead of using the slogan "computing
> the uncomputable," how about using
> *solving any decidable problem in constant time*
Firstly, I have to say that I think the slogan "computing the
uncomputable" is most unfortunate and this appearance of sheer
contradictoriness causes much of the initial negative reaction some
have to hypercomputation. Of course, this problem is just due to some
historical question-begging terminological choices. I would personally
use "computing non-recursive functions" which is by no means
oxymoronic. Indeed, when writing on the topic, I take great care to
refer to the mathematical notion of recursiveness by that name only. I
think it is unfortunate that there is a trend towards terminology that
conflates the two (such as the move from r.e. to c.e.) and which
similarly begs Church's Thesis or some physical version of it. I don't
really understand why this has happened, but it is important not to be
put off by the historically odd terminology.
> Some advantages of this are:
> 1. It seems to capture the spirit of many of the proposals for
> hypercomputation that I have seen. That is, if these proposals
> work as they are supposed to, then they should also be able to
> solve any decidable problem in constant time.
> 2. It avoids the recursive/non-recursive issue, which I have
> argued is a complete red herring, leading to protracted and
> irrelevant arguments about various Church-Turing theses.
I don't understand. Surely it is important whether or not one can solve
the halting problem. That is the type of thing I am interested in when
I study hypercomputation. This is the crux of the matter and not
> 3. It sidesteps entirely all the objections I have been raising,
> by concentrating attention only on finitely verifiable computations.
> 4. It would still make trillions of dollars and be an incredible
> scientific breakthrough.
> 5. It naturally directs attention towards the all-important practical
> implementation issues (making sure that no assumptions of infinitely
> powerful engineering ability are used) rather than towards arcane
> questions about whether certain physical theories are "non-recursive"
> in an unusable way.
> One disadvantage might be that adopting this slogan does mean
> the hope of (affirmatively) settling the consistency of ZFC by a finite
> physical experiment, but as I argued before, I don't think this was
> in the cards in the first place.
Yes, but do you see that you are ruling out what is at question here? I
agree that constant time computation of all recursive functions would
indeed be spectacular if possible and think it is quite interesting
that there is an overlap in methods for this constant time computation
and for hypercomputation. Indeed, I even think that investigators of
methods with this side effect should examine it and be quite explicit
about it, but in the end, it is an independent question.
> The new slogan might be less sensational, which might be bad if the
> goal is to capture the attention of journalists and of funding sources.
This seems a little unfair.
More information about the FOM