第三章 可逆コンピュータからの発想
可逆コンピュータとは
2006/08/23  

コンピュータで演算を行う為には、最低限どれだけのエネルギーを必要とするか? 答えはゼロ。 理論的には、演算そのものに必要なエネルギーはいくらでも小さくすることができる。 なぜ、ゼロで済むのか。 それは、コンピュータを全て可逆な素子から作り上げることができるからだ。 可逆な素子で構成されているということは、演算結果から演算前の元の状態に戻せるということである。 もし演算の途中でエネルギーを失っているのであれば、結果を元の状態に戻すことはできない。 従って、可逆な素子から成るコンピュータは余計なエネルギーを一切必要としないことになる。

それでは、可逆な素子から成るコンピュータとは一体どのようなものであろうか。 可逆な素子とは、演算結果である出力から入力が再現できる素子のことを指す。 例えばNOTという演算は、結果に対してもう一度NOTを施せば元の状態を再現できる。 ゆえにNOTは可逆である。 一般的にコンピュータは AND、OR、NOT によって構成されている。※ この3つのうちNOTは可逆だが、残るANDとORは可逆ではない。 もしANDの結果が0であった場合、その入力は0と1の組だったのか、0と0の組だったのか分からないからである。 同様に、ORの結果が1だった場合は、0or1だったのか、1or1だったのか分からない。 なので、可逆なコンピュータを作るには AND、ORではない、もっと別の素子を用いなければならない。

考えてみると、AND、ORの様に2本の入力に対して出力が1本だけの素子は可逆にはなり得ない。 可逆な素子は2本の入力に対して2本の出力を持つに違いない。 ここで、可逆素子NOTを拡張した制御付NOT(Controlled NOT)という素子を考えてみよう。 制御付NOTは、通常のNOTにもう1本の制御入力を付け加えたもので、2本の入力と2本の出力がある。 そして、制御付NOTは制御入力に1が入力されたときにだけNOTとして働き、信号の反転を行う。 制御入力が0の場合には何も行わず、入力信号はそのまま出力される。 制御付NOTの残るもう1つの出力は、制御入力をそのまま出力する。

  [制御付NOTの入出力表] (Aが制御入出力)
Ain Bin   Aout Bout
 
 
 
 
制御付NOTゲート
この制御付NOTは、出力から入力を再現することができるので可逆である。 単純なNOTと同様、制御付NOTは2回繰り返すと元の状態に戻る。

さて、いま考えた制御付NOTだけでコンピュータが作れるかというと、残念ながらこれだけでは役不足である。 制御付NOTだけで(AND、OR、NOTで構成されたコンピュータと同等能力の)コンピュータを作ることはできない。 コンピュータを作るには制御付NOTをもう1段階パワーアップする必要がある。 そこで、制御付NOTにもう1本制御線を増やした二重制御付NOT(Controlled Controlled NOT)というものを考えよう。 二重制御付NOTには、3本の入力と3本の出力がある。 このうちの2本は制御入力である。 二重制御付NOTは、2本の制御入力が両方とも1だった場合のみNOTとして働き、信号の反転を行う。

[二重制御付NOTの入出力表] (A,Bが制御入出力)
Ain Bin Cin   Aout Bout Cout
0 0 0   0 0 0
0 0 1   0 0 1
0 1 0   0 1 0
0 1 1   0 1 1
1 0 0   1 0 0
1 0 1   1 0 1
1 1 0   1 1 1
1 1 1   1 1 0
二重制御付NOTゲート
二重制御付NOTも、2回繰り返すと元の状態に戻る可逆素子である。 上の説明の「両方とも1だった場合のみ」というくだりがANDと類似していることに注意されたい。 二重制御付NOTはANDと同等の能力を有しているのである。 上の入出力表でCinを0に固定すれば、Cout は Ain AND Bin となっている。※

二重制御付NOTはAND演算を行うことができる。 また、二重制御付NOTはもちろん単なるNOT演算を行うこともできる。 さらに、ORという演算はANDとNOTを組み合わせて作り出すことができる。

NOT( (NOT A) AND (NOT B) ) = A OR B
つまり二重制御付NOTからは AND、OR、NOT 3つの素子が作り出せる。 そしてコンピュータは AND、OR、NOT の3つから成り立っているのだから、結局のところ二重制御付NOTのみによってコンピュータが作り出せるのである。 二重制御付NOTだけで作ったコンピュータは可逆である。 いまここに二重制御付NOTだけで作ったコンピュータがあったとしよう。 その隣に、元のコンピュータと全く逆に二重制御付NOTを配置した「反コンピュータ」を置く。 もとの「正コンピュータ」の演算結果を「反コンピュータ」に入力すれば、反コンピュータは正コンピュータの全く逆の道筋をたどって演算前の状態を再現するはずだ。

