並列計算、ABCD構造、スパイダー、インターリーブ複体
とりとめない。
並列計算を理解したい! 高次遷移系を使いたい。higher-dimensional transition systems とか higher-dimensional automata とかで検索してそれなりに引っかかる。が、なんかピンと来ない。
組み合わせ幾何学の観点からは、単体的複体や方体的複体を扱うことになる。図形に対称性は期待できない。むしろ、非対称性、方向のような概念が重要になる。
組み合わせ複体を作るときは、モノイドや圏の脈体を作る方法がすごく重要になると思う。圏C内のモノイドの圏 Mon(C) が、CΔ で作れることは良いヒントになる。乗法と単位から生成される単体構造があって、コサイクル条件が単位律と結合律に対応している。
モノイド圏におけるモノイド積(テンソル積)と交替律も、並列計算の基本概念を提供する。対象のテンソル積は、独立・無干渉な2つのシステムを一緒に考えて複合システムの構成になる。独立・無干渉であることの主張が交替律になる。交替律を仮定する限り、干渉する複合システムは扱えない。
干渉する複合システムはどう作るか、というと、ファイバー積を作ればよいだろうが、ファイバー積の計算を系統的にしたい。それでスパイダー; 多圏の射の図をスパイダーと呼ぼうと考えていたが、形式テンソル(または抽象テンソル)と言えばいいので、スパンの拡張概念をスパイダーと呼ぼう。
有限完備な圏C上に、対象の部分類A, Bを考える。Aはattributeの類、Bはboundaryの類、ここまででABCとなる。実際は、Cはcodomain、Dはdomainを含めてABCD構造。さて、(C, A, B)内の錐を考える。錐の頂点をボディと呼ぶ。側線が3つのグループにわかれていて、それぞれのグループをD-脚、A-脚、C-脚と呼ぶ。脚のグループが空であってもよい。A-脚の端点(余域)はA類に入っている必要がある。D-脚とC-脚の端点はB類。
以上で定義した錐がスパイダー。スパンの制限と拡張であることは明らかだろう。2つのスパイダーf, gの結合は、fのC-脚とgのD-脚の端点群が一致するとき、そこに出来るマルチ・コスパンを使ってファイバー積を作ればいい。とはいっても、詳細はめんどくさい。
Cをまるまるスパイダーの圏に埋め込めるわけではないが、Cのなかの“興味ある射”はスパイダー圏に埋め込める。Cの結合も直積もスパイダー圏の結合で書けるので、スパイダー圏構成は、“興味ある射”だけを抜き出して計算を拡張したことになる。
ほんとにとりとめもないが、これらの話題はなんか相互に関係するような気がしている。並列計算と直列計算の関係は、同時並行実行がインターリーブでエミュレートできるかどうかに尽きるような気もする。任意のインターリーブで置き換え可能なら、複合システムは独立・非干渉だ。インターリーブで置き換え可能とは可換性を要求する。可換性もまた独立・非干渉の表明となる。
複合システム内で、2つのサブシステムがどの程度干渉しているか、どの程度絡んでいるか? を判定するときにホモトピー的情報が必要になる。このホモトピー的情報を組み合わせ的に計算するためには複体が前提になる。だからなにはともあれ複体を構成しなくちゃ。この複体の0次元部分は状態空間だ。セルは同時実行される複数のアクションの組だろう。インターリーブ可能性とかインターリーブの可換性が組み合わせトポロジー的な構造を決めるはずだ、たぶん。
並列計算の表現となる図形がインターリーブ複体。通常のモノイド圏(の脈体)は、インターリーブ複体の特殊ケースになるはず。なぜなら、モノイド圏は独立・無干渉な複合システムだけを扱う枠組みだから。依存・干渉が入ると、結合とテンソル積を分離して考えるのは困難になる。結合とテンソル積をファイバー積として混ぜて計算する体系がスパイダー計算系。
[追記]単体構造は辺作用素(単位)と退化作用素(乗法)で定義できる。
- δnk : [n]→[n+1] (k = 0, ..., n)
- σnk : [n+2]→[n+1] (k = 0, ..., n)
これに加えて、チェインの隣り合う成分の交換に意味があるときに交換する作用素 τnk:[n+2]→[n+2] (k = 0, ..., n) が必要になるのだろう。チェインが、自己射の列として与えられるなら交換作用素は常に意味を持つ。