Re: QM Turing Universality (was: MGA 2)

From: Bruno Marchal <>
Date: Mon, 12 Jan 2009 18:25:41 +0100

On 12 Jan 2009, at 17:24, Mirek Dobsicek wrote:

> Thank you for a quick answer! I'll take a look at it, my curiosity
> approves additional items on my TODO list :-)

Manage keeping finite your todo list :)

I have finished the reading of the paper I mentioned (Deutsch's
Universal Quantum Turing Machine revisited) and I see they have very
similar problems, probably better described. The paper mentions (but
does not tackle) an old problem already described by Shi 2002, which
made me think at the time that the notion of Universality is a bit
dubious in the quantum realm.

To sum up: is there a (never stopping) quantum counting algorithm? I
think I can build a Quantum UD from it, well in case the Shi problem
is not too much devastating.
But here, and now, I got a feeling there is just no quantum counting
algorithm ...



PS Note that AUDA (the arithmetical UDA) is in principle already able
to solve completely that problem. It is still possible that "the
material hypostases" of the self-observing *classical* universal
machine lacks both the kestrels and the starlings, and their
descendant combinators in which case comp predicts that physics is NOT
Turing Universal. Comp would predict that not all natural numbers are
in any possible nature or physics!
"in principle" only because the translation in arithmetic leads to
very complex arithmetical formula (bounded by PI_1 IN Arithmetical
Truth, if you know a bit of degrees of unsolvability. I will perhaps
explain a bit of this, but take it easy for not making explode the
todo list :).
Note the beauty of comp: even if there are no physical universal
machine in the physical universe (including the physical universe(s)),
*you* (and other persons) are and remains universal machine.
We do not live in physical universes, we just traverse them to be able
to chat some bits, perhaps. The first persons would be spiraling
through an infinite sequence of rotations, if said through an image.

You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at
Received on Mon Jan 12 2009 - 12:25:49 PST

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