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

100111110100112 Posts
Default

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
xilman is offline   Reply With Quote