Uncomputable

释义 Definition

不可计算的；不可由算法在有限步骤内求解的。常用于计算机科学与数学（如可计算性理论）中，描述某些问题或函数不存在任何程序能对所有输入都保证在有限时间内给出正确结果。（也可引申为“无法用计算方法解决的”。）

发音 Pronunciation (IPA)

/n.kmpju.t.bl/

例句 Examples

An uncomputable problem cannot be solved by any algorithm.
不可计算的问题无法被任何算法解决。

Even with unlimited memory, the halting problem is uncomputable for all possible programs.
即使拥有无限内存，停机问题对所有可能的程序而言仍是不可计算的。

词源 Etymology

由前缀 **un-**（表示否定，“不”）+ computable（“可计算的”）构成；而 computable 来自 compute（计算），其词根与拉丁语 computare（合计、计算）相关。整体字面意思即“不可被计算的”。

相关词 Related Words

• Algorithmic
• Computable
• Decidable
• Incomputable
• Recursive
• Turing
• Undecidable
• Unsolvable

文学与著作中的用例 Literary Works

• Stephen Hawking, A Brief History of Time（《时间简史》）在讨论科学理论边界与可预测性时，常与“可计算/不可计算”的思想相联系。
• Douglas Hofstadter, Gdel, Escher, Bach: An Eternal Golden Braid（《哥德尔、艾舍尔、巴赫》）涉及可计算性、停机问题等主题，“uncomputable”在相关讨论中常出现。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”（1936）可计算性理论奠基论文，虽核心术语多为 computable，但对“不可计算”概念的界定与讨论贯穿其中。