可计算与不可计算函数的边界

数学意义上的函数只是输入集合到输出集合的一种对应关系，但”存在这种对应关系”和”存在一套算法能一步步算出这个对应关系”是两回事——简单函数可以用一张完整的表格列出所有输入输出（但输入无限时表格注定不完整），复杂一点的可以用代数公式描述（如复利计算），再复杂的需要更强的数学方法（如三角函数的近似计算）。但存在一些函数，复杂到根本找不到任何定义明确、一步步可执行的过程来从输入算出输出，这类函数被称为不可计算的，其计算需求超出了任何算法系统（因此也包括任何计算机）的能力范围。发散：这条边界之所以重要，是因为机器只能执行由算法描述的任务——如果一个问题的解决依赖计算某个不可计算函数，那么无论未来硬件多强大，这个问题都注定超出机器能力，这不是工程水平的局限，而是数学上被证明了的天花板，这也是为什么理论计算机科学要先划清”可计算”的边界，才能谈”高效计算”的问题。