Re: Infinite computing: A paper

From: Hal Finney <>
Date: Sun, 9 Feb 2003 18:11:22 -0800

Stephen Paul King refers to:

> Quantum Physics, abstract
> quant-ph/0205093
> From: Tien D. Kieu <>
> Date (v1): Thu, 16 May 2002 12:10:57 GMT (28kb)
> Date (revised v2): Mon, 18 Nov 2002 04:26:38 GMT (38kb)
> Quantum Principles and Mathematical Computability
> Authors: Tien D Kieu
> Comments: 9 pages in A4 size and 10pt fonts, 3 figures. Modified with a new
> reference added for submission to QS2002
> Taking the view that computation is after all physical, we argue that
> physics, particularly quantum physics, could help extend the notion of
> computability. Here, we list the important and unique features of quantum
> mechanics and then outline a quantum mechanical "algorithm" for one of the
> insoluble problems of mathematics, the Hilbert's tenth and equivalently the
> Turing halting problem. The key element of this algorithm is the {\em
> computability} and {\em measurability} of both the values of physical
> observables and of the quantum-mechanical probability distributions for
> these values.

This appears to be a variant on the Calude algorithm which got quite a
bit of publicity last summer. Like Calude, Kieu uses infinite dimensional
superpositions. I wrote on the everything-list on July 2,

: 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
: and the original
: paper is available at
: 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.

I still don't see how one could hope to realize these ideas which depend
on infinite dimensional Hilbert spaces. Without claiming to have
investigated these machines too closely, it seems that establishing
the necessary superpositions would take an infinite amount of work,
and creating the infinite dimensional superposition would require an
infinitely large machine.

Hal F.
Received on Sun Feb 09 2003 - 21:15:23 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:08 PST