One Ball Turing Machine -- 考え中. 2004/05/20 ● チューリングマシンを１個のボールで動作させることを考える。 => 最後に１ボールを排出する時間をずらすことによって、 いかなる演算も「ガベージ」無しに可逆的に行えることを示す。 計算における最低消費自由エネルギーはどれだけか？ 「演算自体には自由エネルギーを要しないが、メモリーをリセットする際にエネルギー散逸が欠かせない」 (Landauer's Principle) このことは、例えばフレトキンゲートによって構成された可逆コンピュータによって確認できる。 (Ballistic computers -- The ballistic models of Fredkin and Toffoli) フレトキンゲートは複数のボールを使ってAND,OR,NOTと等価な回路を構成するが、 実は、たった１つのボールだけでも計算機を構成することができる。 このことを示すには、AND,OR,NOTを作るよりも、１ボールでチューリングマシンが 作れることを示す方がてっとり早い。 フレトキンゲートによる可逆コンピュータでは、計算後のメモリ上に「ガベージ」が残る。 このガベージをリセットするプロセスが非可逆過程であり、エネルギー散逸が生じる。 １ボールチューリングマシンであってもテープ上にガベージが残る。 しかし、実はガベージのリセットは１ボールで行うことができることを以下に示そう。 この１ボールリセットを可能にするためには、どうしても時刻を記述する運動 〜 「時計」が必要となる。 ● １ボールができること。 0: 可逆的に与えられた「経路」の上を進む。 経路が勝手に分岐したり、合流したりはしない。 特に「合流」が無い、という認識が大切。 １bitの合流には1bit相当(kT*ln2)のエネルギー散逸が必要。 1: 可逆的に物体を移動させる。 ---------- | | ----->□ -> □ -----> ○ 2: 物体の位置によって、経路を分岐する。(ifのような動作) --- □位置A -----> パターンA ○ | □位置B -----> パターンB ○ 逆に動かせば合流となる。 (ただし、逆流するときにはボールのパターンと物体の位置が合っていなければならない。 例えばパターンB で逆流してきたとき、物体も位置B に合っていなければならないけれど） ● ２進時計 ここで言う「時計」とは、時間の進行に対して周期的に状態が変化する物体のこと。 最も簡単な時計は、ある物体が A -> B -> A -> B -> ... と２つの状態を行き来するもの。 この時計の状態 A 又は B によって、経路分岐が行えるものとする。 理想的な摩擦のない時計自体の動作には全くエネルギー消費が無いことに注意！ 例え時計がボールの経路に影響を与えたとしても、時計、ボールの持つエネルギーは増減しない。 （簡単な時計は「回転する反射板」だが、確実な動作のため 「ロック機構付きの２つの反射板を有した立体」をモデルとした方がよいでしょう） （運動量保存については、時計の置かれている地球を含めないと成り立たないのです） 我々になじみのある秒、分、時の時計は60状態で１つ上の針がカウントアップされるが、 ここでは２状態で１つ上の針がカウントアップする「２進時計」を考える。 「２進針」は無限に、秒針、２秒針、４秒針、８秒針、。。。と続くものとする。 ● ガベージコレクション = メモリーリセットの方法 １個のメモリーセル = Bit をボールを用いてリセットしようとすると、 セルがリセットする代わりにボールのパターンは２通りになる。 Bit : 1 or 0 -> 0 Ball : ○ -> A or B なぜなら、メモリーの２状態が１状態になったのだから、 ボールの方は１状態が（少なくとも）２状態（以上）にならないとつじつまが合わない。 同様の考えで、N個のメモリーBitをリセットすると、ボールの方は 2^N パターンとなる。 つまり、2^N 本の経路のうちの、どこかを走っているわけだ。 上の過程は メモリーの状態数 -> ボールの経路のパターン に置き換えたに過ぎない。可逆な過程では、この置き換えは１対１で行われる。 複数に分かれた経路を再び「合流」させることは可能だろうか。 他に何の影響も与えず「合流」だけを行うプロセスはありえない。（第２種永久機関） たとえばパターンA, B の合流には、適当な物体があって、 パターンＡ のときは位置Ａ パターンＢ のときは位置Ｂ といった置き方をしなければならない。 こうすればボールは合流するが、合流に使った物体はA,B２パターンとなってしまう。。。 つまり、また「ガベージ」を作ってしまう。 ところが。。。 「時計」を使えばガベージを生まずに２本の経路を合流させることができる。 いま、A -> B -> A -> B -> ... と時間変化している時計に対して ・ボールが経路Ａから来た場合は１クロック後に（奇数クロック後に） ・ボールが経路Ｂから来た場合は２クロック後に（偶数クロック後に） ちょうどぶつかる様に、経路の長さを調整する。 こうすれば２つの経路Ａ,Ｂから来たボールを同一の経路に乗せることができる。 ただし、もとの経路Ａ，Ｂの違いによって、最終的なボールの出力は１クロックだけ時間がずれている。 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 上のアイデアを拡張して、2^N 通りの経路からボールが来た場合には、 N本の針を持つ２進時計を用いれば、ボールを最終的に一つの経路に乗せることができる。 ただし、この場合ボールの時間が2^N通りにずれる。 このことは、逆にボールを時計によって「散らす」ことを考えれば納得できる。 時計に対して異なるタイミングでボールを当てれば、当てたタイミングによって ボールの最終的な経路は異なったものとなる。 つまり、メモリー上のガベージは「時計に対するボールのタイミング」に 載せ替えることができるのだ。 （相手が時計ではなく静止した物体なら、いつボールを当てても結果は同じはず。 これが「時計」を必要とする理由だ） ------------------------------------------------------------------------------- ... 後から考え直したところ、以下３つの考察は余計でした ... ● チューリングマシンは、どの範囲のメモリーを使用したか？ これを知るためには、テープは最初全てブランクで、 マシンは 0 か1 を書き込む、という設定にしなければならない。 そうすれば、ブランク以外の部分が使用済みでリセット対象、ということになる。 （あるいはメモリーを使用した、というだけのために余計な記憶装置を付け加えなければならない） メモリーリセットは、1 or 0 を全てブランクに戻す、という作業になる。 あと、１を書き込む、という動作は B -> 1 0 -> 1 1 -> 1 の３パターンとなるので、マシンの機構が複雑になる。 ● 時計と演算の同期についての問題 メモリークリアを開始する時刻に時計を合わせる必要があるけれど。。。 もし演算の後にメモリクリアを開始するのであれば、演算の時間の長さがわからないので クリア開始ポイントも不定になってしまう。。。。 => しかし、この問題は「あらかじめ演算時間を測定しておく」ことによって回避できるだろう。 演算開始と同時に、別の「演算時間測定ボール」を投げておく。 終了時に「演算時間測定ボール」の到達した位置を差し引きすることによって うまく時計のタイミングにボールを合わせることができるだろう。 「演算時間測定ボール」自身は確定的な〜１通りの動作しか行わないので問題なかろう。 余談。。。２進時計ではなく、回転板のイメージを持つと様子が違う。 回転板に異なる経路から異なるタイミングでボールを当てれば結果は１つの経路に落ち着く。 もし回転板の角度とボール入力のタイミングの同期をとらなければ、 最後の結果となる１つの経路自体の角度が不定になる。 。。。１つの経路には収まるのだが、どの１つの経路に収まるのかがわからない。 もっと簡単な解決策は、当初時計は静止しており、メモリークリア開始の時点でスタートボタンを押す、 という方法。こっちの方がスマートだが、ボールは少なくともボール自身と時計の始動のため、 ２倍のエネルギーを要してしまう。。。。 いや、時計には沢山針があるから、うんとエネルギーを要するかも。。。 ● チューリングマシンの動作による時刻のずれ マシンの動作中にも"エントロピー" = パターン数が随時発生する。 このパターン数をマシンの動作時刻をずらすことによって吸収する工夫が必要だ。 あるいは、マシン動作用の別のクリアーなメモリーを持っていて、 最後のリセット時にこちらもクリアーする方が良いでしょう。 「マシン動作専用のメモリ」を持てば、前術のクロック同期問題も回避できそうだ。 なぜなら毎クロックごとにカウントしておけば、そこで動作時間がわかるので、 動作時間から「時計」の同期タイミングが割り出せるでしょう。 ------------------------------------------------------------------------------- ● ... 改めて考え直しました ... チューリングマシンの「テープ上に印字された答え」を消す必要はないのです。 これが答えなのですから。 消すべきなのは、チューリングマシン動作のための「燃料テープ」、 最初は０(又は１)できれいに埋まっていて、１ステップ毎の「合流過程」で 汚れてゆくテープです。 このテープであれば汚れた長さも判るし、同期をとることもできます。 => 本質的には「汚れたテープをきれいにすること」、 テープ上の汚れを時計＋ボールのタイミングに置き換えることができればよいわけだ。 ● フレトキンゲートによって構成された可逆コンピュータであっても、 チューリングマシンと同様、時間信号への置き換えが可能です。 ・計算後、汚れたボールを「メモリ・ボックス」に閉じこめる。 ・メモリーボックスを整頓する（ボールが入っている１、入っていない０に分ける）。 ・分ける過程で時間差１ボールを用いる。 といったかんじ。 ===============================================================================