最終更新日：2025/11/21

undecidable

形容詞

比較不可

(mathematics, computing theory) Incapable of being algorithmically decided in finite time. For example, a set of strings is undecidable if it is impossible to program a computer (even one with infinite memory) to determine whether or not specified strings are included.

日本語の意味

数学や計算理論において、有限な時間内でアルゴリズムによって解決（決定）できない性質を持つこと。 / 有限のステップで正確な判断や決定が不可能な問題や集合に対して用いられる。

このボタンはなに？

The halting problem is a classic example of an undecidable decision problem in computability theory.

Google翻訳 / DeepL翻訳

停止問題は計算理論における、有限時間でいかなるアルゴリズムでも判定できない決定問題の代表的な例です。

詳細

意味（1）

The first-order procedure SP differs from the proposi-

tional procedure CP°₁ in an essential feature. Namely, CP°₁

always terminates while SP may run forever as we have seen with

the example immediately after (3.7). This is not a specific

defect of SP. Rather it is known that first-order logic is an

undecidable theory while propositional logic is a decidable

theory. This means that for the latter there are decision pro-

cedures which for any formula decide whether it is valid or

not — and CP°₁ in fact is such a decision procedure — while

for the former such decision procedures do not exist in princi-

ple. Thus SP, according to these results for which the reader

is referred to any logic texts such as [End], [DrG] or [Lew],

is of the kind which we may expect, it is a semi-decision

procedure which confirms if a formula is valid but may run

forever for invalid formulas. Therefore, termination by running

out of time or space after any finite number of steps will

leave the question for the validity of a formula unsettled. …

Google翻訳 / DeepL翻訳

詳細

意味（2）

(mathematics) (of a WFF) logically independent from the axioms of a given theory; i.e., that it can never be either proved or disproved (i.e., have its negation proved) on the basis of the axioms of the given theory. (Note: this latter definition is independent of any time bounds or computability issues, i.e., more Platonic.)