可计算的定义？
提问于 2011-11-13 21:41:27
我想知道什么是可计算的“简明”定义？我之所以这样问，是因为我对什么是可计算的，什么是不可计算的感到困惑。
某些东西只有在停止时才是可计算的吗？例如
function foo(){
while(true);
}是不可计算的，仅仅因为它永远不会停止？或者我混淆了可计算性的定义和停顿问题？
谢谢
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-11-13 22:01:10
如果给定某种(通常是纯理论的)计算机的能力，你可以证明有一个算法可以在有限的时间内解决这个问题，那么某些东西是形式上可计算的。
因此，可计算性是计算机和问题的属性，而不是一段代码的属性。
研究可计算性的两个有趣的结果：
- 某些类别的计算机在可计算方面比其他类别的计算机更有限，但即使是一些非常简单的模型(如图灵机)也可以计算我们知道如何计算的一切。
- 某些问题可以被证明是不可计算或无法决定的。停机问题就是这样一个问题。
Stack Overflow用户
发布于 2011-11-13 21:46:29
可计算性不是程序的属性。可计算性是数学问题的一个属性，它意味着存在一种算法，通过为问题的每个实例提供正确的答案来有效地解决问题。
停顿问题是不可计算的，因为不存在完全解决它的算法(对于图灵完全编程语言)，但它不是可计算性的定义。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8114980
复制相关文章
![[Error] invalid use of incomplete type 使用了未定义的类型](https://developer.qcloudimg.com/http-save/yehe-10659154/cc2e77954d437a61c8a8ce7f8b44ca62.png)
点击加载更多
腾讯云开发者