コンピュータを構成するには二重制御付NOTで十分なのだが、その上さらに、入力する1の数と出力する1の数が等しくなるような可逆素子を考え出した人たちがいる。 フレトキンと、トフォリという人たちである。 彼らの考案した素子はフレトキン・トフォリ・ゲートと呼ばれている。(以下FTゲートと略す) FTゲートには3本の入力と3本の出力がある。 このうちの1本が制御線となっている。 制御入力が1のとき、FTゲートは残る2本の線の値を交換する。 制御入力が0のとき、FTゲートは残る2本の線に対して何もしない。 制御出力には、制御入力と同じ値が出力される。

[FTゲートの入出力表] (Aが制御入出力)
Ain Bin Cin   Aout Bout Cout
0 0 0   0 0 0
0 0 1   0 0 1
0 1 0   0 1 0
0 1 1   0 1 1
1 0 0   1 0 0
1 0 1   1 1 0
1 1 0   1 0 1
1 1 1   1 1 1
FTゲート
FTゲートは値を交換するだけなのだから、当然入力する1の数と出力する1の数が等しい可逆素子となる。 そして驚くべきことに、このFTゲートだけでコンピュータを構成することができる。
・Binを0に固定すると、Bout = Ain AND Cin
・Binを1に固定すると、Cout = Ain OR Cin
・Binを1に、Cinを0に固定すると、Bout = NOT A
となるので、確かにFTゲートによってAND、OR、NOT の3素子が作り出せる。

これまでに登場した素子は抽象的な1と0の挙動を追っただけで、それが物理的にどのような実体を持つのかについては一切触れていなかった。 ここでFTゲートを念頭に置くと、大変面白い物理的イメージを思い描くことができる。 それはちょうどビリヤードのように、運動するボールが互いに衝突を繰り返して演算を行うというイメージだ。 2個(ときには1個)のボールの衝突は、ボールが存在する場合を1、存在しない場合を0と見なせば、AND素子と同じ意味を持つ。 この考え方を延長して、ボールと、うまくボールを跳ね返す反射板を組み合わせてFTゲートを形作ることができる。

ビリヤードボールによるFTゲート

ボールと反射板によってFTゲートができるならば、それらをさらに組み合わせてコンピュータを作ることができるわけだ。 このボールと反射板でできたコンピュータが可逆なことは直感的にもわかるだろう。 ボールを転がすことによって演算を行った後、さらにその先に反射板を置いて正確にボールの運動を逆転する。 そうすれば、ボールは来た道の逆を正確にたどって、また元の状態に戻ることだろう。

以上のような「ビリヤードボールコンピュータ」のイメージを持てば、当初の問いかけに対して明確に答えることができる。 コンピュータで演算を行う為には、最低限どれだけのエネルギーを必要とするか? 演算自体にかかるエネルギーに下限はない。 摩擦のない床の上を転がるボールがいつまでも止まらないのだから、「ビリヤードボールコンピュータ」も最初にある一定のエネルギーを与えておけば後はいつまでも動き続けるのである。 (反射板を置いておけば入力と出力の間を往復し続ける。) ボールを運動させるのに必要となるエネルギーに(古典的に考えた場合)下限はないのだから、コンピュータの演算に必要なエネルギーにも下限は存在しない。 (いくらでも0に近い値がとれる。) 最も理想的な状況を考えた場合、コンピュータの演算は惑星の運動の様に永久に続くものだったのである。


実はANDとNOTからORを構成することができるので、最低限ANDとNOTだけでコンピュータを作ることができる。 また、ORとNOTからANDを構成することもできるので、ORとNOTを基本的な素子とすることもできる。 ただ、ANDとNOTだけ、あるいはORとNOTだけではどことなく対称性が悪いので、一般にはAND,OR,NOTを基本とすることが多い。


ここではANDと同等の能力を持つ二重制御付NOTを考えたが、もう1つ、ORと同等の能力を持つ二重制御付NOTというものも考えることができるだろう。 つまり、「どちらか一方が1だった場合に」NOTとして働き、信号の反転を行う素子というものが考えられる。 このような ORを内包する二重制御付NOTも、ANDを内包する二重制御付NOTと同じようにコンピュータの基本素子となり得る。
ページ先頭に戻る▲