ぱらぱらめくる『Interaction Combinators』
- この「ぱらぱら」のモチベーションは、「情報が入ってきて、決断する」というプロセスを整理するための道具として便利そうな印象があるから
- 決断を「回路」的に考える
- 計算機(チューリングマシンやcellular automataやrewrite systemsとかそういったもの)として表現されている「計算機(入力があって、出力を決める)」っていうのは、何なの？ということ自体を扱いたい
- あっちこっちで処理が回る(distributed computation)であって、deterministic
- Interaction netsというもの
- 1個の主ポートとn=0個以上の(識別される)副ポートを持つセルを考える。n-arityと呼ぶ
- ポートはペアワイズにワイヤで結んでもよい
- ワイヤはただのサークルを作ってもよい
- このようなinteraction netsは次の集合によって定義される
- 繋がっていないフリーのポートの集合
- セルの集合
- セルを表すシンボル
- ワイヤの集合
- ワイヤの端のポートの集合(ただし両端の個数は0か2)
- これは、いわゆるグラフがノードの集合とエッジの集合(エッジには２つのノードが帰属する(２つのノードが等しいこともある)とのペアで定まるのと同じ。エッジには向きの有無などの属性があったり、重みがあったり、ノードにはラベルがあったりする点は、定義の修飾部分
- 上記のinteraction netsの定義が決まると、その定義の中で存在しうるすべてをパターンによって列挙することができ、それについて名称を定め、取り扱いやすくすることができる
- そんなのの一つが、２つのセルが主ポートをつないでできたもの(Interaction)というものだったりする
- また、それによってinteractionを定義すると、interactionが持つべき、性質として何かしらが定まってくる(方が都合が良くなり、それを定める)
- Interaction netsは「計算機」の仕組みを一般化して記述することを目的に導入したから、「計算機」の一つであるチューリングマシンが、interaction nets的に記載できることになる。cellular automataもできる。１項演算も。
- Reduced nets
- Interaction netsが汲みあげられると、「それって、入出力は同じで、簡便化したinteraction netsと同じじゃない？」となる(いかにもなりそう)であって、そんなもの
- 逆に言うと、「しっかりreducedしたnets」の集合が「計算機」の「演算」を決めてくれそう、と。
- じゃあ、できちゃったinteraction netsをreductionするルールがあった方がよいし、代数演算になると良さそう、というのも自然な発想
- ちょっと不安だけれど、この枠組みに２分岐木のreductionであるZDDとか(こちら)も入ってくるのでは…
