On Monday, December 30, 2002, at 09:38 AM, Hal Finney wrote:
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 (*).
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.
(* 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
