View Single Post
Old 2005-07-09, 00:54   #7
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

Quote:
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.
A non-deterministic TM can be simulated by a classical TM by computing all the branches of the computation.

Quote:
It's clear how a QTM can be programmed so, but how do you do it with a classical TM?
Your point is taken, though I argue since its not an algorithm which solves any problem, you're not really adding any additional computational power. Any algorithm which uses randomness can be simulated by a classical TM by computing every possible outcome.
ColdFury is offline   Reply With Quote