View Single Post
Old 2005-07-08, 19:03   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5·2,039 Posts
Default

Quote:
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?


Paul
xilman is offline   Reply With Quote