泳ぐ細菌で動くコンピューター、計算しながら増えて計算力アップ

1 時間前 2

足し算の組み合わせ探しは、なぜコンピューターでも手ごわいのか?

顕微鏡とパソコンを使う研究のイメージ写真。今回の実験装置ではありません顕微鏡とパソコンを使う研究のイメージ写真。今回の実験装置ではありませんCredit: Photo by Edward Jenner on Pexels

「2、5、9、11の中からいくつか選んで足し、ちょうど16にしてください」と言われたら、どうしますか?

少し考えれば、5+11や、2+5+9が見つかるでしょう。

数字が4つなら、全部の選び方を試しても16通りです。それぞれの数字を「使う」か「使わない」か決めるだけだからです。

ところが、数字が1つ増えるごとに、確かめる組み合わせは2倍に増えていきます。

数字が100個になると、組み合わせは100万の1兆倍のさらに1兆倍を超えます。

これは数学で「部分和問題」と呼ばれる問題で、暗号の分野でも重要とされています。同じ数字ばかり並んだ問題のように簡単に答えが分かる場合もありますが、どんな数字の組が出されても速く解ける一般的な方法は、いまのところ見つかっていません。

電子のコンピューターはとても速く、いまではたくさんの計算を同時に進めることもできます。それでも同時に進められる計算の数には限りがあるので、倍々に増える組み合わせを全部確かめようとすると、数字が増えるにつれて時間が足りなくなっていきます。

そこで考えられてきたのが、問題そのものを、分かれ道のある迷路の形に作りかえる方法です。

左下の入口から、右へ向かって進む迷路を思い浮かべてください。分かれ道には、数字が1つずつ割り当てられています。

分かれ道で階段のほうへ進むと、その数字と同じ段数だけ上がります。これが「その数字を足す」にあたります。平らな通路へ進めば、高さは変わりません。これが「足さない」です。

迷路の右はしには、高さの違う出口が並んでいます。どの高さの出口に着いたかが、選んだ数字の合計になるのです。

たとえば2、5、9の3つで迷路を作ると、次の図のようになります。全部を足す道は、16の高さの出口に着きます。

2・5・9の3つの数字を例に、足し算の組み合わせ探しを通路の形に置きかえる仕組みを示した模式図。実際のチップの迷路を写したものではない。左下の入口から右へ進み、分かれ道ごとに斜め上へ進むと下に書いた数字の分だけ上がって足したことになり、まっすぐ横へ進むと足さない。右はしの出口の高さ0・2・5・7・9・11・14・16が足した合計を表し、全部を足す太い道は合計16の出口に着く2・5・9の3つの数字を例に、足し算の組み合わせ探しを通路の形に置きかえる仕組みを示した模式図。実際のチップの迷路を写したものではない。左下の入口から右へ進み、分かれ道ごとに斜め上へ進むと下に書いた数字の分だけ上がって足したことになり、まっすぐ横へ進むと足さない。右はしの出口の高さ0・2・5・7・9・11・14・16が足した合計を表し、全部を足す太い道は合計16の出口に着くCredit: ナゾロジー

階段と平らな通路が交わる所は交差点になっていて、そこでは曲がらずにまっすぐ抜けるのが決まりです。違う道をたどっても合計が同じになる時は、道が合流して同じ出口に着きます。

こうすると「ちょうど16になる組み合わせはあるか」という問いは、「16の高さの出口までたどり着ける道はあるか」に置きかわります。

組み合わせを1つずつ順に確かめるやり方は、1人の人がすべての道を順番に歩いて確かめるようなものです。一方、大勢の人をいっせいに迷路に送り込めば、たくさんの道を同時に調べられます。

これまでにも、細胞の中で働くタンパク質の細い繊維などを、人の代わりに小さな迷路に走らせる研究が行われてきました。しかし計算を始める段階が順番待ちになって詰まり、大きな問題では、やはり時間がかかりすぎるという弱点がありました。

また、組み合わせを1つずつ順に確かめる方法も、DNAや迷路を使っていっせいに調べる方法も、問題が大きくなるにつれて、何かを爆発的に増やさなければなりません。順に確かめるコンピューターなら計算時間、DNAを使う方法ならDNAの量、迷路を使う方法なら迷路の大きさと、迷路を進む仲間の数です。

そこで研究チームが迷路に送り込んだのが、自分で泳ぎ、分裂して増える細菌でした。

ここは人の例えでは表せません。迷路を歩く人が途中で増えることはありませんが、細菌は迷路を泳ぎながら、体を2つに分けて増えていきます。

つまり、計算を受け持つ数が、計算の途中でひとりでに増えていくのです。

研究チームはこれを、組み合わせの爆発的な増え方に、細菌の爆発的な増え方で立ち向かう作戦だと説明しています。

とはいえ、細菌は数学を知りません。ただ泳いでいるだけの細菌に、本当に正しい出口が見つけられるのでしょうか?

記事全体を読む