マンチェスター大学の研究チームは、DNAを利用することによって超高速で並列処理計算を行う新型コンピュータが実際に作製可能であるとする研究を発表した。量子コンピュータを使っても現実的な時間内に解くことができないと予想されている難問も短時間で解くことができると主張している。

こうしたコンピュータは、計算機科学の分野では「非決定性万能チューリングマシン(NUTM: non-deterministic universal Turing machine)」と呼ばれているものであり、理論的には以前から知られているが、実際の計算機が作製されたことはない。今回の研究も、NUTMの理論的な実現可能性を検討したものであり、すぐに実機の作製に取りかかれるわけではないが、DNAの自己複製能力を利用したDNAコンピュータとしてのNUTMの実現性や、その基本的な動作原理などを示した点で注目される。論文は、物理学とライフサイエンスの境界領域を扱う学術誌「Journal of the Royal Society Interface」に掲載された。

現代のコンピュータは、アラン・チューリング(1912-1954)が提唱した計算機の原理を実用化した「万能チューリングマシン」の一種であるといえる。私たちが普段使っている通常のコンピュータは、ある入力をしたときに計算機がどのような動作をするかが一意に決まっているという意味で、「決定性万能チューリングマシン」とも呼ばれる。これに対して、ある入力をしたときに複数の動作を同時にとれるような計算機は「非決定性万能チューリングマシン(NUTM)」と呼ばれる。大雑把にいえば、並列処理での計算が可能なコンピュータがNUTMである。

たとえば、通常のコンピュータとNUTMで迷路の探索をさせた場合、通常のコンピュータでは、迷路の分岐点にさしかかったとき、右か左どちらか一方の分かれ道を先に探索し、その後に残りの分かれ道を探索するという手順をとる。一方、NUTMでの迷路探索では、分岐点にさしかかったとき、左右の道を同時に探索する並列処理を行う。したがって、迷路内の分岐点の数が増加すればするほど、処理速度は通常のコンピュータよりNUTMのほうが圧倒的に速くなる。

今回の研究では、このような並列処理が可能なNUTMを、自己複製能力のあるDNA分子を使って実現する方法が提唱されている。DNAの塩基配列に特定の文字列を対応させることでコンピュータとして動作させるというもので、迷路探索の例でいえば、分岐点にさしかかるたびにDNAが増殖して並列処理動作を行うというイメージである。データの状態のコピー手段としては、DNAの増幅に用いられるポリメラーゼ連鎖反応(PCR: polymerase chain reaction)を利用する。データの状態を変化させる場合には、部位特異的変異導入法(SDM: Site-Directed Mutagenesis)と呼ばれる手法を利用するという。

この方法で実際に動作するNUTMを作製するには、解決しなければならない問題が数多くあり、実現はまだ先になるだろうと研究チームは予想している。その中でも最も大きな課題はノイズの処理になると考えられる。ノイズの問題は量子コンピュータ開発の上でも深刻な障害になっている。ただし、量子コンピュータと比べると、NUTMにおけるノイズ処理はよく知られた古典的アプローチが利用できるため、現実的な解決が期待できるとも研究チームは主張している。

数学上の未解決問題「P≠NP予想」とNUTM

NUTMが実現可能かどうかという問題は、数学上の有名な未解決問題「P≠NP予想」とも関わっている。

通常のコンピュータで効率的に解を求めるアルゴリズムが発見されていない問題は多数存在する。そうした問題を解こうとすると、しらみつぶしに解を探索していくしかないが、それをすると指数関数的に計算時間が増大してしまい現実的には解くことができない場合が多々ある。たとえば、しらみつぶしで解くために2100回の計算が必要な問題は、1GFLOPSのコンピュータ(1秒間に10億回の計算可能)で40兆年くらいかかる。こうした問題は「クラスNP」の問題と呼ばれる（もう少し詳しく書くと、クラスNPの問題は、ある解が提示されたときその解が正しいかどうかを判定するだけなら現実的な時間内に計算できる）。

