2.1.1 计算与函数

计算思维和计算机都离不开“计算”的概念。广义的计算（Calculation）是指一种将“单一或多个输入值”转换为“单一或多个的结果”的一种思维过程，这与计算机中一个重要的概念——函数（Function）的定义是一致的。函数从数学意义上讲，指的是一组可能的输入值和一组可能的输出值之间的映射关系，它使每个可能的输入对应单一的输出。例如，单位的换算机制可以看作一个函数，我们提供一种单位下的数值，根据两种单位之间的数值对应关系唯一地计算出另一单位下的对应数值。又如我们熟悉的四则运算也都可以看作函数，对于加法，我们的输入是两个加数的数值，根据加法的规则运算之后，输出则是两个数的和。对于函数来说，由给定的输出确定输出的过程，称为函数的计算。

计算机正是通过函数进行计算达到解决问题的目的，它读取用户的输入，根据预先建立好的映射规则计算输出结果，并将结果返回给用户。例如，为了解决加法问题，就必须读取用户的输入并计算加法函数。当然现实生活中的问题不都是数学计算，人类也正是通过将现实问题抽象成一个个函数的求解过程才能使计算机完成各种各样的功能，例如我们使用计算机上网观看一段视频，这一过程看似与“计算”无关，但实际上从我们用鼠标点击视频播放按钮到视频开始播放，这中间计算机执行的正是将一系列的输入转换到输出的操作，因此广义上讲也属于计算。

那么人类要利用计算机高速的计算能力解决实际问题时，就必须思考以下3个问题。

1.哪些问题能够被计算

并不是全部的问题都能被有效地计算。问题可以具有很高的复杂性，但有些问题不管多么复杂，仍然可以找到一种方法，只要按照方法一步步执行，就能根据输入值确定输出值，这样的问题称为可计算（Computable）的问题；相反的，有些问题不存在一步步执行就能解决的方法，则称这类问题为不可计算（Uncomputable）的问题。

2.如何利用计算机系统实现计算

现实中的问题多种多样，各行各业都有不同的问题领域。即使是可计算的问题，也不一定都能顺利地利用计算机系统实现。要想利用计算机解决实际问题，还要思考如何合理地对问题进行抽象，如何设计计算机系统以使其能方便地解决问题。

3.如何高效地实现计算

假设问题能够通过计算机自动进行计算，还要考虑计算的代价问题。如果解决问题花费的时间太久（想象利用计算机中的计算器软件执行一次加法运算要等上一分钟），或者需要的资源过多（想象计算机还具有埃尼阿克那样的体积和耗电量），都不会使计算机成为理想的解决问题的工具，这同样也涉及计算机系统的构建以及问题优化、数据处理、软件构建等问题。

扩展阅读：图灵机与丘奇-图灵论题

关于哪些问题是可以计算的，哪些问题是不能被计算的，即计算的局限性早在20世纪30年代就开始被科学家们进行研究，其中最重要的里程碑是图灵机的提出。1936年，在技术能够提供我们现在所知道的机器之前，阿兰·图灵就提出了图灵机的概念，用来代替纸、笔计算来研究计算的局限性。在此前不久，1931年，哥德尔发表了著名的揭示计算系统局限性的论文，并且其研究的主要精力集中在理解这些局限性上。在图灵提出图灵机概念的同一年，埃米尔·波斯特提出了另外一种模型，这种模型与图形的模型具有相同的能力。作为这些早期研究人员洞察力的见证，他们的计算系统模型在计算机科学研究领域至今仍然可以作为有价值的工具来使用。

能够通过图灵机计算的函数称为图灵可计算函数。图灵猜想指出：图灵可计算函数与可计算函数是一样的，即图灵机的计算能力囊括了任何算法系统的能力。这个猜想通常被称为丘奇-图灵论题，自从图灵的最初工作以来，已经收集了许多支持这个论题的例证。现在，丘奇-图灵论题已经被广泛地接受了，也就是说，可计算函数与图灵可计算函数被认为是一回事。这个猜想的意义在于它领悟到了计算机器的能力和局限性。