「プログラムの算術的計算法 (続き＆完結）」に、Aがプログラムの文（複文や複雑な表現も含める）だとして、I + A + A2 + A3 + ... という無限級数形式が、非決定性の繰り返し、つまり「Aを何回か繰り返すこと、ただし何回かは不明／未定」を表すといいました。
実は、I + A + A2 + A3 + ... って無限級数形式は他でも登場するもので、これ、なかなかに面白いよ。ざっと説明しましょう。
プログラムと正規表現
既に指摘したように、プログラムの計算と正規表現（正規言語）の計算はよく似てます。
| 演算の概念 | プログラム | 正規表現 |
|---|---|---|
| 掛け算 | 順次実行 | 連接 |
| 足し算 | 非決定性の選択 | 合併（ユニオン） |
| 単位 | 何もしない文 | 空列のみの単元言語 |
| 零 | ハングする文 | 空集合 |
I + A + A2 + A3 + ... は、どちらの場合も、「任意回の繰り返し」（実行 or 連接）ですね。
関係の反射・推移閉包
Xを集合だとします。いま、X={1, 2, 3}って例で考えましょう。Xのメンバーをペアにしたタプル(1, 3)、(2, 2)などの全体はX×X = X2と書きます。X2の部分集合をX上の関係（正確には二項関係）と呼びます。
例えば、{(1, 2), (1, 3), (2, 3)}は関係です。これは、x, y ∈X に関して x < y という関係式を満たす(x, y)です。「関係（条件）を満たす全体」を関係そのものとみなすわけ。
- 関係Rが反射的とは： 任意のx∈Xに対して、(x, x)∈R
- 関係Rが推移的とは： 任意のx, y, z∈Xに対して、(x, y)∈R かつ (y, z)∈R なら (x, z)∈R
例：{(1, 1), (2, 2), (3, 3)}は反射的、{(1, 2), (1, 3), (2, 3)}は推移的。(x, y)∈Rを、例えば「xとyは友達」と解釈してみると、反射的＝「自分は友達」、推移的＝「友達の友達はまた友達」。ついでにいうと、「(x, y)∈R なら (y, x)∈R」なら対称的というのですが、恋人関係とかではいつでも対称的とはいきませんね。
関係Rの“二乗”RR = R2を、「(x, y)∈R2 ⇔ (x, t)∈R, (t, y)∈Rとなるtがある」と定義します。また友達の例で説明すると、Rが「直接の友達」（ただし、対称的とか限らない）を表しているとして、R2は、「あいだに1人を介しての間接的友達」関係を表します。
同様に、(RR)R = R(RR) = R3 は、「あいだに2人を介しての間接的友達」関係を意味します。Rnなら「あいだに(n - 1)人を介しての間接的友達」関係。そして R0 = I は{(1, 1), (2, 2), (3, 3)}のことだと約束します。IはX×Xの対角線のように見えるので対角集合とも呼び、イコール関係を表現します。
さて、直接の友達関係Rから出発して、関係を拡大していきましょう：
- I ∪ R -- 自分も友達とみなす
- I ∪ R ∪ R2 -- あいだに1人を介する間接的友達も友達とみなす
- I ∪ R ∪ R2 ∪ R3 -- あいだに2人を介する間接的友達も友達とみなす
- ……（以下同様）
（R = {(1, 2), (2, 3)}として、上の手順を実行してみると実感が湧くと思うよ。）
1番目の手順で反射的となり、どんどん間接的友達を加えていくと、推移的となります。結局、I ∪ R ∪ R2 ∪ R3 ∪ ... は、もとの直接的関係Rから“友達の輪”方式で作った「反射的かつ推移的な関係」となります。これを、Rの反射・推移閉包（reflexive-transitive closure）と呼びます。
そう、関係の反射・推移閉包は、あの形の級数の三番目の事例ですね。
| 演算の概念 | 関係 |
|---|---|
| 掛け算 | 関係の結合（合成） |
| 足し算 | 合併（ユニオン） |
| 単位 | 対角集合（イコール関係） |
| 零 | 空集合 |
まだあるぞ
X上の関係は、Xを頂点とする単純有向グラフ*1で図形的に表現できます。グラフGに対してGnは、長さnの経路（パス）で繋げる頂点を直結（バイパス）したグラフです。あの形の級数は、できるかぎりバイパスしまくった（が、もとの辺も残した）グラフを表します。
単純有向グラフは、{0, 1}（ブール値false, true）成分の行列で表現できて、“関係の計算／グラフの計算”を、行列計算に還元できます。もちろんあの形の級数を行列で作ることもできます。行列成分を{0, 1}から整数や実数にすると、級数は（値としては）発散することがあるのだけど、それでも無意味ではなくて、有意義な情報を持っています。
最後のほうはちゃんと説明しなかったけど、なんか面白い感じはするでしょ。
*1:2つの頂点を結ぶ有向辺がたかだか1つ、ただし自分に戻るループは認める
