Quote:
|
Originally Posted by garo
CT says that every computational problem can be translated into such a machine and all known real-world computations have been shown to have a TM equivalent.
|
Apart from computations that rely on true randomness. There are things a QTM (quantum Turing machine) can do that a TM can not and some algorithms that take polytime on a QTM that take exptime on a TM. Simulating a QTM is one of the latter, whereas simulating any TM on any other TM can be done in polytime.
Paul