在图灵1936年论文第二章,图灵用circle-free来定义“可计算数(Computable sequences and numbers)”,这个定义实际上是由二部份构成的,首先由circle-free来定义“可计算序列”,进一步由“可计算序列”定义“可计算数”。 按照图灵的定义: A sequence is said to be computable if it can be computed by a circle-f ...
“可计算性(Computability)”是可计算性理论的核心概念,具有深刻的数学内涵和哲学底蕴,图灵、丘奇、哥德尔等前辈的工作为此概念打下了坚实的基础,应该说对此概念的理解已经不成问题了,然而从“NP是可计算的”流行观念看,此概念并未得到人们充分而正确的解读,这或许是造成千禧年难题“P versus NP”的最根本原因。 ...