Decidable

释义 Definition

（尤用于逻辑学、数学与计算机科学）可判定的；可决定真假的：指存在一个明确的程序/算法，能在有限步骤内对某类问题给出“是/否”的结论。（也可泛指“可作出决定的”，但学术语境更常见）

发音 Pronunciation (IPA)

/dɪˈsaɪdəbl/

例句 Examples

A decidable problem has an algorithm that always halts with an answer.
可判定问题有一种算法，能够总是停机并给出答案。

In first-order logic, some theories are decidable, while others are not, which shapes what can be automatically proved.
在一阶逻辑中，有些理论是可判定的，而另一些不是；这会影响哪些内容能够被自动证明。

词源 Etymology

decidable 来自动词 decide（决定、裁决）+ 形容词后缀 -able（能够……的），字面意思是“能够被决定的”。在20世纪的逻辑与计算理论中，它逐渐固定为术语，特指“存在算法可在有限时间内判定”的性质。

相关词 Related Words

• Decide
• Decision
• Undecidable
• Decidability
• Computable
• Algorithmic
• Turing
• Halting

文学与作品 Literary Works

• Introduction to the Theory of Computation（Michael Sipser）——在讨论可计算性与形式语言时频繁使用 decidable。
• Computability and Logic（George S. Boolos, John P. Burgess, Richard C. Jeffrey）——系统讲解“可判定/不可判定”与证明理论。
• Undecidable Theories（Alfred Tarski 等相关论文与选集常见标题/主题）——围绕 decidable 的核心对立概念展开。