此外，图灵和丘奇还分别改进了一个称为丘奇-图灵理论的声明。对于这一理论既有狭隘的解释又有广义的解释。狭隘的解释是：如果一个问题能出现在图灵机中，但得不到解决，那么它不能被任何机器解决。这个结论来源于图灵的证明，他证明了图灵机能够模拟任何算法过程。要想描述遵循一种算法的机器行为，这仅仅是一小步。
基于丘奇-图灵理论的强大人工智能提出如下的批判意见：因为计算机能够解决的问题类型存在明确限制，但人类有能力解决这些问题，机器却永远不能完全赶上人类智能。然而，这一结论是经不起论证的。和机器相比，人类没有更多的能力处处解决这种“无解”的问题。在某些情况下，我们可以做些有根据的猜测，或采用启发式方法（一种程序，试着去解决问题，但不保证有用），并偶尔成功。但这两种方法都是基于算法的处理，这意味着机器也能够做这些。实际上，和人类相比，机器通常可以找到更快的更彻底的解决方案。
为了查看机器使用启发式方法的能力，可以考虑一个最有趣的无解问题——“忙碌的河狸”问题，它是蒂伯·雷德在1962年提出的31。每个图灵机器有一定量的状态，其内部程序可处于这些状态，每个状态对应其内部程序的步骤数量。有可能存在一些4个不同状态图灵机、5个状态图灵机等。在“忙碌的河狸”问题中，给定一个正整数n，使所有的图灵机都具有n种状态。这种机器的数量总是有限的。接下来，我们消除这些n种状态机器，它们进入一个无限循环（永不停止）。最后，我们选择一个机器（它已经停止下来），它在自己的磁带上写入最多个1。这种图灵机写入1的数目就是所谓的n个忙碌的河狸问题。雷德表示，任何算法、任何图灵机都不能为所有n种状态计算这种功能。问题的症结是清理这些陷入无限循环的n种状态机器。如果我们编写一个图灵机能够生成和模拟所有可能的n种状态图灵机，当它试图去模拟进入了无限循环的n种状态机器其中一个时，这种模拟器本身就已进入了一个无限循环中。
大约在同一时间，美国数学家和哲学家阿隆佐·丘奇发表了一个定理，在算术方面提出了类似的问题。丘奇独立地得到了与图灵相同的结论29。综合来说，图灵、丘奇和哥德尔首次正式证明了逻辑、数学和计算机能做的事情有一定的限制。
丘奇-图灵理论的广义阐述暗示着生物大脑和机器一样受制于物理学定律，因此，数学同样可以对它们建模和仿真。我们有能力对神经元的功能进行建模和仿真，这是已经论证了的，那么为什么不建一个有千亿个神经元的系统？这样的系统像人类智能一样，显示同样的复杂度，同样缺乏可预见性。事实上，我们已经有结果复杂和不可预测的计算机算法（例如遗传算法），这些算法能提供问题的智能解决方案。丘奇-图灵理论暗示了大脑和机器实质上是等价的。
当我们算到10的时候，图灵机可以计算很多类型，这些计算对于人类来说是不可能的（不从计算机得到帮助）。因此，我们必须依靠计算机才能确定10的忙碌的河狸。答案需要用一个奇异的标记写下来，在这个标记中有一个指数堆栈，这些指数的级数是由另一堆栈的指数确定。由于一台计算机能保持这种复杂数字的轨迹，而人脑却不能，这证明计算机比人类更有能力解决无解问题。
事实上，存在一些不能用这个特定理论机器来解决的问题可能不会特别令人吃惊，直到考虑图灵论文的其他结论：图灵机可以模拟任何计算过程。图灵表明，不能解决的问题和能解决的问题一样多，每种问题的数量是无穷的最低值，所谓的可数无穷大（可以计算整数的数量）。图灵还论证了，在任何一个系统，判断任何逻辑命题的真伪都很困难，哪怕这个系统的逻辑强大到能描述自然数就是无解问题之一，这个结论类似哥德尔。（换句话说，任何程序都无法保证回答所有命题的问题。）
艾伦·图灵在理解计算的性质时得到了类似的结论。1936年，图灵提出了图灵机（详见第2章），并报告了一个意外的类似哥德尔的发现28。图灵机作为计算机的一个理论模型发展至今，并形成了现代计算理论的基础。图灵在当年的论文中描述了无法解决的问题的概念，那就是存在这样的问题：它有明确的定义和唯一的答案，但我们不能通过图灵机计算。
值得注意的是，虽然图灵无解问题的存在是一种数学论断，但丘奇-图灵理论根本不是一个数学命题。事实上，它只是一个在各种假设情况下的猜想，它处在我们关于精神哲学最深刻的辩论的核心30。
早在20世纪数学家阿尔弗雷德·诺斯·怀特海德和波特兰·拉塞尔就发表了他们的开创性工作——《Principia Mathematica》（数学原理），这本书试图确定一些公理，让它们作为所有数学的基础。26然而，他们最后没能证明可以生成自然数（正整数或自然数）的公理系统不会引起矛盾。据推断，这种证明迟早会被找到，但在20世纪30年代，年轻的捷克数学家库尔特·哥德尔证明了在这样的一个系统中必然存在一些命题，他们既不是真命题也不是假命题，他通过这个证明震惊了整个数学界。后来发现，这些不可证明的命题就像可被证明的命题一样常见。哥德尔的不完全性定理从根本上表明逻辑、数学甚至计算的能力是有限的，这个定理被称为数学中最重要的定理，它的含义仍在争论中。27
尽管它是一个无解问题（最有名的一个），但是我们还是能够针对某些n确定忙碌的河狸功能（有趣的是，将我们能够确定其“忙碌的河狸”的n和我们无法确定的n分开也是一个无法解决的问题）。例如，很容易确定6的是35。对于7种状态，一个图灵机可以相乘，所以7种状态的忙碌的河狸是非常大的：22961。对于8种状态，一个图灵机可以计算出指数函数，所以8种状态的忙碌的河狸更大：约1043。我们可以看到，这是一个“智能”功能，因为它需要更高的智能来解决更大的n的忙碌的河狸。
广义的解释是：图灵机无法解决的问题，人类思维也无法解决。这一论点的依据是，人的思维被人脑执行（身体也有一些影响），即人脑（和身体）包括物质和能量，这物质和能量遵循自然法则，这些法则能够用数学术语描述，而算法能够在任何精度上模拟数学。因此，存在着算法可以模拟人的思想。丘奇-图灵理论的广义版本假定人类能够想到的和知道的与可计算物质在本质上是等价的。
