一般我们说到“问题”这个词语时,对应的往往是“答案”。
工作、生活中,有经验的前辈,经常会告诉我们,再复杂的问题也是有答案的。这里面所提到的问题可以分成两种,即感性问题和理性问题。对于感性问题,这里不做讨论,因为感性问题很难有唯一的解,任何事情把情感融入进来,往往很难有绝对的孰是孰非。而理性问题就不同了,它是以数理为基础的问题,有着计算的明确性和描述的唯一性。计算机问题就属于后者,那么,在现如今计算机高速发展的今天,有没有计算机不可解决的问题?
这个“不可解问题”,初听起来可能会比较匪夷所思。对于一个计算机问题,我们的第一反应是肯定有解啊,不论多么复杂的问题,只是解决起来是否困难、计算时间是否很长而已。而这个“不可解”听着就怪怪的,一般人很难想象,有一个明确的计算问题,它无论如何也不可能有一个正确的算法来解决,而且这个问题确实存在!
伟大的图灵提出了第一个不可解问题: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