这台想象中的机器会如何回答希尔伯特的第三个问题——判定问题呢？图灵通过重新定义“可计算数”的概念来着手处理这个问题。由数学规则定义的任意实数都可以通过逻辑计算机器计算出来。甚至像π这样的无理数也可以使用有限的指令表进行无限的计算，其他例子包括7的对数、2的平方根，以及埃达·洛夫莱斯帮助设计算法的伯努利数。实际上无论是多么复杂的数字和数列，只要它的计算是由有限的规则集定义的，那么它就可以被计算出来。按照图灵的说法，这些都属于“可计算数”。
在过去，科学界往往认为，如果我们完全了解了某一时刻的宇宙，就能预测它会在未来发生的所有事情。这个观点来源于天文预测方面取得的成功。然而，现代科学得出的结论是，当我们在讨论原子和电子时，我们无法知道它们的确切状态，因为我们的测量工具本身就是由原子和电子组成的。于是，能够知道宇宙确切状态这一观点在微观尺度上必须被推翻。那么这就意味着“由于日食等天文现象可以预先确定，因此我们的行为也能预先确定”这一理论也是不可信的。我们拥有某种意识，能够控制一部分或者整个大脑的原子的活动。7
1936年9月，在等待论文发表的期间，这位24岁的博士研究生乘上了老旧的远洋邮轮贝伦加利亚号远赴美国，他身上带着一台铜制六分仪。图灵在普林斯顿大学的办公室位于数学系的大楼，这里当时也是普林斯顿高等研究院的所在地，爱因斯坦、哥德尔和冯·诺依曼都曾经担任过这所研究院的院长。温文尔雅、热衷社交的冯·诺依曼对图灵的工作特别感兴趣，尽管他们两人的性格截然不同。
虽然他构想出的“逻辑计算机器”（这只是一个思维实验，并非一台真正得到建造的机器）看起来非常简单，但是它在理论上可以处理任何数学计算。它含有一条无限长度的纸带，纸带上面的方格可以显示不同的符号。如果采用最简单的二进制形式的话，这些符号可以表示为“1”和“空白”。这台机器可以读取纸带上的符号，并根据给定的“指令表”执行特定的操作。9
在舍伯恩的最后一年里，图灵获得了剑桥大学国王学院的奖学金，他在1931年入读这个学院学习数学。他用这笔奖学金买了三本书，其中一本是约翰·冯·诺依曼（John von Neumann）所著的《量子力学的数学基础》（The Mathematical Foundations of Quantum Mechanics ）。冯·诺依曼是一位出生于匈牙利的杰出数学家，这位计算机设计先驱对图灵以后的人生产生了长远的影响。图灵对量子物理学核心的数学原理特别感兴趣，这种数学原理描述的是在亚原子层面发生的事件会如何受到统计概率的控制，而不是那些使用必然性定义事物的原理。图灵（至少在年轻时）相信处于亚原子层面的不确定性使得人类可以实现自由意志——如果这个观点正确的话，能否实现自由意志似乎是一个可以用于区分人类和机器的特征。换句话说，由于发生在亚原子层面的事件不是预先确定的，我们的思考和行动方式才得以有无限的可能。他在一封写给莫科姆母亲的信中解释道：
艾伦的体格强壮，身材高大，他有一个方正坚实的下巴和一头桀骜不驯的棕色头发。深邃而清澈的蓝眼睛是他标志性的特征。微微上翘的短鼻子和讨喜的嘴巴轮廓让他看起来很年轻（有时甚至显得幼稚），以至于年近40的他仍然会被人误以为是大学生。他在衣着和生活习惯方面比较不修边幅。他通常会留着过长的头发，而且总会有一绺刘海垂到脸上，这时他会用力一甩头将其抛回原处……他有时会心不在焉和精神恍惚，这是因为他正在全神贯注于自己的思考当中，在某些场合下，这点会让他显得不擅交际……有时候他的羞怯在别人看来是非常无礼的……事实上他认为自己很适合隐居在中世纪的修道院里面。4
在一场1928年举行的数学大会上，希尔伯特提出了关于任意数学形式系统的三个基本问题：（1）系统的规则集是完备的吗？只使用系统的规则能否证明（或证伪）任意的数学命题？（2）系统是一致的吗？会不会有既可以证明正确，又可以证明错误的命题？（3）系统是可判定的吗？有没有可以判定特定命题是否可证明的方法，会不会出现某些陈述存在不可判定状态的可能性（例如费马大定理[1] 、哥德巴赫猜想 [2] 和考拉兹猜想 [3] 等悬而未决的数学谜题）？希尔伯特认为前两个问题的答案都是肯定的，剩下第三个问题仍有待商榷。他简单明确地表示，“世界上没有无法解决的问题”。
于是在希尔伯特的问题当中只剩下第三个可判定性问题尚未解决，希尔伯特本人将这个问题称为“判定问题”（decision problem）。尽管哥德尔提出了既不能被证明也不能被证伪的命题，但是这些特殊的命题可以通过某种方式辨别和隔离，让形式系统剩余的部分保持完备和一致。这就需要我们找出一些可以判定一个命题是否可证明的方法。剑桥大学的杰出数学教授麦克斯·纽曼（Max Newman）在向图灵讲解希尔伯特的问题时，他对“判定问题”的表述是：有没有一种“机械方式”可以用于判定某个逻辑命题是否可证？
“判定问题”还有另外一个优雅程度不如图灵机的解答——“无类型λ演算”（untyped lambda calculus），这是普林斯顿大学的数学家阿隆佐·邱奇在同年早些时候发表的一个形式系统。图灵的教授麦克斯·纽曼认为，图灵如果跟邱奇学习的话将会为他带来很大的帮助。在写给邱奇的推荐信中，纽曼表示图灵的前途不可限量，同时根据图灵的个性提出了一个更为私人的请求。“他一直以来的工作都没有得到他人的指导或者评价，”纽曼写道，“这点使他更加有必要尽快接触这个领域的领军人物，这样他才不至于变成一个无可救药的孤独者。”11
图灵很喜欢“机械方式”的概念。1935年夏季的某一天，他跟往常一样独自外出沿着伊利河畔跑步。在跑完几英里的路程之后，他停下来躺在格兰切斯特草甸的苹果树下，潜心思考一个问题。他按照字面意思理解“机械方式”的概念，想出一个可以用于解决这个问题的机械方式——一台想象中的机器。8
艾伦在舍伯恩寄宿学校里认识到自己是一个同性恋者。他开始迷恋一位身材瘦削的金发同学克里斯多夫·莫科姆（Christopher Morcom），他们一起研究数学并讨论哲学问题。但是在他毕业前的寒假里，莫科姆突然死于结核病。图灵后来给莫科姆的母亲写了一封信，信中写道：“我真诚地崇拜他踏足过的土地——非常抱歉，我无法掩盖这点。”5 在写给自己母亲的一封信中，图灵似乎想从自己的信仰中寻求安慰：“我感觉自己会在某个地方再次遇到莫科姆，在那里，我们又可以一起工作，正如我之前以为我们可以在这里一起做的一样。现在既然只剩下我一个人来完成我们共同的事业，我一定不能让他失望。如果我能取得成功，我将会比现在更有资格与他在一起。”然而这个悲剧最终侵蚀了图灵的宗教信仰，而且还使他变得更加内向，他之后再也无法轻易地与他人建立亲密的关系。他的舍监在1927年复活节时向他的父母汇报道：“无可否认他不是一个‘普通’的男孩，当然这不是最坏的情况，只是不如其他孩子快乐而已。”6
此后图灵一直在钻研这个问题：人类大脑与确定性机器之间是否存在根本区别？他后来逐步得出的结论是，人与机器的界线要比他原来想象中的更为模糊。
图灵的确更倾向于独来独往。身为同性恋者的事实让他有时会感到自己无法融入其他人的圈子；他独自一人居住，避免与其他人进行深入的接触。他曾经向一位女同事求婚，但后来他还是觉得有必要告诉她自己是同性恋者。对方没有为此感到困扰，仍然愿意与他成婚，但他始终认为这是一种欺骗行为，因此没有继续这桩婚事。不过，他最终并没有成为一个“无可救药的孤独者”。他学会了如何在一个团队中与其他协作者一起工作，正因为有了这样的合作，他的抽象理论才得以体现在真正的发明上。
他还有这样一个直觉，正如亚原子的范围内充满了不确定性，有一些数学问题也是无法通过机械的方式解决的，它们注定要披着不确定性的外衣。当时的数学家们主要专注于研究关于逻辑系统的完整性和稳定性的问题，这种情况在一定程度上是受到了大卫·希尔伯特（David Hilbert）的影响。这位居住在德国哥廷根的天才数学家拥有众多杰出的成就，其中一项是与爱因斯坦同时提出广义相对论的数学表达式。
出身于英国没落贵族的艾伦·图灵在一个缺乏关爱的环境中成长。1 他的家族在1638年受封从男爵爵位，这个爵位一直在图灵家族中世袭，最后传到了艾伦的一位远房侄子。但是图灵家谱中的旁系是没有领地的，也不能继承多少财产，艾伦的祖父就属于这样的旁系。大多数没有继承爵位的家族成员都成了神职人员（比如艾伦的祖父）或者英属殖民地的公务员，他的父亲就是一位服务于印度边远地区的基层行政人员。艾伦是在印度恰特拉普尔被怀上的，随后他的父母回到伦敦休假，并在1912年6月23日生下了艾伦。在他只有一岁的时候，他的父母就要返回印度继续工作，于是艾伦和他的哥哥就被交给了居住在英格兰南海岸的一对退役陆军上校夫妇照顾。“虽然我不是儿童心理学的专家，”他的哥哥约翰·图灵后来表示，“但我相信让一个襁褓中的婴儿离开父母的怀抱，并在一个陌生的环境中成长肯定不会是一件好事。”2
1937年出现的翻天覆地的变化和接踵而至的进步并非直接源于图灵的论文发表。事实上，这篇论文在刚发表的时候也并没有得到多少关注。图灵请母亲将论文的副本寄给数学哲学家伯特兰·拉塞尔和其他六位知名学者，但是只有阿隆佐·邱奇对它进行了认真的审阅。邱奇能够欣赏图灵的工作成果，因为他自己在解决希尔伯特判定问题方面的研究一直领先于图灵。邱奇不仅乐于提携后辈，他还将图灵所说的逻辑计算机器命名为“图灵机”。于是，年仅24岁的艾伦·图灵，他的名字就被永远地刻在了数字时代一个最为重要的概念上。12
图灵在1937年发表了一篇题为《论可计算数及其在判定问题上的应用》的论文，这是一个不太能引人注意的题目。他对希尔伯特的第三个问题的解答有助于数学理论的发展，不过意义更为重大的是图灵在证明过程中产生的逻辑计算机器的概念。这台机器在不久后就被称为图灵机。“发明一台可以用于计算任意可计算序列的机器是可能的。”他断言道。10 这台机器将可以读取其他任何机器的指令，并执行该机器可以完成的任何任务。图灵机从本质上实现了查尔斯·巴贝奇和埃达·洛夫莱斯关于完全通用型机器的梦想。
图灵进一步证明了“不可计算数”的存在。这点跟他提出的“停机问题”（the halting problem）有关，他证明了不存在可以解决停机问题的方法，也就是不能提前判定任意给定指令表和输入集的组合会导致机器得出答案还是进入无限的循环。他表示停机问题的不可解性意味着希尔伯特的判定问题也是不可解的。尽管希尔伯特希望自己的第三个问题也可以得出肯定的答案，但事实上不存在可以判定每一个数学命题的可证明性的机械方式。哥德尔的不完全性定理、量子力学的不确定性，以及图灵对希尔伯特第三个问题的解答都否定了机械的、确定的和可预知的宇宙。
在提出不能被证明或反驳的命题的同时，哥德尔证明了任何足够强大而可以表达常用数学原理的形式系统都是不完备的。他还给出了另外一条配套的定理，能够在事实上否定希尔伯特的第二个问题。
在一份深情的回忆录当中，他的母亲这样描述这个自己过分喜爱的儿子：
希尔伯特提出的前两个问题在三年不到的时间内就被来自奥地利的逻辑学家库尔特·哥德尔（Kurt Gödel）迅速攻破了。时年25岁的哥德尔正与母亲一起居住在维也纳，他当时对前两个问题给出了出人意料的答案：不完备和不一致。他在自己的“不完全性定理”中表示既不能被证明也不能被证伪的命题是存在的。其中一些最简单的例子是类似于“本命题是不可证明的”这样的自指命题。如果它是真命题，那么它可以推出我们不能证明它是真的；如果它是假命题，也会导致逻辑上的矛盾。这就像是源自古希腊的“说谎者悖论”，“本命题为假”这个命题是无法被判定的（如果它是真命题的话，那么它同时也是假命题，反之亦然）。
这个指令表可以根据机器所在的矩阵（configuration）和方格上显示的符号（如果存在的话）指示机器做出对应的操作。例如，用于某个任务的指令表可能会给出这样的指示：如果机器处于矩阵1，并在方格中读取到符号1，那么它就会将方格向右移动，并切换到矩阵2。可能会让我们惊讶的是，只要给定合适的指令表，这样一台机器可以完成任何复杂的数学计算任务。
在母亲回国以后，艾伦跟她一起生活了数年的时间，之后他在13岁的时候被送到了寄宿学校。他独自一人花了两天时间骑车到学校，这是一段超过60英里的路程。他身上有一种孤独者的特质，这点体现在他对长跑和骑行运动的热爱上。他还拥有一个在创新者之间很常见的特点，他的传记作者安德鲁·霍奇斯（Andrew Hodges）对此做出了含蓄的表述：“艾伦需要花比较长的时间才能学会分清主动性和不服从之间的模糊界线。”3
