我们的很多程序的目标都是问题求解,如:
计算两个变量的和;
预测世界杯冠军队;
进行导航路线规划;
当考虑这部分目标时,简单的情形是我们一眼便能判断出一个问题有没有确切的算法得出结论(经典程序);复杂的情形是,我们需要计算机程序经过多轮迭代才能得到最终的结果(就好像你现在不知道自己能不能实现财富自由一样,你需要走一步看一步)。
计算机的早期先驱们(一帮数学家)YY了一种机器,能够求解各种问题。但在他们动手造这个机器前,要先想清楚,这个想法是不是违反逻辑的。如果开始的命题就是违反逻辑的,那他们才不会去真的造这机器。
从数学的角度看,一切问题都可以通过计算机求解吗?
这个问题可以转化为:一切问题,都可以通过有限次的计算得到结果码?
用程序员的语言描述为:在进行问题求解时,能否完全避免出现死循环?或者说,是否存在一种通用的方法,检测一个程序是一个死循环程序?
是否存在一种通用的方法,检测一个程序是一个死循环程序
这个抬杠程序就无法被检测出是否会停机
一个抬杠的程序
如果检测程序说会停机,抬杠程序实际不会停机
如果检测程序说不会停机,抬杠程序实际会停机
结论:不存在这样一个程序(算法),它能够计算任何程序(算法)在给定输入上是否会结束(停机)
以上讨论,即图灵的停机问题。