計算のサイズ(n)に対し、nの多項式時間を必要とする判定問題はP問題と呼ばれる。指数関数時間などになると、計算のサイズに対し計算量は莫大な増加をする。

　英マンチェスター大学は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法を用いることや、従来の計算機科学の技術を応用し、一応の解決の見通しはあるということだ。