クロックによるゴミ掃除
2006/08/23
前節では、たった1つのボールと履歴記録テープを用いて可逆チューリングマシンを構成する方法を考えた。 可逆チューリングマシンが演算の後に残すのは、記録テープに残された演算の結果と履歴の列である。 必要とされる演算結果以外の「データのゴミ」を残すのは、可逆コンピュータの特徴の1つだ。 ビリヤードボール・コンピュータの場合、演算後にはどこにボールが入っているかわからない箱の列が残った。 可逆チューリングマシンの場合には、何が記録されたかわからない履歴記録テープが残される。 つまりこの2つは、途中の演算が複数のボールによって並列に進行するか、1個のボールによって直列に進行するかの違いがあるものの、最終的な生成物は本質的に同じなのである。 可逆コンピュータであれば、演算の途中で生じた余分な(答として必要とされない)結果をデータの形で残す必要に迫られる。 不可逆なコンピュータは、余分なデータが生じるたびに(各素子、各ステップごとに)それらを熱の形でコンピュータの外に捨て去っている。 可逆コンピュータの演算後に残された「データのゴミ」は、不可逆なコンピュータが捨て去っていた熱と同じ意味合いを有しているのである。
可逆コンピュータで生じる「データのゴミ」を、不可逆コンピュータの様なエネルギー消費なしに上手く掃除する方法は無いものだろうか。
「データのゴミ」を掃除するとは、何が記録されているか不明な状態を、明確な状態に戻す作業のことを指す。
履歴記録テープで言えば、全ての履歴ビットを消去して0にする作業のことである。
実のところ、前節で挙げた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通りのパターンそれぞれについてビットの書き換えと時間調整を行う。 つまり下表を全て埋め尽くす作業を行うのである。
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個のボールを使って演算を行い、記録テープをクリーンに保てることが確認できた。 このとき、全ての処理を終える時間の長さは固定にはなり得ない。 処理時間の長さにパターン数を持たせることによって初めて、データのゴミ掃除が可能となるのである。
|