From: "Perry E. Metzger" <perry@imsi.com>
Date: Mon, 25 Jul 94 20:07:04 PDT
To: jamesd@netcom.com (James A. Donald)
Subject: Re: GUT and P=NP
In-Reply-To: <199407230457.VAA19186@netcom13.netcom.com>
Message-ID: <9407250125.AA10242@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



James A. Donald says:
> Ray writes
> > 1) By definition, if something can be computed by a turing machine,
> > then it is an algorithm (Lewis and Papadimitriou)
> 
> Suppose we have a spatial transform performed by light flowing
> through a grid.  Is that an algorithm?   Perhaps it is, but I
> am about to describe a case that will stretch your definition
> of algorithm rather more drastically.

Suppose I have a frog. Is that an algorithm? Obviously not.

On the other hand, suppose I define something that takes an input tape
and turns it into an output tape. Is that something in the space of
things we are talking about? Yes.

The Church-Turing thesis is that if you are talking about the space of
"things that turn input tapes into output tapes and end in particular
states", turing machines are capable of doing any sort of
transformation other things can, although perhaps taking longer to do
so. I can believe that (possibly) quantum computers are faster, but it
would be truly shocking to discover that they did some things that
turing machines couldn't given enough time.

Perry