計算可能性と決定可能性

計算可能性理論は、アルゴリズムによる問題解決の根本的な限界を研究し、効果的な手続きによって解決できる問題と、いかなるアルゴリズムも決定できない問題との境界を画定するものです。

Definition

計算可能性理論とは、どの関数や決定問題が効果的な手続きによって計算可能であるかを研究する学問分野です。ある問題が決定可能であるとは、あるアルゴリズムが常に正しい「はい」または「いいえ」の答えを出して停止する場合を指し、そのようなアルゴリズムが存在しない場合は決定不能であるとされます。

Scope

この分野は、チューリングマシンなどの効果的な計算の形式モデル、これらのモデルとアルゴリズムの直感的な概念を同一視するチャーチ＝チューリングの提唱、停止問題を含む決定不能な問題の存在、問題間の非可解性を転送するために使用される還元、および計算可能な範囲を超えて問題を分類する非可解性の次数構造を扱います。

Sub-topics

• Reducibility and Degrees of Unsolvability
• The Church–Turing Thesis
• Turing Machines
• Undecidability and the Halting Problem

Core questions

• ある問題がアルゴリズムによって解決可能であるとは、何を意味するのでしょうか？
• いかなるアルゴリズムも決して解決できない、明確に定義された問題は存在するのでしょうか？
• ある問題の非可解性を、別の問題の非可解性を証明するためにどのように利用できるのでしょうか？
• 非可解な問題は、その相対的な困難さによってどのように分類されるのでしょうか？

Key theories

チューリングの計算モデル

チューリングの抽象機械は、効果的な手続きの概念を形式化し、停止問題や一階述語論理の決定問題が解決不能であることを証明するために使用され、計算における内在的な限界を確立しました。

決定不能な問題の存在

対角線論法により、最も有名な停止問題をはじめとして、いかなるアルゴリズムも決定できない問題が存在します。したがって、決定不能性は単なる珍奇な現象ではなく、遍在する構造的特徴であると言えます。

計算モデルの等価性

チューリングマシン、ラムダ計算、および再帰関数は、まったく同じクラスの計算可能関数を定義します。この収束がチャーチ＝チューリングの提唱を裏付けています。

Clinical relevance

決定不能性の結果は、ソフトウェアツールが保証できることに対して厳しい限界を設定します。任意のプログラムが停止するか、正しいか、特定のバグがないかを決定できる一般的なアルゴリズムは存在しません。このため、検証ツールは完全な自動解析ではなく、近似、制限された言語、および人間のガイダンスに依存しています。

History

ヒルベルトの決定問題に触発され、チャーチとチューリングは1936年に独立して、いかなるアルゴリズムも一階述語論理のすべてを決定できないことを示しました。チューリングの機械モデルとチャーチのラムダ計算は同等であることが証明されました。ポストとクリーネは、その後の数十年で理論を非可解性の次数の研究へと拡張しました。

Key figures

• Alan Turing
• Alonzo Church
• Kurt Gödel
• Emil Post

Seminal works

• turing1937
• church1936
• sipser2013

Frequently asked questions

決定可能と決定不能の違いは何ですか？

ある問題が決定可能であるとは、すべての入力に対して常に停止し、正しい「はい」または「いいえ」の答えを出すアルゴリズムが存在する場合を指します。停止問題で証明されているように、そのようなアルゴリズムが存在し得ない場合は決定不能です。決定不能な問題であっても、認識可能である場合があります。これは、アルゴリズムが「はい」のインスタンスを確認できるものの、「いいえ」のインスタンスに対しては永遠に実行され続ける可能性があることを意味します。

決定不能性とは、これらの問題が決して解決できないことを意味するのでしょうか？

それは、単一のアルゴリズムがすべてのインスタンスを正しく解決するわけではないことを意味します。実際には、ツールは制限されたケースを扱い、近似的または保守的な答えを提供したり、多くのインスタンスを解決する一方で、時折失敗したり助けを求めたりします。したがって、決定不能性は、すべての進歩を禁じるというよりも、問題への取り組み方を形成するものです。