自分の理解のための自分へのメモ。
間違ってたら自分の理解が間違っているということなので、あしからず。
π計算はCCSの拡張なのでCCSを説明する。
CCSとは、Calculus of Communicating Systemの略。
コミュニケーション(通信)システムを抽象化したもの。
なんとなく抽象機械と比べてみよう。
データを記した列(テープ)と、状態遷移表で構成される。
最小のデータは、テープ上の記号。(0と1が馴染み深い)
最小の振る舞いは状態遷移。
ラムダ計算
λ(ラムダ)といくつかの記号で構成される。
最小のデータは関数
最小の振る舞いは関数適用
CCS/π計算
チャネルといくつかの記号で構成される。
最小のデータはチャネル(通信ポートのようなもの)
最小の振る舞いは通信(チャネル同士の相互作用)
それぞれ全く異なるように見えても、全てチューリング完全(どんなプログラムも書ける)である。
…CSSを説明する前に力尽きたのである。