可计算性

可计算性（Computability）是指一个实际问题是否可以使用计算机来解决。从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）。而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决。事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题。分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题上。