NurseAngelの日記: 非決定性万能チューリングマシン 3
日記 by
NurseAngel
http://rsif.royalsocietypublishing.org/content/14/128/20160990
Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA
This means that a desktop DNA NUTM could potentially utilize more processors than all the electronic computers in the world combined, and thereby outperform the world's current fastest supercomputer, while consuming a tiny fraction of its energy.
http://pc.watch.impress.co.jp/docs/news/1047398.html
実現すれば万能チューリングマシン(UTM)に分類される既に存在するコンピュータや、現在も研究されている量子コンピュータよりも理論的には遥かに高速になると考えられる。
よくわからん。
素人考えだと量子コンピュータのほうがずっと早そうに思えるんだがどう違うんだろう。
まあ何でもいいから早く一般的価格で店頭販売してくれ。
うろ覚えですが… (スコア:1)
うろ覚えですが、理論的には、量子コンピューターの様な「条件分岐時に状態の重ね合わせを利用できる」コンピューターより、「分岐時に全ての条件を枝分かれさせて並列計算出来る」コンピューターの方が速い(後者は神託機能で「正しい答え」を常に選び出していると見なせる)と言う論文?が有るのだとか…。DNAコンピューターなら条件分岐ごとにDNA鎖を増やせるので、後者の「神託」コンピューターが実現できるとか…。
因みに、普通の電子コンピューターで量子コンピューターや神託コンピューターの動作をエミュレートすることも可能ではあるが、肝心の高速性は再現できないとか…。
補足 (スコア:0)
ここで言う「コンピューター」とは、(抽象的な)チューリングマシンの事だったと思います。
# でも、理論的にはDNAコンピューターの方が強力な計算機能を持っていても、個々の計算での「クロック数」はあまり上げられない気も…(汗)
数学的には (スコア:0)
量子計算より非決定性多項式時間計算のほうが…と言いたかったが、NPとBQPの包含関係は未解決問題だったのね。
# じゃあニュースが何を根拠に「量子コンピュータよりも理論的には遥かに高速」と言っているのか謎だ