Loading article…
コンピュータ科学やコンピュータプログラミングにおいて、非決定性アルゴリズムとは、決定性アルゴリズムとは対照的に、同じ入力であっても実行ごとに異なる動作を示す可能性のあるアルゴリズムのことである。
計算モデルが異なると、アルゴリズムが非決定論的になる理由も異なり、その性能や正しさを評価する方法も異なる。
コンピュータ科学で非決定性の概念が形式化される以前から、ランダム性を用いた明示的なアルゴリズムが検討されていました。1917年、ヘンリー・C・ポックリントンは、素数を法とする平方根を効率的に求めるためのポックリントンのアルゴリズムとして知られるランダム化アルゴリズムを発表しました。 [ 1 ] 1930年代、エンリコ・フェルミは中性子拡散の研究中にモンテカルロ法を実験しましたが、この研究は発表しませんでした。[ 2 ] 1940年代と50年代にロスアラモス国立研究所の科学者たちは、モンテカルロアルゴリズムに関する最初の出版物につながる概念を開発し、実装しました。[ 3 ] [ 4 ]
マイケル・O・ラビンとダナ・スコットは1959年に非決定性有限オートマトン（NFA）を導入し、形式化しました。[ 5 ]その論文で彼らは、言語を認識する能力に関して、決定性有限オートマトン（DFA）との等価性を示しました。また、チューリングマシン（TM）にも適用し、非決定性チューリングマシン（NTM）を導入しました。NFAを使用することで、スティーブン・C・クリーネらが以前に確立した正規言語の特定の閉包特性をより効率的な方法で再証明することができました。
非決定性アルゴリズムという用語は、ロバート・W・フロイドによって1967年には既に使用されていました。[ 6 ]この論文ではフローチャート のグラフィカル言語が使用されていますが、これはオートマタやチューリングマシンとは異なるアルゴリズムの形式化方法であり、当時は電子計算機でのプログラミングの実践により近いものでした。
哲学において、決定論と自由意志をめぐる議論は、少なくとも古代ギリシャにまで遡ります。コンピュータ科学における非決定性という概念は、各計算ステップにおいて、事前に明示的に定義された、多くの場合有限個の選択肢の中から比較的限定された選択を行うことを指すのに対し、哲学においては、可能な選択肢は必ずしも事前に明示されたり、形式的に定義されたりする必要はないという点に注目すべきです。特に、この追加的な特性ゆえに、コンピュータ科学における非決定論は、伝統的な哲学における非決定論と比較して、新たな発展と言えるでしょう。