来讨论讨论逻辑和可计算性

yongjian

Halting problem 很典型，计算机没有办法根据参数的变化来判断什么时候运行停止。我的感觉是不能为数学证明的问题都是不可计算的。算法是以数学证明为前提的，是想如果一个问题不能通过数学描述来证明，那如何能写算法啊？那是不是能被数学证明的问题都有可能的算法呢？

yongjian

NPC 问题无法通过确定多项式的算法来描述，但很多却可以brute force得到答案。只要输入量级已知并且复杂度不大的话，还是可以在有限时间里得到答案的。如果brute force也算一种算法的话，那算法也不一定都需要以严格的数学证明为前提了。可以这样理解吧。