「状態遷移機械と非決定性遷移」における「遷移先は未定義」に対する注釈で：
実は、「未定義」の定義が問題になるのですが、いまは触れません。
と書きました。このエントリーで「未定義」に関してちょっと考えてみます。
次の3つの考え方を紹介しましょう。
- 未定義っていってんだから、そりゃ未定義なんだよ。
- 未定義は、エラーだろうよ。
- 未定義ってのは、なんでもいいってことじゃねっ。
実例
「状態遷移機械と非決定性遷移」で出したカウンターを実例に使いましょう。状態空間はN = {0, 1, 2, 3, ...}*1、アルファベットは{up, down, reset}です。
up, down, resetの各記号で表現される遷移は決定性です。つまり、遷移先が一意的に決まっています。ただし、状態点0におけるdownの遷移先は未定義としましょう。
未定義は未定義
決定性で完全に定義された遷移は、状態空間から状態空間への関数（写像）として解釈できます。カウンターの例では、up, down, resetのそれぞれが、N→N という関数と思っていいわけです。例えば：
- up = λn.(n + 1)
ですね（記号λについては、「JavaScriptで学ぶ・プログラマのためのラムダ計算」を参照）。
downも λn.(n - 1) と書けますが、n = 0 のところが未定義なのです。一部分が未定義な関数は部分関数（partial function）と呼びます。部分関数は、普通の関数（特に全域関数とも呼ぶ）を使って次のように定義されます。
- 集合Xから集合Yへの部分関数とは、Xの部分集合Dと、普通の関数f:D→Yの組み合わせである。
つまり、fが「XからYへの部分関数」だとは、なんか適当なD⊆Xがあって、f:D→Y は完全に定義されていることです。downの例では、D = {n∈N| n > 0} であり、f = λn.(n - 1) は、D→N という関数になっています。
「未定義」概念を素直に解釈すると、部分関数による定式化になるのは自然なことだと思います。
未定義はエラー
「未定義」を部分関数で解釈するのは、しごくまっとうな方法で、文句の付けようはないのですが、downをプログラムで実装する立場になると、downに引数0が渡されたときどうすりゃいいんだよ？ と疑問になります。
ひとつの対処法はこんなふうでしょう。
function down(n) {
if (n < 1) throw "Argument must be positive.";
return (n -1);
}
JavaScriptでは、そもそもnが整数であることも保証されませんが、大目に見てください。
通常、例外は値とはみなされませんが、ここでは特殊な値と考えましょう。自然数（0を含む）とエラー（例外）を表す値errorを一緒にした集合は N∪{error} = {0, 1, 2, 3, ..., error} となります。そして、down:N∪{error} → N∪{error} を次のように定義します。
- n = 0 のときは、down(n) = down(0) = error
- n = error のときは、down(n) = down(error) = error
- それ以外のときは、down(n) = n - 1
これもまた、「未定義」の解釈のひとつです。
未定義はなんでもいい
いま、「n > 0 なら down(n) = n - 1」という仕様が与えられ、n = 0 については何も言及されてないとします。言及されてないのですから未定義です。そのとき、down(0) はエラーにしないとまずいのでしょうか？
言及されてないとは「エラーにしろ」とも指示されてないことです。例えば down(0) = 0 とか down(0) = 39 とかしても文句は言えないはずです（文句を言うなら最初から仕様に書いておけ！）。
この場合、「未定義とは実装者がどうしようと勝手」ということですね。この種の未定義を定式化するには、非決定性の遷移を使います。n = 0 での遷移先、つまり down(0)の値を“最大限に非決定的”にしておきます。最大限に非決定的とは、許容できる値の範囲をN全体としておくことです。
最大限の非決定性を使う定式化はあまり知られてないようですが、一番自然であることもけっこう多いのです。考慮してみる価値はありますよ。
