可逆コンピュータからの発想1ボール・チューリングマシン2006/08/23前の節ではビリヤードボールコンピュータ、複数のボールが互いにぶつかりあって演算を行う装置を紹介した。ここではさらに新しい種類の可逆コンピュータを考えてみようと思う。ここで扱うのは、たった1つのボールによって演算を行う装置である。いった演算を基本に考えたが、ここではより原理的なチューリングマシンを構成することを考えよう。チューリングマシンとは、本質的にただ1本の道筋をたどる装置である。チューリングマシンがただ1個のボールによって実現できそうなことは、およその想像がつく。以下にその様子を描き出してみよう。チューリングマシンとは、今日のデジタル・コンピュータの原型に相当する仮想的な装置である。デジタル・コンピュータ上で行われているどんな演算も、原理的には全てチューリングマシン上で行うことができる。チューリングマシンは、無限に長い記録テープ、テープの読み書きを行うヘッド、ヘッドの動作を決定する制御部、の3つから成っている。今日風に言えば、記録テープはメモリーであり、制御部はCPU、ヘッドはメモリーとCPUを結ぶバス(結線)である。記録テープは一定間隔のマス目に区切られていて、それぞれのマス目には値0か1のいずれかが書き込まれている。(書き込む値は1〜9までの数字やアルファベット26文字など多数の記号でも構わないのだが、それらは全て0,1に還元することができる。ヘッドはテープ上の値0,1を読んだり書いたりしながら、テープの上を行き来する。具体的にヘッドが実行できることは次の5項目である。・マス目の値を読み取る・マス目に0を書き込む・マス目に1を書き込む・マス目を1つ右に移動する・マス目を1つ左に移動する制御部は内部に有限個の状態を持ち、その状態によって次のヘッドの挙動を決定する。(制御部の持つ有限個の内部状態とは「フラグ」のことだと思えば分かりやすいだろう。チューリングマシンは次のようなサイクルで動作する。1:現在ヘッドがあるマス目の値を読み取る。2:読み取った値と、現在の内部状態に従って次の挙動を決定する。このとき同時に、内部状態も次の状態へと遷移する。(フラグが立つことがある)3:挙動に従って(必要であれば)マス目に0か1の値を書き込む。4:挙動に従って(必要であれば)右か左に移動する。*:特別な内部状態「停止」に至った場合、動作を停止する。これだけのことでコンピュータの持つ演算能力の全てをカバーしているのだ。重要なのは内部状態の遷移規則と、テープ上に最初に書き込んである0,1の配置にある。「内部状態の遷移規則」とはCPUの命令と実行結果、「テープ上に書かれた0,1の配置」とはプログラムに相当する。現代のパソコンを知る我々からすれば、チューリングマシンとはコンピュータの心臓部を取り出したものに見えるだろう。ここで1個のボールで動作するチューリングマシンを考えるにあたって、まずは用いることができる部品をリストアップしよう。ここで用いることができる部品は次の3種類だけだ。1:ボールと経路2:物体の移動3:条件分岐(合流)これらの3つの部品だけを用いてチューリングマシンを構成せよ、というのがここでの命題である。以下、それぞれの部品について順番に見てゆこう。最初に、摩擦のない一本の線上を運動する、ただ1個のボールを考える。ボールの通り道である線のことを「経路」と呼ぶことにする。摩擦がないので、一度動き出したボールは経路上をどこまでも(経路の終わりまで)転がり続ける。経路は空間内の任意の場所に配置することができる。経路は可逆でなければならない。ボールは経路上を双方向に、順方向にも逆方向にも転がることができる。経路は途中で分岐したり合流したりすることはできない。運動しているボールと衝突することによって、空間内に配置した特定の物体を移動することができる。静止している物体にボールが衝突すれば、ボールは跳ね返り、物体は移動を開始する。跳ね返ってきたボールを、衝突とは全く逆に移動中の物体にぶつければ、物体の移動はそこで止まる。物体の移動も可逆である。ボールが順方向に転がったとき物体がA->Bに移動したとすれば、その反対に、ボールが逆方向に転がったなら物体はB->Aに移動する。3:条件分岐(合流)経路上をさえぎる様に物体が置かれていた場合、ボールは物体に反射して運動の向きを変える。これによって、物体が置かれていた場合と置かれていなかった場合で、ボールを異なる2本の経路に導くことができる。物体の置かれている位置を条件として、ボールの運動を分岐させることができる。(これは、先の章で「ゲート」と呼んでいたものである)この条件分岐の過程を全く逆にたどれば、2本の経路を1本の経路に合流させることができる。逆に言えば経路の合流には、あらかじめ物体が所定の位置に置かれているといった条件が必要なのであって、何も無しに(エネルギーの損失無しに)自然に経路が合流することはない。条件分岐と、2:物体の移動を組み合わせることによって、コンピュータで扱う様々なロジックを実現することができる。同じ物体であっても、2:物体の移動の際には物体が動くのに、3:条件分岐では物体は動かない、というのはつじつまが合わないと思われるかもしれない。物体は特定のレールの上をスライドして動くものとして考え、ボールが縦方向から衝突したときは移動、横方向から衝突したときは条件分岐とすれば矛盾は避けられる。(また、条件分岐の場合、物体は必ずしも静止している必要はない。)以上の3種類の部品、ボールと経路と物体を上手に配置してチューリングマシンを構成しよう。1,0の書き込まれたテープ。これは物体が2状態の位置、例えばLとRのいずれかに置かれているものによって実現できる。1つのマス目が1つの物体に対応しているので、テープ全体は物体がたくさん(無限に)並んでいるものとなる。この物体には名前を付けた方が分かりやすいので、ここでは「メモリービット」と呼ぶことにしよう。テープの読み取りは、この物体、メモリービットにボールを衝突させることによって実現する。メモリービットは条件分岐となっていて、例えばメモリービットがLのときにボールは経路Lへ、メモリービットがRのときにボールは経路Rへと導かれる。2つの経路、LとRはそれぞれ別の入り口から制御部へと入る。ボールが入ってくる経路の違いはメモリービットから読み取った値の差異を表している。制御部には幾つかの物体が配置されており、それらの物体の配置によってボールの経路が変化する。「物体の配置=制御部の内部状態」なのである。制御部内に置かれた物体を、ここでは「フラグビット」と呼ぶことにしよう。フラグビットはボールの分岐条件となっているだけではない。その反対に、ボールの運動によってフラグビットの状態(配置)が変化することもある。制御部の動作の一例として、次の様なチューリングマシンを考えてみよう。・このチューリングマシンはただ1つのフラグビットXを持つ。Xは2つの状態、X=AとX=Bの2状態を取ることができる。・このチューリングマシンは、テープの読み取り値と、Xの状態によって下表の動作を行う。Aに遷移、0を書き込む、左に移動このチューリングマシンは何らかの演算を行う目的で作られたものではない。簡単な状態遷移と書き込みの例として挙げたものである。状態遷移表は「A,0,左」と「B,1,右」について対称なので(「A,0,左」と「B,1,右」を入れ替えても同じものになるので)どちらか片方の動作だけを追ってみることにする。テープの読みが0で、X=Aのとき、経路0から制御部に入ってきたボールはフラグビットXに衝突するものとしよう。ボールは衝突によって向きを変え、今度はフラグビットXをX=Bの位置に移動する。テープの読みが0で、X=Bのときは、ボールはフラグビットと衝突せず、制御部を素通りする。この時点でボールの経路はXに衝突した方と、していない方の2通りあることになる。これに続く、テープへの値の書き込み、制御部の移動は、どちらも物体の移動の応用なので詳細は省く。移動を終えたチューリングマシンが次のサイクルに入る際に、困った問題が生じる。ボールの経路が2通りに増えているため、次サイクルの開始点も2つ用意しなければならない。経路は1サイクルごとに2倍に増えてゆくので、いつかは装置が破綻することになる。チューリングマシンとは、そのままの形では可逆な部品で構成することができない、不可逆なコンピュータだったのである。このことはチューリングマシンの遷移状態図からもわかる。***チューリングマシンの動作には複数の異なった状態から同一の状態へと遷移する過程が幾つも含まれている。状態Aに至る過程は、「Aのまま」と「BからAに遷移」の2つがある。いった異なる状態から同一の状態への遷移は、逆向きにたどることはできない。逆にたどれば、ある同一の状態から複数の異なる状態のどこに戻るべきかか決められないからである。それでは、チューリングマシンを可逆な部品によって構成することはできないのだろうか。可逆なチューリングマシンを構成するには、増えた経路を1つにまとめる仕組みを追加する必要がある。ボールと物体によって構成された条件分岐(上記の部品3:)は、逆向きに動かせば経路の合流装置として働く。ここで経路Lと経路Rの2本の経路を経路Xの一本にまとめることを考えてみよう。経路Lから入ってきたボールがそのまま経路Xに直結していたとしよう。このとき経路Rから入ってきたボールも、最終的には経路Xに入るようにしたい。そこで、経路Rの先に1つの物体を置く。ボールは物体に衝突し、その位置を移動させる。物体は経路Xの延長上に移動し、反射後のボールをうまく経路Xに導くような位置にくる。このような移動する物体を1つ置くことによって、経路の合流が実現できるのである。もとのボールが2つの経路のどちら側から来たかという情報は、物体の位置に記録される。上の例では、ボールが経路Lから入ってきた場合、物体は経路X上には無く、ボールがRから入ってきた場合、物体は経路X上に置かれることになる。言い換えれば、経路が1つになる代わりに、物体の配置が2通りになるのである。ここで経路を1つにするために用いた物体のことを、ボールの経路を記録したという意味で「履歴ビット」と呼ぶことにする。(不可逆な)チューリングマシンを動作させると、各サイクルごとに経路の総数が増えてゆく。経路を合流させるための仕組みは、各サイクルごとに用意しなければならない。結果的にそれは「履歴ビット」をたくさん並べたもの、履歴用の記録テープという形になるだろう。履歴用の記録テープは、最初には既知の値、例えば全て0が書かれている。経路を合流させる度に履歴ビットが使われてゆくので、履歴記録テープには0か1か、いずれかの値が刻まれてゆくのである。履歴用の記録テープを持つ可逆なチューリングマシンは、およそ次の様な動作を行う。1:各サイクルを通常通り(上に述べたのと不可逆チューリングマシーンと同じように)実行する。2:1サイクル実行ごとに、経路の取り得る総数は次の数だけ増大する。経路の総数=(0,1)の2パターンx遷移パターン数x(右、左、移動なし)の3パターン3:増大した経路の総数を、履歴ビットを用いて1つにまとめる。仮に履歴ビットが記録テープのような形状をしていたとすれば、各サイクルごとにNビットの履歴記録テープを書き進めることになるだろう。4:もう少し詳細を検討すると、履歴記録テープの扱いには幾つかの仕組みが必要になってくる。a.1つの履歴ビットに書き込んだ後、次の履歴ビットにコマを進めるb.S本の経路に対してNビットの履歴テープをあてがう。これらの機能は全て固定的な仕組みで実現できるため詳細は割愛するが、概ね次の様になるだろう。履歴ビットへの書き込み装置(書き込みヘッド)は、書き込みの後無条件に次のコマに移動する。この装置は「物体の移動」によって実現できて、その過程に経路の分岐は無い。S本の経路に対してNビットの履歴テープをあてがう処理はやや複雑である。ln[2](Smax)をあてがうことである。この方法であれば、固定的な仕組みによって実現できる。この方法だとSmaxにならなかったサイクルでは無駄な履歴ビット(Nmax-N)を消費してしまうので、いささか効率が悪い。それでも、とにかくこの「毎回最大ビット数をあてがう」方法で一応の機能はカバーしている。5:履歴ビットを用いて経路が1つにまとまれば、次のサイクルを問題なく1つの開始点から(現在ヘッドのある位置から)スタートさせることができる。以上の様な仕組みを用意すれば、たった1つのボールで可逆なチューリングマシンを実現することができる。チューリングマシンとは本来不可逆なので、可逆に動作させようとすれば何らかの仕組み、例えば履歴記録テープを付け加える必要がある。可逆チューリングマシンは、実在のコンピュータと比べて計算速度の面で猛烈に効率が悪い。それでも、可逆チューリングマシンはエネルギー消費の面では実在のコンピュータを上回るであろうし、何よりもたった1個のボールでコンピュータの全てが実現できることは興味深い。※ここで紹介したチューリングマシンは、元来のチューリングが考案したものと同一ではなく、幾つかのアレンジが入っていることをお断りしておく。オリジナルのチューリングマシンでは、1,0だけではなく、複数の記号の読み書きを扱っていた。オリジナルでは記号が書いてある部分は有限長であり、そこから先は記号が書かれていない空白の状態としていた。本論で示したチューリングマシンは、記号が1,0だけで、空白状態を考えていない。(もともとテープは0で埋まっているもと考えている。一見するとこれではコンピュータとしての動作がおぼつかない様に思えるかもしれない。2進数で数字を書き込むことを考えると、データの一部を表す0なのか、空白状態の(最初からテープを埋めていた)0なのか区別がつかないのではないか。確かに、一般的な2進数のコンピュータを念頭に置けば、この疑問はもっともかもしれない。ところが、実のところ工夫次第で1と0しかないテープであってもチューリングマシンを構成することができるのである。・2進数ではなく、単純に1の並びの長さによって1つの数字を表現する。・1の間に挟まった0を、数字同士の区切り文字として用いる。・0が2個以上続いていたらデータの終点を表す。いう方法で(2進数より効率は悪いが)あらゆる数字列を表現できる。「皇帝の新しい心(ペンローズ)」という本に1と0しかないチューリングマシンの例が載っているので、参照されたい。可逆チューリングマシンを構成する方法として、ベネットは逆動作チューリングマシンをペアにして置くことを考えた。逆方向チューリングマシン「ファインマン計算機科学」に載っていた。