什麽是可以計算的，只要把不可以計算的全部排除，剩下的就是全部可以計算的了。

　　馬丁·戴維斯《可計算性和不可解性》開始研究什麽樣的計算是可計算的。

　　那什麽又是不可以計算的?

　　首當其衝的是停機問題。令Z表示一個簡單圖靈機。關於Z，有如下判定:

　　對於一個給定的瞬間描述α，判定是否存在一個以α開始的對Z的計算。也就是說，我們希望如果給定初始狀態，那麽Z會不會最終停止?這就是Z停機問題。

　　最後戴維斯說:“存在一種圖靈機，其停機問題是遞歸無解的。”