为什么有些问题不能解决？

为什么有些问题不能解决？(1) 一些问题没有解决的方法(算法)；(2) 一些问题有解
决的方法(算法)，但随着问题的尺度的增加，无法算下去。

第一类问题中典型的例子是图灵(TURING)停止问题：是否存在一个程序，它可以用
来判断另一个程序是死循环(不停地运行)或停止。一般来说，这样的程序是不存在
的。如果存在这样的程序H，它可以用来判断另一个程序P，H(P)：H将P作为输入。
我们可以根据H(P)的判断结果来设计另一个程序G(H(P))：当H(P)认为P是死循环时，
G停止；当H(P)认为P是停止时，G死循环。SO FAR，SO GOOD。但当我们用G来代替P，
即用上述程序来判断程序G，G(H(G))，我们就进入悖论怪圈。里面的G是死循环，外
面的G是停止；里面的G是停止，外面的G是死循环。实际上里面的G和外面的G是同一
个G。所以，一般来说，程序H是不存在的。在计算机理论中，常有一些递归不能解
决问题。所谓“递归”是指“对自己”，即一些算法“对自己”不灵，“对别人”
可以。

这一类问题还有很多，比较著名的是贴砖(TILING)问题。给出一组有限种类的砖(数
量是无限)，问是否存在一个算法，它能确定是否这些砖能铺满座标系的第一象限。
贴砖时，砖子不能旋转，砖子之间还得符合邻接条件。贴砖的程序可以转换为图灵
机程序。于是贴砖问题就转换为图灵停止问题。因此这样的算法是不存在。

第二类问题也有很多，现举一个旅行商问题。旅行商问题：有N个城市，一个推销员
要从某一个城市出发，走遍所有的城市(一个城市只能去一次)，再回到他出发的城
市，求长度小于或等于K的路线。这个问题属于NP问题，即非确定性多项式时间问题。
所谓NP问题是指，有一个非确定型计算机，它可以得到问题的解，而且每一步程序
都是正确的；(实际上，世界上还没有这种计算机) 然后只需用多项式时间来证实这
个问题的解。对于旅行商问题，非确定型计算机已经得到它的解，证实这个解实际
上只需多项式时间。当然，用确定型计算机求解这个问题，就需要(N-1)阶乘时间，
因此当N很大时，无法算下去。对于旅行商问题，如果我们要证实没有长度小于或等
于K的路线，这就不是NP问题，因为我们要枚举所有的情况。这时，这个问题属于CO-NP问题。

在研究工作中，我们经常碰到这样的情况，当问题的尺度比较小时，理论很优美，
计算也简单；当问题的尺度比较大时，就无法搞下去。