在發現巨大素數、解阿基米德牛群問題、破譯密碼、證明四色地圖定理以及發現新圖形等問題上，計算機證明對數學家是有用的。然而在計算機能做些什麼問題上，卻還有難以捉摸的限制。
自20世紀30年代起，數學就面臨著一場革命，如同物理學的兩次革命——廣義相對論與量子力學——一樣重要，這兩次革命動搖了物理學的基礎，並且推翻了關於空間、時間與因果律的經典理論。數學的前景展望也由於美國紐約大學的莫里斯·克林提出了“必然的損失”的說法而完全改觀。一種嶄新的工作已不再注重於數學計算的能力，而是注重於計算的限制。有意義的計算問題被規定為原理上不能解的，或在原理上能解而實際上無法解的問題。
一個從原理上不能解的有意義的典型問題就是“停機問題”，它是艾倫·馬西森·圖靈於1936年提出的。圖靈想到了計算機程序是否遲早會提供結果和停機的問題。停機問題已不僅是紙上談兵的理論家所關心的問題，而且是很容易在實踐中出現的問題。
美國麻省理工學院計算機科學理論學家邁克爾·錫普塞說道：“你可以想像，當你把程序編入卡片，然後提交給計算機中心時，尤其是在這幾天裡，你是多麼想知道答案。他們總是整夜地進行運算，第二天就送回給你。比方說，你有一筆100美元的錢存在機內。有時，計算機程序會有一個無限的循環，而且會耗掉許多錢。由於它會陷入無限的循環，因此你從程序上得不到任何東西。不論是你帳上的錢都已耗費完，還是計算機以何種方式註意到機器運行了很長時間，計算機自己停了機。
“那麼，你一定會想，為什麼事先不檢驗程序，如果其中有無限循環，就不應該用它運算”。然而令人驚奇的是，這種自然的概念不能夠實現，因為圖靈證明了，沒有一種檢驗方法能夠適用於所有程序。
除了圖靈所證明的停機問題是不可解的之外，1936年數學家向絕對數學知識的虛幻目標發動了另一次進攻。邏輯學家阿朗索·丘奇證明了所謂的判定問題也是不可解的：判定一個已知的語句是否表達一個算術的真值，決不可能有一般的過程。換句話說，能夠輸出所有算術真值的計算機是不存在的。至於你所給的每一種可能想到的算術語句，計算機也是不能確定其真值的。的確如此，要求找出算術的真值是沒有訣竅的。
近幾年來，數學界的注意力已從理論上不能解的問題轉向理論上能夠解而實際上不能解的問題上。在這些問題中，最著名的就是美國國際商業機器公司（IBM）的拉里·斯托克邁耶稱之為“內在困難”的問題，即委婉法問題，如果這也算是一個問題的話。他請你構想一部想像中的最大功率的計算機。這部想像的計算機，可以大到充滿整個宇宙（直徑也許為1，000億光年）。它將由質子大小（直徑為10-13厘米）的硬件構成，信號將以光速（每秒3×1010厘米）在硬件中疾馳通過。它可以就某個問題工作200億年，它超過了宇宙的估計年齡。這個難題具有一個令人不知所措的特點，即它在原則上能夠解決，但即使用可想像出的最大功率的計算機，按宇宙年齡再工作上千百萬年也無法解決。
這類問題之一是下棋問題，它在棋盤不是普通的8×8，而是n×n（這裡n表示任意大的數目），而且還有不限數量的棋子（但每方只能有一個王棋）。我們想有一種計算機程序，不論棋下到哪一步，不管我們是哪一方，比如說白子，它都可以用來確定是否能夠贏。某種程序只在理論上可行而在實際中行不通，它需要考慮所有白方可能走的棋步，隨後考慮所有黑方可能回應的棋步，還要考慮所有白方可能反回應的棋步，以此類推，考慮所有可能繼續的棋步，直到結束時為止。
這種窮舉搜索程序的缺點是速度太慢：有那麼多可能繼續的棋步，甚至理想的計算機也不可能在200億年的時間內把所有棋步都考慮進去。 1981年，美國耶魯大學的戴維·利希滕斯坦和以色列的數學家艾維茲裡·弗倫克爾證明了對於足夠大的棋盤也沒有更快的程序。換句話說，耗時的窮舉搜索程序沒有簡捷的方法。這種下棋問題，即使我們知道已有解法，也總是會使計算機的分析落空。
下面4章，我們將從理論和實踐兩個方面考慮計算機的能力與局限性。