图灵的构想是存在这样一台图灵机,可以用来判定任意图灵机的运行结果。他考虑了以下问题:给定一台图灵机和相关输入集,它最终是会停止,还是永无止境地运行下去?这就是一个判定问题了,属于我们前文讨论过的范畴,尽管它相对复杂一些。现在,假设存在一个机器能够判定这个判定问题,图灵指出,这个假设会引起悖论[3]。因此,没有办法检测出图灵机是否停止。那么,“图灵机是否停止”是一个不可判定问题。所以图灵得出结论:存在某些判定问题不能简单地按照确定的步骤来解决。他解决了希尔伯特的难题:数学并不能被简化为遵循方法解决问题[5]。
这一结果是20世纪数学界最伟大的成就之一,单凭它就足以让图灵在数学界名垂青史。但更伟大的是它的副产物——通用问题解决机器,即图灵机。图灵发明图灵机的时候,它只是个抽象的概念,他并没有想着将它实体化。不过没过多久,不少人,包括图灵自己,开始着手把这个想法转化成现实。在二战时的慕尼黑,康拉德·楚泽(Konrad Zuse)为德国航天部设计了一台名为Z3的计算机,虽然它算不上一台完整的计算机,但引入了不少关键部分。在大西洋彼岸的美国宾夕法尼亚州,由约翰·穆克里(John Mouchly)和普雷斯伯·埃克特(J. Presper Eckert)领导的小组开发了一台名为ENIAC的机器来计算火炮射击表。杰出的匈牙利裔数学家约翰·冯·诺依曼(John von Neuman)对它进行了相关调整,使ENIAC具备现代计算机的基本架构(为了纪念这位数学家,传统计算机的架构被称为“冯·诺依曼架构”)。在战后的英国,弗雷德·威廉姆斯(Fred Williams)和汤姆·基尔伯恩(Tom Kilburn)建造了昵称为“曼彻斯特宝贝”的小规模实验机,直接促成了世界上第一台商用计算机“费兰蒂一号”的出现(图灵本人于1948年加入曼彻斯特大学的工作团队,并编写了最早运行的程序)。