There was an article recently in New Scientist about a new way to geet
computing beyond the "Turing barrier". I think it is somewhat similar
in spirit to the analog machines, in that it uses infinities, but it is
based on the quantum computing model. The NS article is reprinted at
http://www.cs.auckland.ac.nz/~cristian/smashandgrab.htm and the original
paper is available at
http://www.arxiv.org/abs/quant-ph/0112087.
>From the NS article:
His suggestion is to think bigger: why not create a superposition
of every conceivable state at once? Something like a hydrogen atom
has infinitely many possible energy levels. While the levels start
out well-spaced, they get closer as the energies grow higher, until
they become almost indistinguishable. In a paper to be published
in the inaugural edition of MIT's new journal Quantum Information
Processing, Calude and Pavlov have shown that a superposition of an
infinite number of energy states would allow a quantum computer to
do things no classical computer can ever manage-almost like running
"forever" in a finite time.
This leap means that a quantum computer can overcome Turing's most
famous barrier to computing power: the "halting problem".
...
Calude is extremely proud of this result: he believes it could be
implemented on a real-life quantum computer, laying much that is
"unknowable" open to attack. "Using infinite superpositions is rather
theoretical, but not necessarily non-practical or non-testable,"
he says.
My opinion is that infinite superpositions will never be practical hence
his machine is of only theoretical interest.
Hal
Received on Fri Jul 05 2002 - 10:51:44 PDT