【IT】英大学、量子コンピュータを超える「非決定性万能チューリングマシン」の実現可能性を指摘［03/02］
■ このスレッドは過去ログ倉庫に格納されています
■DNAを用いたコンピューティング理論
英マンチェスター大学は1日(現地時間)、DNAの複製メカニズムを利用し、
同時に異なる全ての過程を並行してシミュレーションできるDNAコンピュータの実現可能性を発表した。
これについて、同学のRoss D. King教授による論文が英Journal of the Royal Society Interfaceに掲載された。
発表論文は、DNA分子を用いて未だかつて実現したことのない
「非決定性万能チューリングマシン(NUTM)」を作製できる可能性を指摘する。
実現すれば万能チューリングマシン(UTM)に分類される既に存在するコンピュータや、
現在も研究されている量子コンピュータよりも理論的には遥かに高速になると考えられる。
同教授は、NUTMについて
「迷路をコンピュータに解かせた際、UTMは分岐路でどちらの分岐を先に計算するか決定する必要があるが、
NUTMは全ての通りを同時にシミュレートするため、その必要がない」とし、
「量子UTMも同時に異なる通りをシミュレートできるが、迷路が左右対称である必要があり、
これは利用者にとって大きな制約だ」としてNUTMの優位性を強調している。
DNA(デオキシリボ核酸)は、生体では遺伝情報の運搬や格納に用いられる。
異なる4種の塩基が作る塩基対を持つ2重らせん構造が有名だが、その塩基の配列こそが遺伝情報だ。
DNAは複製や転写が可能であると同時に、生物の遺伝情報が数十億年に渡り事実上変化していないことが示す通り、
相補的な塩基対の構造により配列の信頼性も高い。加えて、DNAを用いたコンピューティングは低消費電力なことや、
理論的には1bitあたり1立方nmで記録できる情報の記録密度の高さから注目されている。
同教授は、これらの性質がNUTMの実現にも好適であると考えた。
DNAの塩基配列の基本単位は3塩基からなり(トリプレットという)、トリプレットに文字を割り当て、
その文字や文字列を一定の規則に応じて操作する項書き換えシステムを試作した。
この項書き換えは、DNAを増幅するPCR法と選択的に遺伝配列の変化を起こす技術(Site-Directed Mutagenesis)を応用して実現された。
この実験によって得られた結果は、NUTMに必要とされた性質を全て満たしているという。
この研究はNUTMの存在を実証するものではなく、完全なNUTMを作製するにはさらなる実験が必要である。
また、技術的にもノイズの問題などの懸念が存在するとしつつも、DNAの編集にCRISPR法を用いることや、
従来の計算機科学の技術を応用し、一応の解決の見通しはあるということだ。
画像：計算のサイズ(n)に対し、nの多項式時間を必要とする判定問題はP問題と呼ばれる。
指数関数時間などになると、計算のサイズに対し計算量は莫大な増加をする。
https://pc.watch.impress.co.jp/img/pcw/docs/1047/398/f1_s.jpg
PC Watch
https://pc.watch.impress.co.jp/docs/news/1047398.html 完璧に伝送するより、ある程度の確かさで伝送してある程度のゆらぎの誤差は許容する妥協をすればもっと速められるのでは。
アナログに近くなる。アナログ的な不確かさを許容して設計されているこの世界が神のコンピューターの計算結果なのかもしれない。 量子コンピュータばかりに注目が集まっていて
DNAコンピュータはもうダメかなと思っていたのに。 ってゆーか、我々こそ、古代宇宙人がつくったコンピュータのなれの果てなのだ！ 量子コンピューターも何言ってるか分からんけど、もっと分からん 多数の猫に一斉にちゅ〜るを投与できるマシーンだな？ DNA分子がいくらでも増やせるとか仮定できるなら、そりゃまあと
>>6
チューリングマシンは固有名詞ではないからな。
チューリングから命名されているが、コンピュータのモデルで、
チューリングマシンは学術用語だ。
ほとんど全ての現在のコンピュータはこのモデルに集約可能。
これ以上将棋AIを強くして、どうしようって言うのよ！ >>10
大したことはないんだよ
答えと言う名前の生命(生物学的定義ではなく情報学的定義の、しかし実在の生命と同じ機構による)を淘汰に掛けるだけ
ちょっとザンコクだよね
この機構が原因で戦争が起きて良いレベル 無理だよ…
と言おうと思ったらDNAコンピューターの話か。
凄く難しいし解ける問題は限られるが(その時点でチューリングマシンではなくない？)まぁできるかもね。
確かオリンパスがやってた気がするけど、
本当にそこそこ動くなら定理証明にでも応用してほしいもんだ。 >この項書き換えは、DNAを増幅するPCR法と選択的に遺伝配列の変化を起こす技術(Site-Directed Mutagenesis)を応用して実現された。
>この実験によって得られた結果は、NUTMに必要とされた性質を全て満たしているという。
いやかすってもない、ただの決定論的TMでしかねーぞ 並列コンピューターType増殖ってことね
粘菌でそんな事してたイグノーベルが有ったような >>9 生命、宇宙、そして万物についての究極の疑問の答えを導き出す
究極の疑問が得られそうだな。 超並列計算
力ずくの方法
で、指数時間の問題を解く
ってことかな？
非決定性へのコンパイルは、どうするんだろう >>29
「それにつけても金の欲しさよ」
究極の疑問にして究極の解答 >>31
>超並列計算
>力ずくの方法
>で、指数時間の問題を解く
それやっても指数時間問題の計算には指数時間かかることに変わりはない >>1
これ1年前の記事だよ…
佐藤 亮 2017年3月2日 17:33 致死遺伝子だらけで評価関数の方が高く付くんじゃないのかな このDNAコンピュータはDNAの分裂複製を使って並列計算するという仕組みだから
計算時間の指数関数的爆発を抑えるかわりに計算に必要な分子量あるいは
DNAを収めるために必要な空間が指数爆発してしまうから意味ないと思われる >>40
>DNAを収めるために必要な空間が指数爆発してしまうから意味ないと思われる
空間が指数爆発するには指数時間かかるからそもそも意味ねーんだよ >>41
空間の指数爆発に指数時間はかからない
たとえば空間が1秒間に2倍に拡大していくとする
わずか100秒後に2^100倍の広さが必要になる
これが空間の指数爆発
>>1の並列計算は指数時間の計算を多項式時間内に終わらせるかわりに
指数爆発する空間が必要になるってこと よりすぐれた動作原理を求めて研究をつづけていたら
あれ？これって？動物の脳じゃね？
ってなったりしてな >>43
アンカーまちがえた
何の直径ですか？空間の直径ってこと？
そういう話じゃないんだが
DNA増殖 | → || →|||| → |||||||| → |||||||||||||||| → ||||||||||||||||||||||||||||||||
→ ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
→ ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
…
この倍々で増えてくDNA1本ずつが分岐計算の枝分かれに対応している
DNAが分裂していくだけだから別に光速が律速条件になったりはしない
ただしすぐに宇宙全部の原子の個数を使い切っても足りないくらいにDNAが増える 極端な事を言えば、ディスプレイには何かしら文字や画像が表示されているわけだが
もしも画素の組み合わせを全通り表示できるなら、そのランダムな画像の中に自分の顔の画像や小説の一部を表示したもの
もちろん今ここで表示されている画面と全く同じものも含まれる np は not polynomial じゃないからな、non deterministic polynomial だから ■メタトロンコンピュータ
メタトロンを集積回路に使用した量子コンピュータの一種
それまでのデジタル式フォン・ノイマン型コンピュータとは
一線を画す桁違いの演算速度と小型化を両立
演算装置と記憶装置の区別がなくサーキットそのものが
絶えず変化することで演算と記憶を
（量子論的に言えば別の宇宙で）行う おまえら何も分かっとらんようだが、要すればかつ丼を食うかカレーを食うか、
どちらがいいか瞬時に判断できるようになるってことだ。これは役に立つぞ 規模が大きくなると量子よりもDNAの方が速くなるって話かな？ これってクラスNP完全の問題は解けてもNP困難の問題は解けないでしょ 生物の遺伝情報が数十億年に渡り事実上変化していない
・
・
・
変化していなかったら、地球に存在する生物は１種類だけなのでは？
変化しまくったからこそ、地球には大量の生物がいるのだと思うが。 人間の脳はアナログコンピュータ、量子コンピュータが１億年掛かる計算を０．１秒で
計算する。神は偉大なり。 >>11
素晴らしい。
あとは情報が必要な人にどう見せるかだね。 量子コンピュータはいまだに、ダークマターとダークエネルギーのような概念に
進歩を阻害されているからなぁ、
そもそも量子力学まなんでいない奴が量子コンピュータ作っているんだし。
D-Waveとか量子コンピュータを開発する為の量子コンピュータだと
自分のＷｅｂに宣言していたぐらいだし、 けっきょく「有機コンピューター」というか
「ニューロコンピューター」というか
大脳の神経回路みたいなもんだろ 量子コンピュータもそうだけど、並列性が論理的に無限になるのを仮定するの疑わしいな 量子コンピュータ以上の性能がある理由がさっぱり分からん 並列処理なことだけは分かったｗ >>73
で、何の半径を光速で割ればいいんですか？ 俺氏、全てのウイルスは細胞DNAの破片である可能性を指摘
みたいなもんだろコレ >>79 DNAで出来る事なら自然発生してても不思議ではないな 補食者の居ない有機物のスープである古代の海が天然の計算機になってたとか 分岐が発生したら増殖して並列計算する
だが資源を無駄に食い尽くす気もする >>84
量子コンピュータって計算が成立するが確率的に成立する原理ゆえ、
計算の規模が大きくなるほど計算時間は一瞬でも正しく答えを取り出せる確率が
指数的に０％に接近してくる、計算は一瞬でも、なんども1兆回とかやって1回計算できるとか
それが1兆の一兆乗に1回しか計算が正しく取り出せないとかになると、
それは速いというより激遅いというのが正解だ。 現状の量子コンピューターの致命的欠点は、１量子の量子状態を維持できる時間が致命的に短いことだと思っている。
今の半導体メモリーは、タイプに関わらず半永久的に状態を維持できる。
想像を絶する電荷の数を使うからだ。
例えて言えば、これを、たった一個の電荷で処理しようとするのが量子コンピューターだ。
基本的には、共振器に閉じ込めて存続時間を伸ばそうとしているが、限界がある。
昔、眉村卓の司政官シリーズのSF小説に、エンタングルメントを利用した通信装置を使う場面がよく出てくるが、ほぼ半永久的に量子状態を維持しないと実現できないから、正にSF小説だ。
IBMもGoogleも、写真を見る限りでは、極低温の共振器を使っているので、秒オーダーで維持するのは難しいのではないか。 なんという事だ…この地球は生物を使った計算機だったんだよ！！
つまり人類は滅亡する！！ 量子コンピュター
量子と言えば何でもありみたいな・・ 最近、理論だけでXXX超える！ が多すぎて困る。
基礎研究は必要だけど、一般人が夢見すぎてお花畑。
全人類妄想狂言化しそう。 こういうコンピューターが実際に登場したら
現在ある暗号化なんて一瞬で解かれちゃうわけだよね？
代わりになる暗号化とかって考案されてるんかな ■ このスレッドは過去ログ倉庫に格納されています
