On Monday, December 30, 2002, at 09:38 AM, Hal Finney wrote:
>
> We discussed this article briefly in July. Calude relies on infinite
> dimensional Hilbert space with the inputs prepared in an infinite
> superposition. Without claiming to understand all the details, this
> looks to me like it would require an infinite amount of work to
> prepare.
>
> It is well known that under idealized classical Newtonian physics,
> computations are possible that break the Turing barrier if you have
> infinite precision in your inputs. Of course, we don't live in a
> Newtonian universe. This new result has something of the same flavor,
> applied to a quantum mechanical universe. It still relies on
> infinities.
>
> When a finite quantum computer can break the Turing barrier, that will
> prove something. But when your first step is to prepare an infinite
> superposition, that has no applicability to the physical universe.
>
Along these lines, the noted Berkeley mathematician Steve Smale has
worked with others (cryptographers Blum, Shub) on what it would mean to
have a computer work with _real_ instead of integers. This seems close
in spirit to much of both what Hal refers to above and to the more
general "quantum computation" systems (*).
(* where machines must be set up with very high precision to compute,
via Shor's or Grover's algorithms, for example, even small
results...and where large results will require precisions of many, many
decimal places. There is hope that Zurek-type quantum error correction
coding (QECC) can fix this scenario where materials have to be
positioned to, say, 50 decimal places of accuracy to compute some level
of computation (epsilon-delta argument, of course), but some recent
reports cast doubt on the rising energy requirements of QECC. But I am
not (yet) as knowledgeable about quantum computing as I hope to be in
several months, so go to the source materials if interested.)
Here is one of many readily-findable references to the work:
http://citeseer.nj.nec.com/context/5445/0
"An important example are computations over the real numbers based on
the model of Blum Shub Smale. Computation over . In 1989 Blum, Shub,
and Smale [14] introduced a model for computations over the real
numbers (and other rings as well) which is now usually called a BSS
machine. The important difference with, say, the Turing model is that
real numbers are treated as basic entities and that arithmetic
operations on the reals are performed in a .... "
Here's a review article by John Casti:
http://www.heise.de/tp/english/kolumnen/cas/2414/1.html
(Note that he calls the machine a BBS machine, getting it wrong. He was
probably confusing it with the BBS (Blum-Blum-Shub) random number
generator, which is not at all the same thing as a BSS mahine. But
Casti writes engagingly, so this is a good introduction.)
In a hand-waving sort of way, computing with real numbers cuts through
a lot of the work to build arbitrary-precision (or length) strings of
symbols.
But are the reals real?
A fascinating topic, perhaps too much of a digression here. Read on if
interested.
A real number is a point on a line. Its expansion in any base is of
course infinite. Does such a thing "really" exist?
David Lewis would argue that yes, lines and points and real numbers
really do exist, but that they are inaccessible to us (in the way that
the worlds where Germany won the second world war really exist, but
cannot be visited or communicated with). Lewis uses a closeness metric,
where he shows how we may "approach" the world of the perfect Euclidean
line or point or space. "Take any drawn line, make the pencil line
thinner and thinner, straighten out the kinks, etc."
In the possible worlds ontology, real numbers and Euclidean lines exist
as possible worlds, but nothing in our experience or in what we
understand of the working of the world we are in lets us reach these
possible worlds.
To the constructivist, or intuitionist (a la Brouwer, Heyting), this
says that a real number is only the name we give to a process of
construction (e.g., Dedekind cuts, the familiar epsilon-delta
construction of the real numbers). The real number is not an actual
thing, but a process, an algorithm. (As someone quoted within the past
day, Kronecker's "God made the integers, all else is the work of man.")
To cut to the chase, so to speak, the reals don't actually exist in our
world except as ideals (other possible worlds we can approach but never
reach).
An attempt to build a machine computing with the reals would be
interesting, if only to show how buried in the attempt would be
algorithms and constructions which are simulating real numbers to some
precision. (Perhaps this is where quantum computers break down, if they
do.)
But the BSS work sheds a lot of interesting light on computability,
further illuminating the fascinating links between the theory of
recursive functions (aka lambda calculus), cartesian closed categories,
and the effective topos of Hyland and others.
By the way, once we think in terms of the real numbers and points on
lines and planes not actually having any real existence, the
idealization of a manifold (e.g., a Riemannian spacetime manifold) as
being infinitely divisible becomes more and more farfetched.
(Now it may well be that spacetime is in fact an ideal manifold,
divisible and measurable at scales of 10^-35 m, or even at scales of
10^-100 m. But it will not be surprising at all to many of us if
spacetime is quantized, or foamy, or latticelike, at approximately
Planck-length scales. What those lattice points are "made of" is itself
a question, but the smoothness and continuity of spacetime is not
necessarily "real all the way down." Cf. the usual books and articles
by MTW ("Gravitation"), Smolin ("Three Roads..."), Rovelli,
Markopoulou, Crane, Baez, etc. for more on spin foams, lattice
structures, etc. Greg Egan's "Schild's Ladder" novel has a description
early on, a fictional description, of course.)
--Tim May
Received on Mon Dec 30 2002 - 13:37:45 PST