決定不能問題
Undecidable problem
☆
計算可能性理論および計算複雑性理論において、決定不能問題とは、常に正しい「はい」または「いいえ」の答えを導くアルゴリズムを構築することが不可能で
あることが証明された決定問題である。停止問題は、その一例である。任意のプログラムが実行された際に、最終的に停止するかどうかを正確に判断するアルゴ
リズムは存在しないことが証明されている。[1]）
| In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.[1] | 計算可能性理論および計算複雑性理論において、決定不能問題とは、常に
正しい「はい」または「いいえ」の答えを導くアルゴリズムを構築することが不可能であることが証明された決定問題である。停止問題は、その一例である。任
意のプログラムが実行された際に、最終的に停止するかどうかを正確に判断するアルゴリズムは存在しないことが証明されている。[1] |
| Background A decision problem is a question which, for every input in some infinite set of inputs, requires a "yes" or "no" answer.[2] Those inputs can be numbers (for example, the decision problem "is the input a prime number?") or values of some other kind, such as strings of a formal language. The formal representation of a decision problem is a subset of the natural numbers. For decision problems on natural numbers, the set consists of those numbers that the decision problem answers "yes" to. For example, the decision problem "is the input even?" is formalized as the set of even numbers. A decision problem whose input consists of strings or more complex values is formalized as the set of numbers that, via a specific Gödel numbering, correspond to inputs that satisfy the decision problem's criteria. A decision problem A is called decidable or effectively solvable if the formalized set of A is a recursive set. Otherwise, A is called undecidable. A problem is called partially decidable, semi-decidable, solvable, or provable if A is a recursively enumerable set.[nb 1] |
背景 決定問題とは、ある無限の入力集合のすべての入力に対して、「はい」または「いいえ」の答えを必要とする質問である。[2] それらの入力は、数値（例えば、「入力は素数か？」という決定問題）や、形式言語の文字列など、他の種類の値である可能性がある。 決定問題の形式表現は、自然数の部分集合である。自然数に関する決定問題の場合、その集合は決定問題が「はい」と答える数で構成される。例えば、「入力は 偶数か？」という決定問題は、偶数の集合として形式化される。入力が文字列やより複雑な値で構成される決定問題は、特定のゲーデル番号付けにより、決定問 題の基準を満たす入力に対応する数値の集合として形式化される。 決定問題Aは、Aの形式化された集合が再帰集合である場合、決定可能または事実上解けると呼ばれる。そうでない場合、Aは決定不能と呼ばれる。問題は、Aが再帰的に列挙可能な集合である場合、部分的に決定可能、半決定可能、解ける、または証明可能と呼ばれる。[注釈 1] |
| Example: the halting problem in computability theory In computability theory, the halting problem is a decision problem which can be stated as follows: Given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever. Alan Turing proved in 1936 that a general algorithm running on a Turing machine that solves the halting problem for all possible program-input pairs necessarily cannot exist. Hence, the halting problem is undecidable for Turing machines. |
例：計算可能性理論における停止問題 計算可能性理論において、停止問題とは次のように定義される決定問題である。 任意のプログラムの記述と有限の入力が与えられた場合、そのプログラムが実行を終了するのか、それとも永久に実行し続けるのかを決定する。 アラン・チューリングは1936年に、チューリングマシン上で実行される一般的なアルゴリズムでは、すべての可能なプログラムと入力の組み合わせに対して 停止問題を解決することは不可能であることを証明した。したがって、停止問題はチューリングマシンでは決定不可能である。 |
| Relationship with Gödel's incompleteness theorem This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. (August 2019) (Learn how and when to remove this message) The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that an axiomatization of the natural numbers that is both complete and sound is impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers. Since soundness implies consistency, this weaker form can be seen as a corollary of the strong form. It is important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the truth value of a statement, but only concerns the issue of whether it is possible to find it through a mathematical proof. The weaker form of the theorem can be proved from the undecidability of the halting problem as follows.[3] Assume that we have a sound (and hence consistent) and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. We know that this statement can be expressed with a first-order logic statement, say H(a, i). Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n′ such that N(n′) = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt, and furthermore, the answer it gives us will be true (by soundness). This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false. |
ゲーデルの不完全性定理との関係 この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 この節に参考文献や出典を追加して記事の信頼性向上にご協力ください。 出典が示されていない記事は、削除される場合があります。 (2019年8月) (Learn how and when to remove this message) ゲーデルの不完全性定理によって提起された概念は、停止問題によって提起された概念と非常に似ており、証明も非常に類似している。実際、不完全性定理の弱 い形は、停止問題の決定不能性の容易な帰結である。この弱い形は、自然数に関する完全かつ健全な公理化は不可能であると主張することで、不完全性定理の標 準的な表現とは異なる。「健全」という部分が弱まっている。つまり、問題となっている公理系が証明すべきは、自然数に関する真の命題のみであることを意味 する。完全性は一貫性を意味するため、この弱まった形は強まった形の帰結と見なすことができる。 重要なのは、ゲーデルの第一不完全性定理の標準形の主張は、命題の真偽とはまったく関係なく、数学的証明によって命題を見つけられるかどうかという問題の みに関係しているということである。 この定理の弱い形式は、停止問題の決定不能性から以下のように証明できる。[3] 自然数に関するすべての真の第一階論理命題の健全な（したがって矛盾のない）完全な公理化が存在すると仮定する。 そうすると、これらの命題をすべて列挙するアルゴリズムを構築できる。つまり、自然数 n が与えられた場合、自然数に関する真の第一階論理式を計算するアルゴリズム N(n) が存在し、すべての真の命題に対して、N(n) がその命題を導くような n が少なくとも1つ存在するということである。ここで、表現 a を持つアルゴリズムが入力 i で停止するかどうかを判断したいと仮定しよう。この命題は、第一階論理式、例えば H(a, i) で表現できることが分かっている。公理化が完全であるため、N(n) = H(a, i) を満たすnが存在するか、またはN(n′) = ¬ H(a, i) を満たすn′が存在することになる。したがって、H(a, i) またはその否定が見つかるまで、すべての n を繰り返し処理すれば、常に停止し、さらに、その答えは真となる（妥当性により）。これは、停止問題を決定するアルゴリズムが得られることを意味する。そ のようなアルゴリズムは存在し得ないことが分かっているため、自然数に関するすべての真の第一階論理文の一貫した完全な公理化が存在するという仮定は誤り であることが分かる。 |
| Examples of undecidable problems Main article: List of undecidable problems Undecidable problems can be related to different topics, such as logic, abstract machines or topology. Since there are uncountably many undecidable problems,[nb 2] any list, even one of infinite length, is necessarily incomplete. |
決定不能問題の例 詳細は「決定不能問題の一覧」を参照 決定不能問題は、論理、抽象機械、トポロジーなど、異なるトピックに関連している可能性がある。決定不能問題は無数に存在するため、[nb 2] どのようなリストも、たとえそれが無限の長さであっても、必然的に不完全なものとなる。 |
| Examples of undecidable statements See also: List of statements independent of ZFC and Independence (mathematical logic) There are two distinct senses of the word "undecidable" in contemporary use. The first of these is the sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent, effective formal system which proves for every question A in the problem either "the answer to A is yes" or "the answer to A is no". Because of the two meanings of the word undecidable, the term independent is sometimes used instead of undecidable for the "neither provable nor refutable" sense. The usage of "independent" is also ambiguous, however. It can mean just "not provable", leaving open whether an independent statement might be refuted. Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the truth value of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various philosophical schools. One of the first problems suspected to be undecidable, in the second sense of the term, was the word problem for groups, first posed by Max Dehn in 1911, which asks if there is a finitely presented group for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1955.[4] The combined work of Gödel and Paul Cohen has given two concrete examples of undecidable statements (in the first sense of the term): The continuum hypothesis can neither be proved nor refuted in ZFC (the standard axiomatization of set theory), and the axiom of choice can neither be proved nor refuted in ZF (which is all the ZFC axioms except the axiom of choice). These results do not require the incompleteness theorem. Gödel proved in 1940 that neither of these statements could be disproved in ZF or ZFC set theory. In the 1960s, Cohen proved that neither is provable from ZF, and the continuum hypothesis cannot be proven from ZFC. In 1970, Russian mathematician Yuri Matiyasevich showed that Hilbert's Tenth Problem, posed in 1900 as a challenge to the next century of mathematicians, cannot be solved. Hilbert's challenge sought an algorithm which finds all solutions of a Diophantine equation. A Diophantine equation is a more general case of Fermat's Last Theorem; we seek the integer roots of a polynomial in any number of variables with integer coefficients. Since we have only one equation but n variables, infinitely many solutions exist (and are easy to find) in the complex plane; however, the problem becomes impossible if solutions are constrained to integer values only. Matiyasevich showed this problem to be unsolvable by mapping a Diophantine equation to a recursively enumerable set and invoking Gödel's Incompleteness Theorem.[5] In 1936, Alan Turing proved that the halting problem—the question of whether or not a Turing machine halts on a given program—is undecidable, in the second sense of the term. This result was later generalized by Rice's theorem. In 1973, Saharon Shelah showed the Whitehead problem in group theory is undecidable, in the first sense of the term, in standard set theory.[6] In 1977, Paris and Harrington proved that the Paris-Harrington principle, a version of the Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of second-order arithmetic. Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism. Goodstein's theorem is a statement about the Ramsey theory of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic. Gregory Chaitin produced undecidable statements in algorithmic information theory and proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound c such that no specific number can be proven in that theory to have Kolmogorov complexity greater than c. While Gödel's theorem is related to the liar paradox, Chaitin's result is related to Berry's paradox. In 2007, researchers Kurtz and Simon, building on earlier work by J.H. Conway in the 1970s, proved that a natural generalization of the Collatz problem is undecidable.[7] In 2019, Ben-David and colleagues constructed an example of a learning model (named EMX), and showed a family of functions whose learnability in EMX is undecidable in standard set theory.[8][9] |
決定不能な命題の例 参照：ZFCに依存しない命題のリスト、独立（数学的論理学） 現代の用法では、「決定不能」という語には2つの異なる意味がある。その1つ目は、ゲーデルの定理に関連して用いられる意味であり、特定の演繹体系におい て証明も反証もできない命題という意味である。2つ目の意味は、計算可能性理論に関連して用いられ、命題ではなく決定問題に適用される。決定問題とは、そ れぞれ「はい」または「いいえ」で答えられる質問の可算無限集合である。そのような問題は、問題セット内のすべての質問に正確に回答する計算可能な関数が 存在しない場合、決定不能であると言われる。この2つの関係は、決定問題が決定不能である場合（再帰理論的な意味において）、問題内のすべての質問Aに対 して「Aの回答はイエスである」または「Aの回答はノーである」と証明する一貫性のある効果的な公式システムは存在しないということである。 「決定不能」という言葉には2つの意味があるため、「証明も反証も不可能」という意味で「独立」という用語が「決定不能」の代わりに使用されることもあ る。しかし、「独立」という用語の使用もまた曖昧である。「独立」という用語は「証明不可能」という意味に過ぎず、「独立」な命題が反証可能かどうかは不 明である。 ある演繹システムにおける命題の決定不能性は、それ自体では、その命題の真偽値が明確に定義されているか、あるいは他の手段によって決定できるかという問 題には対応しない。決定不能性は、考慮されている特定の演繹システムがその文の真偽を証明できないことを意味するだけである。真偽が決して知ることができ ない、あるいは不適切に指定されている、いわゆる「絶対に決定不能な」文が存在するかどうかは、さまざまな哲学派の間で論争の的となっている。 この言葉の2つ目の意味で決定不能であると疑われた最初の問題の1つは、1911年にマックス・デーンが最初に提起した「2つの語が等価であるかどうかを 決定するアルゴリズムが存在しない有限生成群が存在するか」というグループの語の問題であった。これは1955年にその通りであることが示された。[4] ゲーデルとポール・コーエンの共同研究により、決定不能な命題（この用語の最初の意味）の2つの具体的な例が示された。すなわち、連続体仮説はZFC（集 合論の標準的な公理化）では証明も反証もできない。また、選択公理はZF（選択公理を除くZFCの公理のすべて）では証明も反証もできない。これらの結果 は不完全性定理を必要としない。ゲーデルは1940年に、ZFまたはZFC集合論において、これらのいずれの主張も反証できないことを証明した。1960 年代には、コーエンがZFからいずれも証明できないこと、および連続体仮説はZFCから証明できないことを証明した。 1970年には、ロシア人数学者のユーリ・マティヤセヴィチが、1900年に次世紀の数学者たちへの挑戦として提起されたヒルベルトの第10問題は解決不可能であることを示した。ヒルベルトの課題は、ディオファントス方程式の すべての解を求めるアルゴリズムを求めていた。ディオファントス方程式はフェルマーの最終定理のより一般的なケースであり、整数係数の多変数多項式の整数 根を求めるものである。方程式は1つだけだが変数はn個あるため、複素平面上には無限に多くの解が存在する（そして、見つけるのは簡単である）。しかし、 解が整数値のみに限定されると、問題は不可能になる。マティヤセヴィッチは、ディオファントス方程式を再帰的に列挙可能な集合に写像し、ゲーデルの不完全 性定理を適用することで、この問題が解けないことを示した。[5] 1936年、アラン・チューリングは、チューリングマシンが与えられたプログラムで停止するかどうかという停止問題は、その用語の第二の意味において決定不能であることを証明した。この結果は後にライスの定理によって一般化された。 1973年、サハロン・シェラは、標準集合論において、グループ論におけるホワイトヘッド問題は、その用語の第一の意味において決定不能であることを示した。 1977年、パリとハリントンは、ラムゼイの定理の1つのバージョンであるパリ＝ハリントンの原理は、ペアノの公理で与えられる算術の公理化では決定不能であるが、2次算術のより大きな体系では真であることが証明できることを証明した。 クルスカルの木の定理は、コンピュータ科学への応用があるが、ペアノの公理からは決定不能であるが、集合論では証明可能である。実際、クルスカルの木の定 理（またはその有限形）は、数学の哲学である「predicativism」と呼ばれる原則を基礎とする、より強力な体系では決定不能である。 グッドスタインの定理は、自然数に関するラムゼイ理論に関するもので、カービーとパリスが、それはペヤノ算術では決定不能であることを示した。 グレゴリー・チャイティンは、アルゴリズム情報理論における決定不能な命題を導き出し、その設定における不完全性定理を証明した。チャイティンの定理は、 十分な算術を表現できる理論であれば、その理論において、コルモゴロフ複雑度がcより大きいことを証明できる特定の数値は存在しないという上限cが存在す ることを述べている。ゲーデルの定理は「嘘つきのパラドックス」に関連しているが、チャイティンの結果は「ベリーのパラドックス」に関連している。 2007年、クルツとサイモンという研究者は、1970年代のJ.H.コンウェイの先行研究を基に、コラッツ問題の自然な一般化は決定不能であることを証明した。[7] 2019年、ベン＝デイビッドとその同僚は学習モデル（EMXと名付けられた）の例を構築し、EMXにおける学習可能性が標準的集合論では決定不能である関数族を示した。[8][9] |
| Decidability (logic) Entscheidungsproblem Proof of impossibility Unknowability Wicked problem |
決定可能性（論理） 決定問題 不可能の証明 不可知 厄介な問題 |
| https://en.wikipedia.org/wiki/Undecidable_problem | |
リ ンク
文 献
そ の他の情報
Copyleft, CC, Mitzub'ixi Quq Chi'j, 1996-2099
☆
☆