【IT】英大学、量子コンピュータを超える「非決定性万能チューリングマシン」の実現可能性を指摘[03/02]

スポンサーリンク



1 :しじみ ★:2018/03/09(金) 11:30:43.23 ID:CAP_USER.net
■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問題と呼ばれる。
指数関数時間などになると、計算のサイズに対し計算量は莫大な増加をする。
f1 s - 【IT】英大学、量子コンピュータを超える「非決定性万能チューリングマシン」の実現可能性を指摘[03/02]

PC Watch
https://pc.watch.impress.co.jp/docs/news/1047398.html

78 :名無しのひみつ:2018/03/10(土) 09:36:02.11 ID:k2++utTY.net

>>73
で、何の半径を光速で割ればいいんですか?

67 :名無しのひみつ:2018/03/10(土) 01:19:03.14 ID:eBdocrQN.net

すべてはイオンなのです

106 :名無しのひみつ:2018/03/12(月) 02:09:15.35 ID:9HMcdB5V.net

非決定性万能チューリングマシン「せやな(肯定とも否定とも言えない」

83 :名無しのひみつ:2018/03/10(土) 13:24:36.51 ID:N0nkw2og.net

>>79 DNAで出来る事なら自然発生してても不思議ではないな

98 :名無しのひみつ:2018/03/11(日) 14:48:48.48 ID:fwANACq7.net

1ユニットでも動作サンプル出来てから発表しろよな

49 :名無しのひみつ:2018/03/09(金) 17:54:57.16 ID:M5XrKQkd.net

>>2
バカの一つ覚え

14 :名無しのひみつ:2018/03/09(金) 12:00:37.09 ID:bl/vOoR+.net

AIは理解できるのかな

57 :名無しのひみつ:2018/03/09(金) 21:41:23.30 ID:ZGRftQmQ.net

これってクラスNP完全の問題は解けてもNP困難の問題は解けないでしょ

92 :名無しのひみつ:2018/03/10(土) 22:55:31.06 ID:4G89JbQX.net

量子コンピュター

量子と言えば何でもありみたいな・・

5 :名無しのひみつ:2018/03/09(金) 11:44:50.80 ID:CRMMGeDL.net

腐らないように冷蔵庫内で作動させるのか?

15 :名無しのひみつ:2018/03/09(金) 12:14:32.02 ID:0c7tgiBU.net

反応速度遅いから無理、

60 :名無しのひみつ:2018/03/09(金) 22:36:36.90 ID:gxphO6Z7.net

現代版小型エニグマ?

19 :名無しのひみつ:2018/03/09(金) 12:26:58.04 ID:mhU7Nzub.net

これ以上将棋AIを強くして、どうしようって言うのよ!

103 :名無しのひみつ:2018/03/12(月) 00:17:37.58 ID:ajV3F8lO.net

>>7
観測する事

28 :名無しのひみつ:2018/03/09(金) 14:24:07.88 ID:Z9veJEo3.net

並列コンピューターType増殖ってことね
粘菌でそんな事してたイグノーベルが有ったような

59 :名無しのひみつ:2018/03/09(金) 22:00:59.44 ID:XTOjj76/.net

人間の脳はアナログコンピュータ、量子コンピュータが1億年掛かる計算を0.1秒で
計算する。神は偉大なり。

69 :名無しのひみつ:2018/03/10(土) 01:26:12.38 ID:+TlVJVUS.net

脳が究極だわな。省エネだし。

12 :名無しのひみつ:2018/03/09(金) 11:52:46.79 ID:KlwrSsMZ.net

多数の猫に一斉にちゅ〜るを投与できるマシーンだな?

8 :名無しのひみつ:2018/03/09(金) 11:51:08.44 ID:2aXtOR1F.net

量子コンピュータばかりに注目が集まっていて
DNAコンピュータはもうダメかなと思っていたのに。

25 :名無しのひみつ:2018/03/09(金) 14:03:51.79 ID:ALjcDLMw.net

音叉があればチューニングマシンなんていらねぇよ

22 :名無しのひみつ:2018/03/09(金) 13:25:21.60 ID:F1Zz3/8i.net

>>10
大したことはないんだよ
答えと言う名前の生命(生物学的定義ではなく情報学的定義の、しかし実在の生命と同じ機構による)を淘汰に掛けるだけ
ちょっとザンコクだよね
この機構が原因で戦争が起きて良いレベル

131 :ニュースソース検討中@自治議論スレ:2018/05/27(日) 09:17:51.20 ID:AxJY62rI.net

>>127
現実的に計算する話になれば、量子コンピュータよりも激しく現実的、
理論モデルで妄想を繰り返している量子コンピュータの基礎技術は応用できても
量子コンピュータだけのモデルは物理法則で破綻しているのばかり。
もしできたらという仮定で、将来は技術で可能だというレッテルだけ、未だ希望だけの領域、
試験管の中で核融合が起きたという話と同じで現実に核融合が起きたとしても
それはなんにも役に立たないってこと。
スイスでマイクロブラックホールを作る実験したが、現実に地球が飲み込まれるぞという
妄想と同じ、実効的に無理なのは人類がアンドロメダ星雲に旅行できる希望となんの
違いもないレベル。まあ希望的に将来技術的にアンドロメダ星雲まで旅行できるかもしれないが。

96 :名無しのひみつ:2018/03/11(日) 06:19:29.70 ID:Mro1wVI7.net

バイオコンピュータ?

122 :名無しのひみつ:2018/03/16(金) 20:44:44.77 ID:+ZV1EhWY.net

 
男色の傾向があるのか?

112 :名無しのひみつ:2018/03/12(月) 23:41:44.79 ID:8tRjtsVF.net

尚、暗号を破るには地球以上の質量のDNAが必要

21 :名無しのひみつ:2018/03/09(金) 13:24:22.64 ID:oihe/Dgt.net

インチキは量子コンピュータだけにしとけよw

100 :名無しのひみつ:2018/03/11(日) 16:49:31.42 ID:2/taGanB.net

こういうコンピューターが実際に登場したら
現在ある暗号化なんて一瞬で解かれちゃうわけだよね?
代わりになる暗号化とかって考案されてるんかな

124 :名無しのひみつ:2018/03/16(金) 22:59:43.74 ID:XR9dRkfe.net

>>7
情勢報告

34 :名無しのひみつ:2018/03/09(金) 15:10:18.49 ID:M+9ozDiR.net

>>31
>超並列計算
>力ずくの方法
>で、指数時間の問題を解く

それやっても指数時間問題の計算には指数時間かかることに変わりはない

42 :名無しのひみつ:2018/03/09(金) 16:05:53.31 ID:8iJxpFfr.net

>>41
空間の指数爆発に指数時間はかからない
たとえば空間が1秒間に2倍に拡大していくとする
わずか100秒後に2^100倍の広さが必要になる
これが空間の指数爆発

>>1の並列計算は指数時間の計算を多項式時間内に終わらせるかわりに
指数爆発する空間が必要になるってこと

シェアする

  • このエントリーをはてなブックマークに追加

フォローする