View Single Post
Old 2005-07-08, 12:28   #3
xilman's Avatar
May 2003
Down not across

2·7·757 Posts

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.

xilman is online now   Reply With Quote