このようにクラスNPの問題を通常のコンピュータで解くことは難しい。しかし、仮にNUTMが実現すれば、非決定性アルゴリズムを使ってすべてのしらみつぶし探索を同時に行えるので、計算時間は短時間に収まる。2100回の計算の例でいえば、しらみつぶしの選択肢の枝分かれが100層分あることになるので、1層の枝分かれに1秒かかったとしても100秒もあれば計算は終わる。

また、数学の世界では、NP問題の中に｢NP完全｣と呼ばれる特別な問題があることが知られている。すべてのNP問題は、現実的な時間内での計算によってNP完全問題の形に置き換えられることがわかっているので、もしもNP完全問題を現実的な時間内に解くことができれば、すべてのNP問題が解けることになる。

通常のコンピュータで現時的な時間内に解くことができる問題は「クラスP」の問題と呼ばれる。実際にNP完全問題を現実的な時間内に解くアルゴリズムが存在するならば「P＝NP」であることになる。逆に、そのようなアルゴリズムが原理的に存在しないならば「P≠NP」になるが、どちらが正しいのかについてはいまだ証明されていない。これが「P＝NP予想」または「P≠NP予想」と呼ばれる数学上の未解決問題である（「P≠NP予想」は100万ドルの賞金がかかったミレニアム問題の1つでもある）。

NP完全問題については、量子コンピュータを使ってもやはり現実的な時間内に解くことはできないのではないか、という予想がある。一方、NUTMが実現されれば、NP完全問題も高速のしらみつぶしで解けてしまうと考えられる。つまり、NUTMが実現すると「P＝NP」であることが証明される可能性がある。

しかし、「P＝NP予想」が正しく、したがってすべてのNP問題が解かれてしまうという事態は、ありそうにないと考えられるため、専門家のあいだでは「P≠NP予想」を支持する人のほうが多い。どちらが正しいのかは未解明の問題であるが、仮に「P≠NP」であるなら、NUTMは実際には作れないのではないか、とも考えられる。

今回の研究チームの論文では、「P＝NP予想」または「P≠NP予想」の真偽について明確な意見は表明されていない。しかし、その一方で、DNA分子を利用した自己複製型のNUTMは物理的に実装可能であると主張している。

DNA型NUTMの計算には時間ではなく空間的制約がかかる

ここで注意を要するのは、研究チームが提唱しているNUTMでは、計算可能性を制限する要素が「時間」ではなく「空間」に置き換わるという点である。これは、並列処理を行うたびにDNAが複製され、NUTMを構成する物理的空間が増加していくことを意味する。

通常のコンピュータも量子コンピュータも、ある問題を現実的に解くことが可能かどうかは、その計算に必要な時間によって制約される。一方、DNA分子型NUTMでは問題のサイズが大きくなっても、計算に必要な時間が増えないかわりに、計算に必要な空間が増大するため、時間ではなく空間が物理的な制約になるという。このため、NUTMを使ってしらみつぶしに解くことができるNP問題のサイズには依然として物理的な制限が残る。

計算に使える時間に限りがあるように、計算に使える空間にも限りがある。地球上の原子の数がおよそ1049個、宇宙全体の原子の数がおよそ1080個であることを考えれば、計算に必要なDNA分子数がこのようなオーダーで指数関数的に増大していく場合、やはり現実的には解けない問題があることは明らかであろう。

研究チームは、DNA分子を用いてコンピュータを微小化することによって空間を有効利用すれば、上記のような物理的制限の下であっても、既存の最高性能のスーパーコンピュータを凌駕するNUTMは実現できると主張している。具体的な数値としては、デスクトップサイズのDNAコンピュータで毎秒1020回の計算が可能(既存の最高のスパコンの約1000倍の計算性能)であり、しかも1ジュールあたりに実行可能な計算回数が2×1019回(既存のスパコンのおよそ10億倍)という低消費エネルギーが実現できると見積もっている。ただし、現実に問題を解く上で、上述した空間上の物理的制約がどのように影響してくるのかについては、さらに慎重な検討が必要であると思われる。