早在20世紀數學家阿爾弗雷德·諾斯·懷特海德和波特蘭·拉塞爾就發表了他們的開創性工作——《Principia Mathematica》（數學原理），這本書試圖確定一些公理，讓它們作為所有數學的基礎。26然而，他們最後沒能證明可以生成自然數（正整數或自然數）的公理系統不會引起矛盾。據推斷，這種證明遲早會被找到，但在20世紀30年代，年輕的捷克數學家庫爾特·哥德爾證明了在這樣的一個系統中必然存在一些命題，他們既不是真命題也不是假命題，他通過這個證明震驚了整個數學界。後來發現，這些不可證明的命題就像可被證明的命題一樣常見。哥德爾的不完全性定理從根本上表明邏輯、數學甚至計算的能力是有限的，這個定理被稱為數學中最重要的定理，它的含義仍在爭論中。27
艾倫·圖靈在理解計算的性質時得到了類似的結論。1936年，圖靈提出了圖靈機（詳見第2章），並報告了一個意外的類似哥德爾的發現28。圖靈機作為計算機的一個理論模型發展至今，並形成了現代計算理論的基礎。圖靈在當年的論文中描述了無法解決的問題的概念，那就是存在這樣的問題：它有明確的定義和唯一的答案，但我們不能通過圖靈機計算。
事實上，存在一些不能用這個特定理論機器來解決的問題可能不會特別令人吃驚，直到考慮圖靈論文的其他結論：圖靈機可以模擬任何計算過程。圖靈表明，不能解決的問題和能解決的問題一樣多，每種問題的數量是無窮的最低值，所謂的可數無窮大（可以計算整數的數量）。圖靈還論證了，在任何一個系統，判斷任何邏輯命題的真偽都很困難，哪怕這個系統的邏輯強大到能描述自然數就是無解問題之一，這個結論類似哥德爾。（換句話說，任何程序都無法保證回答所有命題的問題。）
大約在同一時間，美國數學家和哲學家阿隆佐·丘奇發表了一個定理，在算術方面提出了類似的問題。丘奇獨立地得到了與圖靈相同的結論29。綜合來說，圖靈、丘奇和哥德爾首次正式證明了邏輯、數學和計算機能做的事情有一定的限制。
此外，圖靈和丘奇還分別改進了一個稱為丘奇-圖靈理論的聲明。對於這一理論既有狹隘的解釋又有廣義的解釋。狹隘的解釋是：如果一個問題能出現在圖靈機中，但得不到解決，那麼它不能被任何機器解決。這個結論來源於圖靈的證明，他證明了圖靈機能夠模擬任何算法過程。要想描述遵循一種算法的機器行為，這僅僅是一小步。
廣義的解釋是：圖靈機無法解決的問題，人類思維也無法解決。這一論點的依據是，人的思維被人腦執行（身體也有一些影響），即人腦（和身體）包括物質和能量，這物質和能量遵循自然法則，這些法則能夠用數學術語描述，而算法能夠在任何精度上模擬數學。因此，存在著算法可以模擬人的思想。丘奇-圖靈理論的廣義版本假定人類能夠想到的和知道的與可計算物質在本質上是等價的。
值得注意的是，雖然圖靈無解問題的存在是一種數學論斷，但丘奇-圖靈理論根本不是一個數學命題。事實上，它只是一個在各種假設情況下的猜想，它處在我們關於精神哲學最深刻的辯論的核心30。
基於丘奇-圖靈理論的強大人工智能提出如下的批判意見：因為計算機能夠解決的問題類型存在明確限制，但人類有能力解決這些問題，機器卻永遠不能完全趕上人類智能。然而，這一結論是經不起論證的。和機器相比，人類沒有更多的能力處處解決這種「無解」的問題。在某些情況下，我們可以做些有根據的猜測，或採用啟髮式方法（一種程序，試著去解決問題，但不保證有用），並偶爾成功。但這兩種方法都是基於算法的處理，這意味著機器也能夠做這些。實際上，和人類相比，機器通常可以找到更快的更徹底的解決方案。
丘奇-圖靈理論的廣義闡述暗示著生物大腦和機器一樣受制於物理學定律，因此，數學同樣可以對它們建模和仿真。我們有能力對神經元的功能進行建模和仿真，這是已經論證了的，那麼為什麼不建一個有千億個神經元的系統？這樣的系統像人類智能一樣，顯示同樣的複雜度，同樣缺乏可預見性。事實上，我們已經有結果複雜和不可預測的計算機算法（例如遺傳算法），這些算法能提供問題的智能解決方案。丘奇-圖靈理論暗示了大腦和機器實質上是等價的。
為了查看機器使用啟髮式方法的能力，可以考慮一個最有趣的無解問題——「忙碌的河狸」問題，它是蒂伯·雷德在1962年提出的 31。每個圖靈機器有一定量的狀態，其內部程序可處於這些狀態，每個狀態對應其內部程序的步驟數量。有可能存在一些4個不同狀態圖靈機、5個狀態圖靈機等。在「忙碌的河狸」問題中，給定一個正整數n，使所有的圖靈機都具有n種狀態。這種機器的數量總是有限的。接下來，我們消除這些n種狀態機器，它們進入一個無限循環（永不停止）。最後，我們選擇一個機器（它已經停止下來），它在自己的磁帶上寫入最多個1。這種圖靈機寫入1的數目就是所謂的n個忙碌的河狸問題。雷德表示，任何算法、任何圖靈機都不能為所有n種狀態計算這種功能。問題的癥結是清理這些陷入無限循環的n種狀態機器。如果我們編寫一個圖靈機能夠生成和模擬所有可能的n種狀態圖靈機，當它試圖去模擬進入了無限循環的n種狀態機器其中一個時，這種模擬器本身就已進入了一個無限循環中。
儘管它是一個無解問題（最有名的一個），但是我們還是能夠針對某些n確定忙碌的河狸功能（有趣的是，將我們能夠確定其「忙碌的河狸」的n和我們無法確定的n分開也是一個無法解決的問題）。例如，很容易確定6的是35。對於7種狀態，一個圖靈機可以相乘，所以7種狀態的忙碌的河狸是非常大的：22961。對於8種狀態，一個圖靈機可以計算出指數函數，所以8種狀態的忙碌的河狸更大：約1043。我們可以看到，這是一個「智能」功能，因為它需要更高的智能來解決更大的n的忙碌的河狸。
當我們算到10的時候，圖靈機可以計算很多類型，這些計算對於人類來說是不可能的（不從計算機得到幫助）。因此，我們必須依靠計算機才能確定10的忙碌的河狸。答案需要用一個奇異的標記寫下來，在這個標記中有一個指數堆棧，這些指數的級數是由另一堆棧的指數確定。由於一台計算機能保持這種複雜數字的軌跡，而人腦卻不能，這證明計算機比人類更有能力解決無解問題。