Computability

释义 Definition

可计算性：指一个问题或函数能否在有限步骤内由某种形式化的计算过程（如算法、图灵机）求解的性质。常用于理论计算机科学与数理逻辑中。（另有相关方向如“可判定性/不可判定性”）

发音 Pronunciation (IPA)

/kəmˌpjuːtəˈbɪləti/

词源 Etymology

由 compute（计算）+ -ability（……的能力/性质）构成，表示“能被计算/可计算的性质”。compute 源自拉丁语 computare，意为“计算、估算”（com- “一起” + putare “思量、估计”）。

例句 Examples

Computability studies what problems computers can solve in principle.
可计算性研究计算机在原理上能够解决哪些问题。

The computability of a function may depend on the formal model of computation you choose, such as a Turing machine.
一个函数的可计算性可能取决于你选择的形式化计算模型，例如图灵机。

相关词 Related Words

• Algorithm
• Decidability
• Undecidable
• Turing
• Recursion
• Complexity
• Halting
• Computable

文学与经典著作 Literary Works

• Introduction to the Theory of Computation（Michael Sipser）——讨论可计算性、可判定性与复杂性基础。
• Computability and Logic（George S. Boolos, John P. Burgess, Richard C. Jeffrey）——从逻辑视角系统讲解可计算性理论。
• Computability: An Introduction to Recursive Function Theory（Nigel Cutland）——以递归函数理论为线索介绍可计算性。
• Gödel, Escher, Bach: An Eternal Golden Braid（Douglas Hofstadter）——在跨学科叙述中多次涉及可计算性与图灵思想。