Re: GUT and P=NP

Ray wrote:
> Everything is an algorithm
 
This does not appear to be a very useful concept of what
an algorithm is.
 
>   I can't think of a single thing which is non-algorithmic
> except true randomness or non-determinism. 
 
How about any process where the state and the change
between one state and another state can be described
tolerably simply in some language that is not explicitly
algorithmic, but which is enormously difficult, complex,
and expensive to describe in explicitly algorithmic
language, for example water pouring through a channel?
 
 
-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we     James A. Donald
are.  True law derives from this right, not from     jamesd@netcom.com
the arbitrary power of the omnipotent state.

> How about any process where the state and the change
> between one state and another state can be described
> tolerably simply in some language that is not explicitly
> algorithmic, but which is enormously difficult, complex,
> and expensive to describe in explicitly algorithmic
> language, for example water pouring through a channel?

So are you suggesting that the definition of "algorithm" has
an "as long as it's not too hard" clause?

Mike McNally writes:
 > However, I fail to udnerstand why you do not consider the
 > programming of the quantum computer to be a non-algorithm.  

Oops.  Make that:

However, I fail to understand why you do not consider the programming
of the quantum computer to be an algorithm.

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

One last word on this.  Try and represnet a continum of states by an 
infinite turing machene.  Go ahead, I dare you.  You can't.<=big period.

So, It *WOULD* *NOT* supprise me that something that is a continum 
phenomona can do something that an ordinal(descrete) machene can't do.

Berzerk.

berzerk@xmission.xmission.com writes:
 > One last word on this.  Try and represnet a continum of states by an 
 > infinite turing machene.  Go ahead, I dare you.  You can't.<=big period.

Could I not let each position on the tape represent a real value in
[0...1]?

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

On Tue, 26 Jul 1994, Mike McNally wrote:
>  > One last word on this.  Try and represnet a continum of states by an 
>  > infinite turing machene.  Go ahead, I dare you.  You can't.<=big period.
> Could I not let each position on the tape represent a real value in
> [0...1]?
No, the continuium can not be maped onto an ordinal infinity.  It is a 
greater infinity.

Berzerk.

James A. Donald writes:
 > An algorithm is a method of solving problems.  Not everything in
 > the universe is an algorithm or equivalent to an algorithm.

Ok.

 > Suppose we have a quantum computer that solves some NP (incomplete) 
 > problem in polynomial time with order one probability..
 > 
 > A numerical simulation of that computer...

Indeed, a numerical simulation would be quite complex.  However, I
fail to udnerstand why you do not consider the programming of the
quantum computer to be a non-algorithm.  Clearly, if somebody can make
the quantum computer solve the NP problem, there must be some
technique of expressing the process.  If it's not an algorithm, what
do you call it?  (Hint: it is an algorithm.)

 > The quantum computer is not equivalent to the mindless brute
 > force algorithm for solving the problem.

Right; it executes a different algorithm.

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

Mike McNally writes
> So are you suggesting that the definition of "algorithm" has
> an "as long as it's not too hard" clause?

No.

I said what I meant.

An algorithm is a method of solving problems.  Not everything in
the universe is an algorithm or equivalent to an algorithm.

Suppose we have a quantum computer that solves some NP (incomplete)
problem in polynomial time with order one probability..

A numerical simulation of that computer very likely involves 
evaluating every possible solution of that NP problem as
one of a great many steps, thus to describe that numerical
simulation as an algorithm for solving the problem is
meaningless or obfuscatory.  

The simulation is equivalent the mindless brute force algorithm 
for solving the problem, plus an enormous amount of garbage.  
The quantum computer is not equivalent to the mindless brute
force algorithm for solving the problem.


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com