Decidability

定义 Definition

decidability（可判定性）：在数理逻辑与计算机科学中，指一个问题/命题是否存在总能在有限步骤内给出“是/否”答案的算法。常用于讨论某类问题是否“可由程序完全解决”。（也可泛指“是否可作出明确判断”的性质，但最常见的是技术含义。）

发音 Pronunciation (IPA)

/dɪˌsaɪdəˈbɪləti/

例句 Examples

Decidability is a key topic in theoretical computer science.
可判定性是理论计算机科学中的一个关键主题。

The paper studies the decidability of whether a given formula is satisfiable under certain constraints.
这篇论文研究在特定约束下，判断给定公式是否可满足这一问题的可判定性。

词源 Etymology

来自 decidable（可判定的、可裁决的）+ 名词后缀 -ity（表示“性质、状态”）。decide 源自拉丁语 decidere，本义与“切断、了结”相关，后来引申为“做出决定、判定”。在现代逻辑与计算理论中，“decidable/decidability”专门用来描述“是否存在终止算法”的性质。

相关词 Related Words

• Decidable
• Undecidable
• Computability
• Algorithm
• Turing Machine
• Halting Problem
• Logic
• Satisfiability
• Complexity

文学与著作中的用例 Literary Works

• Michael Sipser, Introduction to the Theory of Computation（讨论可判定性、不可判定性与停机问题等核心概念）
• H. R. Lewis & C. H. Papadimitriou, Elements of the Theory of Computation（系统介绍可判定性与计算理论）
• George S. Boolos, John P. Burgess, Richard C. Jeffrey, Computability and Logic（将逻辑与可计算性联系起来，频繁使用“decidability”）
• Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid（以通俗方式涉及逻辑、形式系统与可判定性/不可判定性的思想）