非決定性機械って実在するの?
昨日のエントリでは，「決定性のアルゴリズム」，「非決定性操作」といった表現を選びました．決定性というのは，いつも使っているコンピュータの振る舞いです．
非決定性操作ができる機械があるのか，ですが，授業ではテューリング機械Turing Machine*1を説明して，それから，決定性テューリング機械，非決定性テューリング機械，確率テューリング機械の順に説明しました．
実際のところ，都合のいい答えをすいすいと選んでくれる，非決定性テューリング機械というのはこの世に存在しません．存在していたら，素因数分解でも暗号解読でも，一瞬で…解を生成して，正しいか確認する時間だけあれば…やってくれるのです．
ただし，「非決定性」の振る舞いをする「機械」となると，テューリング機械に限定しません．
具体的には，「有限オートマトン」という機械について，決定性有限オートマトンと，非決定性有限オートマトンを考えることができます．この二つの間では，受理能力は等価であることが証明されています．外形的には，非決定性有限オートマトンの機能限定版が，決定性有限オートマトンです．その一方で，非決定性有限オートマトンが与えられたら，それと等価な決定性有限オートマトンに変換するアルゴリズムが知られています．
実際，grepコマンドや各種プログラミングで使用される「正規表現」の処理をするとき，計算機内部で，与えられた正規表現に対応する非決定性有限オートマトン(のデータ構造)を構成し，次にそれと等価な決定性有限オートマトン(のデータ構造)に変換すればいいわけです．
ところで，決定性有限オートマトンは，deterministic finite automatonの頭文字をとって「DFA」，非決定性有限オートマトンはnondeterministic finite automatonなので「NFA」と呼ばれます．これらについて深く学びたければ，http://www.syuhitu.org/other/rgnor/rgnor.htmlが参考になると思います．
最後に，他にも「決定性」と「非決定性」のものが考えられるんじゃないかとか，どんな機械でも，決定性と非決定性とで能力差はないんじゃないかという疑問も出ると思いますので，答えておきますと，プッシュダウンオートマトンという機械については，決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンとで受理能力が異なります．
