Noncomputable

Definition / 定义

noncomputable（不可计算的）：指在给定的计算模型（通常是图灵机/算法）下，不存在任何算法能够在有限步骤内对所有输入都正确给出结果的性质或问题。常用于计算理论中（如“不可计算函数”“不可判定问题”）。
（注：在日常语境中较少使用，主要出现在数学与计算机科学理论中。）

Pronunciation / 发音

/ˌnɑːn.kəmˈpjuː.tə.bəl/

Examples / 例句

A noncomputable problem cannot be solved by any algorithm.
不可计算的问题无法用任何算法解决。

Some numbers encode noncomputable information, meaning no program can generate their digits in general.
有些数包含不可计算的信息，这意味着一般而言不存在程序能生成它们的各位数字。

Etymology / 词源

由前缀 non-（表示“非、不”）+ computable（“可计算的”）构成。computable 源自 compute（计算），来自拉丁语 computare（合计、计算）。整体字面义即“不能被计算出来的”。

Related Words / 相关词

• Uncomputable
• Computable
• Undecidable
• Incomputable
• Algorithmic
• Computability
• Halting
• Recursive

Literary Works / 文学作品

• Introduction to the Theory of Computation（Michael Sipser）
• Computability and Logic（George S. Boolos, John P. Burgess, Richard C. Jeffrey）
• Gödel, Escher, Bach: An Eternal Golden Braid（Douglas R. Hofstadter）
• The Annotated Turing（Charles Petzold）
• Theory of Recursive Functions and Effective Computability（Hartley Rogers Jr.）