Thread: Church-Turing Thesis View Single Post
2005-07-09, 00:54   #7
ColdFury

Aug 2002

26×5 Posts

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.