計算科学において、非決定性写像は矢鱈に役に立ちます。僕は、「非決定性写像に足を向けて寝られない」と思っているのですが、実際のところ、非決定性写像・様がどっちの方角にいらっしゃるか分からないので、寝る向きに気をつけているわけじゃないです。
fが集合AとBのあいだの非決定性写像だとは、Pow(B) をBのベキ集合だとして、fが A→Pow(B) という（普通の意味の）写像であることです。また、非決定性写像は A×B の部分集合として捉えることもできます。F⊆(A×B) と表現した非決定性写像は、通常「関係」と呼びますけどね。
f:A→Pow(B) と F⊆(A×B) が同値（事実上同じ）ことは、次のように記述できます。
- b∈f(a) ⇔ (a, b)∈F
単に気分の問題とも言えますが、f:A→Pow(B) だと方向性があり動的なイメージがあります。それに対して、F⊆(A×B) は静的な記述のような雰囲気。
f:A→Pow(B) にも2つの解釈があるように思えます。非決定性（不定性）を時間方向で考えるか、空間方向で考えるかの違いです。これは、現実のモデルとして非決定性写像を使うときはけっこう重要な違いになると思います。
fが非決定性写像のとき、f(a) にはたくさんの値が含まれることがあります（まったく値が含まれないこともあります）。この「たくさんの値」の解釈ですが：
- 実際には f(a) としてただ1つの値を返すが、いつも同じ値ではなくて、実行のたびに値が変わるかもしれない。実行を何度も何度も繰り返して記録を取ると、全体として集合となる。壁に向けてピストルを何度も撃って、終わった後で壁の弾痕を見るようなものです。
- f(a) はホントに集合である。1回実行すると集合が値となる。いつも同じ値を返すが、その値が集合である。壁に向けて散弾銃を一発撃って、その弾痕を見るようなものです。
最初の解釈では、時間方向のバラツキにより集合が形成されます。二番目の解釈は一気に空間方向の広がりとして集合が得られます。形式的な定義 f:A→Pow(B) はどちらの解釈も許し、どちらかを強制するものではありません。しかし、現実との兼ね合いでは、この2つの解釈は全然違います。
僕の個人的な経験では、「一回の実行は単一値を返すが、その値が確定的に予測できない」状況で非決定性写像を使うことが多かったです。ホントの集合がポンと返されるケースは少ないですね。でも、まったく使わないわけじゃないですよ。例えば、戻り値がリストのとき、それを項目値の集合と思えば、ホントの集合を返すケースです。
リストの例は分かりやすいのですが、次のような例では「集合が返されている」ことが意識されにくいかもしれません； fの値は2つの数 a, b のペア (a, b) です（a≦b としましょう）。この数値のペアは、スライダーUIの下限値と上限値を与えます。この例では、(a, b) が {x| a≦x≦b} という集合を表現しています。xが整数値に限るなら、許容できる整数を列挙したリストでもいいので、はっきりと集合だと分かります。集合の記述には、外延的記法と内包的記法があるのでした。
まとめると、次のようなケースで非決定性写像＝関係が使われます。
- 2つの値の関係を静的に記述するとき
- 時間的にバラツキがある値（の系列）を記述するとき
- ホントの集合を結果として一度に返すとき
