可逆コンピュータからの発想クロックによるゴミ掃除2006/08/23前節では、たった1つのボールと履歴記録テープを用いて可逆チューリングマシンを構成する方法を考えた。可逆チューリングマシンが演算の後に残すのは、記録テープに残された演算の結果と履歴の列である。必要とされる演算結果以外の「データのゴミ」を残すのは、可逆コンピュータの特徴の1つだ。ビリヤードボール・コンピュータの場合、演算後にはどこにボールが入っているかわからない箱の列が残った。可逆チューリングマシンの場合には、何が記録されたかわからない履歴記録テープが残される。この2つは、途中の演算が複数のボールによって並列に進行するか、1個のボールによって直列に進行するかの違いがあるものの、最終的な生成物は本質的に同じなのである。可逆コンピュータであれば、演算の途中で生じた余分な(答として必要とされない)結果をデータの形で残す必要に迫られる。不可逆なコンピュータは、余分なデータが生じるたびに(各素子、各ステップごとに)それらを熱の形でコンピュータの外に捨て去っている。可逆コンピュータの演算後に残された「データのゴミ」は、不可逆なコンピュータが捨て去っていた熱と同じ意味合いを有しているのである。可逆コンピュータで生じる「データのゴミ」を、不可逆コンピュータの様なエネルギー消費なしに上手く掃除する方法は無いものだろうか。「データのゴミ」を掃除するとは、何が記録されているか不明な状態を、明確な状態に戻す作業のことを指す。履歴記録テープで言えば、全ての履歴ビットを消去して0にする作業のことである。実のところ、前節で挙げた3種類の可逆な部品、1:ボールと経路2:物体の移動3:条件分岐(合流)だけを用いてデータのゴミ掃除を行うことはできない。(だたし、全ての演算を逆向きに行って元の状態に戻す、という掃除の方法は除く。データのゴミ掃除を行うには、部品をもう一種類つけ加える必要がある。その4番目の部品とは「周期的に運動する物体」、即ち「クロック」である。4:クロック(時計)周期的に運動している物体にボールを衝突させることによって、ボールの経路を変える仕組み。ボールの経路は物体と衝突した時刻によって切り替わる。この仕組みは、例えば回転する反射板にボールをぶつけることによって実現できる。反射板にぶつかるタイミング(回転の位相)によって、ボールは相異なる特定の方向に反射する。単純な回転する板だと、衝突の際にボールと反射板との間にエネルギーのやりとりが生じてしまう。これを防ぐため、衝突の瞬間に反射板をしっかりと固定し、ボールの勢いで反射板の周期運動が攪乱されないような仕掛けを施す必要がある。反射板を固定する仕掛けは同時に、ボールの経路を連続的にではなく、離散的な固定した方向に向ける役割も果たす。固定する仕掛けの付いた反射板は、例えば板とストッパーとクロック用ボールの3つの部品によって構成できるであろう。***反射板はあたかも時計の秒針のように、すばやく移動、停止、を繰り返すことになる。現実の時計はゼンマイなどに蓄えられたエネルギーを少しずつ消費するが、ここでは摩擦の無い世界を考え、クロック自体にエネルギーの損失は無いものとする。クロックを用いて異なる経路を1つにまとめる方法を考えてみよう。経路を1つにまとめるとは、経路を2つに分岐する過程の逆のことだ。経路を分岐する過程は、回転する反射板のイメージを思い描けば容易に想像が付く。反射板と衝突するタイミングによって、ボールは異なる方向に弾き返される。仮に、時刻Aでぶつけたボールは経路Aへ、時刻Bでぶつけたボールは経路Bに向かうとしよう。この逆の過程を経れば、2つの経路AとBから来たボールを1つにまとめることができるはずだ。いま、何らかの原因によって、例えばメモリービットの読み取り等によって、ボールの経路が2つに分岐したとする。2つの経路をA、Bとしたとき、Bの経路をAの経路よりも長くとって、通過に余計な時間を要するように配置する。すれば、AとBから出てきたボールを異なるタイミングで反射板にぶつけることができる。経路の長さと反射板の位相を調整すれば、2つの経路から来たタイミングの異なるボールを1つの経路に導くことができるだろう。このクロックを用いた経路の合流とは、つまるところ経路の違いを時間の違いに置き換える仕組みである。経路の本数を減らせる代わりに、経路を通過するボールのタイミング、時間に対するパターン数は増大する。次に、クロックを用いてNビットの履歴記録テープを掃除(0クリアー)する方法を考えてみる。この仕組みを1ボールチューリングマシンの後つなげることができれば、データのゴミを残さない「クリーンな」マシンが実現できることになる。記録テープ掃除の基本的な考え方は、上に示した1ビット(2通り)の経路をまとめる方法の応用に過ぎない。ある記録ビットを読み込み、その値が0ならば何もせず、1ならば値を0に書き換える。その結果、ボールの経路は値が0の場合と1の場合の2通りになる。この2通りの経路を1本にまとめる処理は、1つのクロックを用い、ボールのタイミングをずらすことによって実現できる。これで長さ1ビットの記録テープの掃除はできたわけだが、もっと長いテープの場合はどうだろうか。長いテープを掃除する最も直接的な方法は、全パターン分の経路を用意することだ。長さNビットのテープに書き込める1か0のパターン数は全部で2^Nである。いうことは、1個のボールでNビットのテープを読み取った場合、ボールの経路は2^Nに分岐する。ここで、1ビットで行った方法をそのまま応用し、2^N通りのパターンそれぞれについてビットの書き換えと時間調整を行う。下表を全て埋め尽くす作業を行うのである。・パターン0のとき、何もしない、経路の通過にT秒かかる。・パターン1のとき、1ビット目を0に書き換える、経路の通過にT+1秒かかる。・パターン2のとき、2ビット目を0に書き換える、経路の通過にT+2秒かかる。・パターン3のとき、1ビット目と2ビット目を0に書き換える、経路の通過にT+3秒かかる。・パターン4のとき、3ビット目を0に書き換える、経路の通過にT+4秒かかる。・パターン2^Nのとき、全ビットを0に書き換える、経路の通過にT+2^N秒かかる。この表では、パターン番号をビットの2進数に対応させてある。最後に、2^Nに分岐した経路を1つにまとめるため、反射板の向きが2^Nだけあるようなクロックを用意する。時計の秒針が60通り、64=2^6だから、時計の秒針程度の刻みだと6ビットに対応することもできない。長い記録テープを1まとめにするには、時計よりもずっと細かい刻み巾の反射板が必要となるだろう。非常に高い精度を要求されることにはなるが、とにかく理屈の上では高精度のクロックさえあれば長い記録テープをただ1個のボールによって0クリアーすることができるのである。このとき、Nビットのテープが0クリアーされる代わりに、ボールの時間に対するパターン数は2^N通りに増大する。1個のボールによるデータのゴミ掃除の本質は、上でほぼ出尽くしている。「Nビットのデータのゴミ処理を行うには、ボールの時間に対するパターン数を2^N通りに増やさなければならない。以下はやや蛇足気味ではあるが、もう少しスマートなクロックの仕組みを紹介しよう。上ではただ1枚の反射板によって2^Nの経路を1まとめにすることを考えた。今回は反射板の数を増やす代わりに、1つ1つの反射板を単純化することを考える。反射板はN個用意する。その代わり、個々の反射板は2通りの経路を1つにまとめる機能だけを持つことにしよう。Nビットの長さの記録テープがあったとする。最初の1ビット目を読み取った値によって、ボールの経路は2つに分岐する。1ビット目の値を0に書き戻した後(あるいは何も行わずに値を0のまま保持した後)、1つ目のクロック(反射板)によってボールのタイミングをずらす。このとき、ボールのずれの間隔を2^(N−1)単位時間だけ開けておくのである。(「単位時間」とはクロックの時間分解能のこと。「秒」と読み替えてもよい。2ビット目は、1ビット目と同様の操作を行うのだが、ボールのずれの間隔を2^(N−2)単位時間とする。以下、iビット目ではずれの間隔を2^(N−i)単位時間とする。後のビットになるほどクロックの刻みが細かくなってゆく。この操作を最後のビットまで行えば、最後にボールが1つの経路から出てゆくときには2^N通りだけの時間に対するパターン数を持つことになる。いった具合に針を分けているのと同じように、この操作ではクロックごとに時間の「桁」を分けているのである。時計の針は60ごとに1つ上の位(針)となるのだが、ここでのクロックは2単位ごとに1つ上のクロックに繰り上がっている。空間上に配置されたパターンは、特定の操作を通じて時間軸上に配置されたパターンに変換することができる。1個のボールによるデータのゴミ掃除は、この事実をプリミティブなモデルによって確認したに過ぎない。可逆チューリングマシンとその後の処理によって、ただ1個のボールを使って演算を行い、記録テープをクリーンに保てることが確認できた。このとき、全ての処理を終える時間の長さは固定にはなり得ない。処理時間の長さにパターン数を持たせることによって初めて、データのゴミ掃除が可能となるのである。合流は任意の時間、位相でできるわけではない。(A:1秒後)、(B:2秒後)の組があった場合、(A:2秒後)の動作は不定だ。反射板のようなモデルで考えると、ボールが経路を外れてあさっての方向に飛んでいってしまう。ボールが許されない時間に入ってこないように、反射板の位相に合わせて経路の入り口にフタをすることは可能である。