2815. 非決定性、補足

　連休は日曜大工に手を出してしまい、例の古典幾何学本の翻訳はストップしたままです。リズムをつかめば何とかなりそうですが、きっかけがつかめない。普段は普通に働いていますし。

　ちょっと前にシリーズ化していた非決定性の話。作り方の話になってしまっていて、どこが嬉しいのかは書いていませんでした。まあ、本当は知られていないとまずいと思いますが。
　Wikipediaを見ても、非決定性の状態遷移図は決定性に置き換えることができる、と言う点ばかりが強調されています。効率が全く違います。
　イメージとしては、迷路を抜ける手順で説明すると分かりやすいです。右手法とか左手法、というアルゴリズムがあって、右手で壁を触りながら歩くといつかは迷路を抜けられる、というもの。しかし、その軌跡は行ったり来たりの箇所がいくつもありますし、無駄な手順も含まれます。
　非決定性では、分岐点で正しい方向を全て知っている神が駆け抜けるようなもので、全く無駄がありません。これが非決定性時間の説明です。
　時間方向で無く空間方向、つまりメモリの節約にも非決定性は効用があります。

　このあたり、最初は素朴だったのですけど、いつの間にか過剰分類されたような感じで難解になってしまいました。
　間の悪いことに、実例の説明があまりなくって、実際にプログラミングまでできる人は少数の感じがします。案の定というか、C言語などのプログラミング言語が絡むと、とたんに間違いの記述が目立ちます。