From: rjc@gnu.ai.mit.edu (Ray)
Date: Sat, 23 Jul 94 02:56:45 PDT
To: jamesd@netcom.com (James A. Donald)
Subject: Re: GUT and P=NP
In-Reply-To: <199407230457.VAA19186@netcom13.netcom.com>
Message-ID: <9407230956.AA28103@geech.gnu.ai.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain


James A. Donald writes:
> Ray writes
> > 1) By definition, if something can be computed by a turing machine,
> > then it is an algorithm (Lewis and Papadimitriou)
> > 2) a quantum computer can be simulated by a TM with exponential 
> > slowdown. (claimed by you on the Extropians list, but also
> > claimed by Feynmann I believe, not about qm computers, but qm systems
> > in general)
> 
> True.

  Therefore it is an algorithm.
 
> > then by (1) and (2), it follows that
> > 3) quantum computers are algorithmic (if not, it would contradict
> > 2) and possibly 1)
> 
> Suppose our quantum system has thirty two bytes.
> 
> Then a classical simulation of our quantum system would require
> 2^257 words of memory
> 
> The computer would require more matter than exists in the universe.
> 
> Each step of the simulation would require 2^514 steps by the computer,
> which even for a computer constructed of very tiny components out
> of all the matter in the universe would still require vastly longer
> than the entire lifetime of the univers.

   We are not talking about physical computers, we are talking about
turing machines. If there is some *finite* deterministic process to
get from the initial data to the final result, no matter how long it
takes, it is an algorithm. I'm sure I could hand you a composite
number that would require a computer larger and older than the
universe to factor. Does that prove that none of our current factoring
algorithms are actually algorithms, or that brute force isn't an
algorithm?

   If you have a different definition of "algorithm" then perhaps your
argument is right, but to me, an algorithm is a process to
get from A to B, regardless of how long it takes.

> > 
> >    It doesn't matter how slow the turing machine runs the simulation
> > because we allow an arbitrary time along with the infinite tape
> > to complete the computation. 
> > -Ray
> 
> It does not sound like a very useful algorithm, nor is it one
> that is easy to describe.

  Usefulness is a matter of time complexity, not a condition for
membership in the set of algorithms.
 
> The difference is like the difference in my example of light
> flowing through a grid, as against a fourier transform etc,
> but the difference is enormously greater.
> 
> You say it makes no difference by definition.  I say such
> definitions are misleading when we discuss how problems are
> to be solved.

  Those definitions were invented to solve problems in the first
place.

  I can't think of a single thing which is non-algorithmic
except true randomness or non-determinism. Since no finite axiom
system can prove whether a string is truly random, no algorithm is
possible for generating nor proving them.  (anything with
infinite logical depth would also probably suffice) Err, I may
be mistaken since I recall that Chaitin said that you need
N bits of formal axioms to prove that an N-bit string is
"elegant" (the smallest representation), but I also recall
somewhere that a truely random string needs an infinite
set of axioms. Perhaps Tim can shed some light.

  Perhaps another example is a physical process able to solve the
halting problem. Imagine a time traveling UTM. Call it as a
subroutine. All it does is run your algorithm program and wait. If the
program ever halts, it sends the signal back in time, otherwise it
runs forever.  Thus, you feed the TT-UTM the algorithm you want to
check. If the program halts, the signal travels back in time from the
far future to arrive during the next "tick" of your current program.
If you receive no such signal, then either the universe died before
the algorithm halted, the machine broke down, or the algorithm doesn't
halt.

  The traditional "proof by contradiction" of the insoluability of the
halting problem doesn't work here. The algorithm used to test the
contradiction simply doesn't halt. It calls the TT-UTM recursively forever,
and creates an infinite number of them. In fact, this questions
the validity of the halting proof itself since the
contradiction derived isn't a valid input to the halt checking
machine in the first place, or, the halting proof disproves
logically the existence of time travel! Inputing an algorithm
to the halt checker which calls the halt checker should be
considered an exception like "division by zero" In which case,
the halt checking TT-UTM returns "exception: input algorithm  
recurses forever"  Thus, two new classes of algorithms are
developed. Those checkable by a TT-UTM and those which are not.
Those which are not should be left up to an even more
powerful machine. ;-)

(this violates the conditions of Church's thesis since the machine
can perform an infinity of calculation at each step. Oh well.)

-Ray
"Everything is an algorithm, even you!"