為什麽有些問題不能解決？

為什麽有些問題不能解決？(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問題。

在研究工作中，我們經常碰到這樣的情況，當問題的尺度比較小時，理論很優美，
計算也簡單；當問題的尺度比較大時，就無法搞下去。