一般我们说到“问题”这个词语时，对应的往往是“答案”。
工作、生活中，有经验的前辈，经常会告诉我们，再复杂的问题也是有答案的。这里面所提到的问题可以分成两种，即感性问题和理性问题。对于感性问题，这里不做讨论，因为感性问题很难有唯一的解，任何事情把情感融入进来，往往很难有绝对的孰是孰非。而理性问题就不同了，它是以数理为基础的问题，有着计算的明确性和描述的唯一性。计算机问题就属于后者，那么，在现如今计算机高速发展的今天，有没有计算机不可解决的问题？
这个“不可解问题”，初听起来可能会比较匪夷所思。对于一个计算机问题，我们的第一反应是肯定有解啊，不论多么复杂的问题，只是解决起来是否困难、计算时间是否很长而已。而这个“不可解”听着就怪怪的，一般人很难想象，有一个明确的计算问题，它无论如何也不可能有一个正确的算法来解决，而且这个问题确实存在！
伟大的图灵提出了第一个不可解问题：The Halting Problem。
输入一段程序代码和一个针对此程序的输入，能否编程判断运行这个程序后程序是否会终止？
一个问题不可解就已经很神奇了，我们还能证明它确实不可解————这得多么的神奇啊！（画外音来自草帽路飞）
The Halting Problem是一个不可解问题，我们需要证明不可能有一种算法可以：正确判断一个指定的程序运行后，给予指定的输入，程序最后是否能终止。
证明过程非常简单，也非常漂亮，用到了反证法。
假设The Halting Problem是有解的，并且已经用程序实现了：
function Halting(a, b)
{
//经过一系列算法
//若程序a接受参数b后执行终止，则返回true
//否则返回false
******
return trur/false;
}
那么我们只需要再编写一个程序Bug，就会发现存在矛盾：
var
input
begin
get(input); //读入input
if halting(Program Bug code, input) then repeat until false
end.
可以看到，这个Bug程序很有意思，它将自己的程序源码和接受的参数传递给了halting，如果halting返回true，那么它就死循环执行，如果halting返回false，那么它就终止程序。
而halting只有在程序终止时才能返回true，在死循环时返回false，这正好与Bug程序是矛盾的，因此halting问题不可解！
多么神奇的证明，向前辈们致敬。记得初学数论时候，也遇到过一个类似问题，也在此分享出来。
证明，素数/质数 有无穷多个。
假设素数有限多，那就会有全体素数有限集合：
{p1, p2, p3, ... pn}
考虑这个数m：
p1 * p2 * p3 * ... * pn + 1
由于数m并不在素数集合中，因此它不是素数，既可以分解成几个素数相乘，不妨设可以被素数q整除：
m = q * t
由于q是素数，那么q一定属于素数集合，因此q一定是某个pi。
pi * t = p1 * p2 * p3 * ... * pi * ... * pn + 1
等式显然不成立，因此通过反证法得出素数有无穷多个。
Leave a Reply