第454章 巴拿赫-塔斯基悖論

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


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


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

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


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


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