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