アルゴリズム的に非可解な問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/12 02:07 UTC 版)
「数理論理学」の記事における「アルゴリズム的に非可解な問題」の解説
再帰理論の重要な部分領域ではアルゴリズム的に非可解な問題が研究される；決定問題または関数問題がアルゴリズム的に非可解（英: algorithmically unsolvable）あるいは決定不可能（英: undecidable）とは、任意の合法な入力に対して正しい解を返すような計算可能なアルゴリズムが存在しないことをいう。決定不可能性に関する最初の結果は、1936年にチャーチとチューリングによって独立に得られたもので、一階述語論理の決定問題がアルゴリズム的に非可解であるというものである。チュ―リングはこれを停止性問題の決定不可能性を示すことによって証明した。この結果は再帰理論と計算機科学の双方に広範な示唆を与えるものである。 通常の数学においても多くの決定不可能問題の例が知られている。群の語の問題は1955年のピョートル・ノビコフと1959年のW.ボーンによって独立に証明せられた。ビジービーバー問題は1962年にTibor Radóによって与えられた別のよく知られた例である。 ヒルベルトの第10問題は多変数整数係数代数方程式（ディオファントス方程式）が整数解を持つか否かを決定するアルゴリズムの存在を問うものである。部分的な解答はジュリア・ロビンソン、マーティン・デイビス、ヒラリー・パトナムらによって与えられた。この問題のアルゴリズム的非可解性はユーリ・マチャセヴィッチによって1970年に証明された（Davis 1973）。
※この「アルゴリズム的に非可解な問題」の解説は、「数理論理学」の解説の一部です。
「アルゴリズム的に非可解な問題」を含む「数理論理学」の記事については、「数理論理学」の概要を参照ください。
- アルゴリズム的に非可解な問題のページへのリンク
