X-Message-Number: 9340
From: eli+@gs160.sp.cs.cmu.edu
Subject: "non-Turing computation" one last time
Date: Mon, 23 Mar 98 23:50:58 EST

>From: Thomas Donaldson <>
>Subject: Re: CryoNet #9284 - #9292

This whole discussion is peculiar.  Saying that something is faster than a
Turing machine is trivial, and may be an indication that one is confused
about what sort of results are interesting.  Nobody _cares_ about the
speed of a TM.

They're dog-slow, because Turing didn't care about anything but
simplicity.  As performance models for real machines, they're worthless;
you use other models for that.  TMs are only interesting for questions of
computability -- what sets can be recognized, regardless of how long it
takes.

The paper you cite talks about performance, not computability, correct?
(My memory of it is fuzzy, but I recall finding it valid though
unsurprising rather than screamingly bogus.)  So we can ignore the
Church-Turing thesis, which talks about the latter.

As it's uninteresting to be faster than a Turing machine, the below
question, taken literally, has turned out to be a relatively minor issue.
But I suspect their result generalizes to "faster than a bounded-precision
RAM", since their model is similar to (no stronger than) an unbounded-
precision RAM, which is known to be faster -- not surprising when you
consider that you get get more work done with each operation.  (The
Random-Access Machine is a model of serial computation often used for
analyzing algorithms, similar to a TM except that any memory location can
be accessed in one cycle.)

>Just like a true Turing machine, the Siegelmann device is an intellectual
>construction only. Why is an infinite tape not laughable while use of 
>infinite decimal numbers is?

Not infinite, in either case.  Finite but unbounded.  (Like a possible
response to "pick any integer".)

To solve a finite problem requires a machine of some finite difficulty to
construct.  The question is how the difficulty scales with problem size.
I'm going to be vague, because I don't want to try introducing asymptotic
notation, and because I was more precise the last time I said this on this
list, but the idea is that memory is easy to build, while analog precision
becomes much harder the more you want of it.  Each bit requires halving
the noise floor.  I suspect quantum effects will trip you up even as you
approach absolute zero, but I'm a layman on that.

For the next message:
>I would say, myself, that incommensurable states provide the real
>basis for models with infinite accuracy.

"Incommensurable" means nothing in the presence of any noise whatsoever
(the rationals are dense on the real line).  Again, how do you get zero
noise?

-- 
     Eli Brandt  |  eli+@cs.cmu.edu  |  http://www.cs.cmu.edu/~eli/

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=9340