View Single Post
Old 2005-07-08, 19:03   #6
xilman's Avatar
May 2003
Down not across

296616 Posts

Originally Posted by ColdFury
A QTM can be inherently faster than a TM, but they are still computationally equivalent. A TM can do everything a QTM can do, although with possible exponential slowdown.
I disagree.

A non-deterministic TM may be able to do anything a QTM can do, possibly with exponential slowdown (though I've not seen a proof of this claim) but a clasical TM can not.

Consider this program: "if (random_value < 0.5) then halt else {print FOO; halt}" where random_value is chosen uniformly and at random in the range 0 .. 1.

It's clear how a QTM can be programmed so, but how do you do it with a classical TM?

xilman is offline   Reply With Quote