状態遷移マシンは、計算機構のモデルとして有名なものだし重要ですよね。僕が「ホッピングボール・マシン」と名付けた（適切な名前が見あたらなかったので）モデルは、とても単純な状態遷移マシンです。これ以上の単純化は難しいというくらい単純です。
この単純なモデルであるホッピングボール・マシンは、プログラム意味論はもとより、圏論、論理、グラフ理論などの立場からも興味深い素材で、この素材を使って次のようなことを説明できます。
- 振る舞い意味論
- 模倣／双模倣
- モノイド圏
- 高次圏
- 計算現象と物理現象のアナロジー
- 一般化された行列計算
僕が「面白いなー」と思っていることはだいたい、ホッピングボール・マシンを例題として解説できそうです。以前から、ホッピングボール・マシンとその周辺について書きたいとは思っていたのです。でも、なかなか書き出せないでいました。
ホッピングボール・マシン自体は単純なんですが、背後に非常に豊かな構造があるので、関連する分野は多岐に渡ります。長い解説を書く気力はないし、ブログ記事の続き物にするにしても息切れしそう。
でもまー、息切れするのはいつものことだし、思い出してまた続きを書いたりすることもあるので、あまり気張らないで書き始めることにします。続き物のスタイルにはしませんが、エントリータイトルに「ホッピングボール：」を含めたら、この話題の記事です。
全体目次：
- ホッピングボール：書きはじめよう、ゆるゆると（当エントリー）
- ホッピングボール：何が面白いのか、どんなことを考えるのか
- ホッピングボール：サイクルだけのマシンの観測結果はどうなる
- ホッピングボール：エキゾチック二進小数
関連記事：
今回内容：
●ホッピングボール・マシンとは何か
ホッピングボール・マシン（hopping ball machine）とは、下の図のような箱です。
手前にいくつかの（例では3つの）穴が空いてます。ここからボールを入れます。入れたボールは何秒後かに向こうにある穴（例では2つ）のどれかから出てきます。入り口となる穴にも出口となる穴にも、それぞれ「1, 2, ...」と番号が振ってあります。また、ボールを入れてから出てくるまでの時間はキッチリ秒単位で計れるものとします。したがって、次のような言明は（正しいか間違っているかはともかくも）意味を持ちます。
- 1番の入り口穴から入れたボールは、4秒後に1番の出口穴から出てきた。
- 2番の入り口穴から入れたボールは、5秒後に2番の出口穴から出てきた。
- 3番の入り口穴から入れたボールは、1秒後に1番の出口穴から出てきた。
このような言明は今後頻繁に出てくるので、次のような略記をします。
- 1 -(4秒)→ 1
- 2 -(5秒)→ 2
- 3 -(1秒)→ 1
特別なケースとして、入れたボールがすぐさま出口の穴から飛び出すことがあります。このときは次のように書きます。
- 1 -(0秒)→ 2
0秒後に出てくるとはつまり、「入れたらすぐに出てくる」ということです。今まで例に挙げた「1 -(4秒)→ 1」、「2 -(5秒)→ 2」、「3 -(1秒)→ 1」、「1 -(0秒)→ 2」などを、ホッピングボール・マシンに関する観測命題と呼びます。
とある入り口穴にボールを入れて、それがどの出口穴から何秒後に出てくるかを観測することを試行と呼びましょう。1回の試行の結果は、1つの観測命題で述べられます。ただし、有限時間でボールが出てくることは保証していません。いつまでたっても出てこないことがあります。
ホッピングボール・マシンの動作は非決定的です。つまり、同じ入り口穴にボールをいれても試行のたびに結果が違うかもしれません。例えば、最初の試行で「2 -(6秒)→ 2」だったのに、2回目の試行では「2 -(2秒)→ 1」、3回目の試行では「2 -(3秒)→ 2」となるかもしれません。
●ホッピングボール・マシンの内部構造
ホッピングボール・マシンを外から見れば、完全なブラックボックスです。ホッピングボール・マシンに対して出来る操作は、入り口の穴にボールを入れることだけです。そして、出口の穴から出てくるボールを確認して「2 -(4秒)→ 1」のような観測命題を述べるのです。
でも、いざとなったらホッピングボール・マシンの箱を開けて中を覗いてもかまいません。ホッピングボール・マシンの動作は非決定的でも、中の仕掛けは決まっています。ノードと呼ばれる場所と、ノードとノードを結ぶ辺と呼ばれる矢印から構成されています。これを図示すると有向グラフとしてよく知られた図形になります。下の図は、ホッピングボール・マシンの構造を図示した例です。黒丸が内部のノード、実線の矢印は辺、白丸は穴で、点線により穴とノードの結びつきを示しています。
入り口の穴からホッピングボール・マシンの内部に入ったボールは、まずどれかのノードに落ちます。ボールは辺をたどって、1秒後には別なノードに移動します。この動作を何度か繰り返すことになります。ノードのうちのいくつかは出口の穴とつながっていて、そのようなノードに到着したら、ボールはジャンプして出口から出てもかまいません。次の点に注意してください。
- ボールが入り口からノードに落ちるときと、ノードから出口にジャンプするときには時間がかからない。
- 辺でつながれていないノード間では、ボールは移動できない。
- とあるノードから同じノードに戻る辺（ループ）があってもよい。
- ノード間のボールの移動には常にキッカリ1秒かかる。これは、図に描いた辺の長さとは無関係、ループを回るときも1秒。
- ノードが出口の穴とつながっていても、ボールが他のノード（または、ループ経由で同じノード）に移動できるなら出なくてもよい。
- 移動または出口へのジャンプのどちらかができるなら、必ずしなくてはならない。
- 移動も出口へのジャンプもできないなら、そのボールは永久に同じノードに留まる。
- 出入り口の穴とノードとの結びつき（点線で表示）は1対1である必要はない。
ノードから出る辺は1本とは限らないので、ボールの移動に非決定性が現れます。同じ入り口からボールを入れても、どのような経路を通ったかによって、出口と所要時間に差が出るのです。
●ホッピングボール・マシンの例
入り口も出口も1つの例です。
このホッピングボール・マシンでは、1番入り口から入れたボールは瞬時に1番出口に出ます。観測命題「1 -(0秒)→ 1」がいつでも成立します。「1 -(0)→ 1」以外は起きません。
次も、入り口／出口が1つずつ。
内部にループを持っているので、ループを回る回数により、出てくるまでの所要時間が変わります。「1 -(0秒)→ 1」、「1 -(1秒)→ 1」、「1 -(2秒)→ 1」、「1 -(3秒)→ 1」など、すべての可能性があります。
入り口が1つ、出口が2つです。
「1 -(0秒)→ 1」または「1 -(0秒)→2」のどちらかが必ず起きます。それ以外の可能性はありません。
入り口が2つ、出口も2つです。
このホッピングボール・マシンでは、「1 -(0秒)→ 2」と「2 -(0秒)→1」が必ず起きます。入り口が1番なら、必ず2番出口からボールが出てきて、入り口が2番なら、必ず1番出口からボールが出てきます。
これも、入り口が2つ、出口も2つ。
任意のn（n = 0, 1, 2, ...）に対して「1 -(n秒)→ 1」と「1 -(n秒)→ 2」が起こりえます。しかし、2番入り口から入れたボールは永久に出てきません。
●ゆるゆると続く
これで、主題であるホッピングボール・マシンがどんなものかは説明しました。細部まで完全には記述してないのですが、だいたいのイメージを作るには十分でしょう。たったこれだけの仕掛けなのに、ほんとに驚くくらいに豊富な構造を持ち、多様な現象を生成します。
まー、ぼちぼち、ゆるゆると説明していきます。
