停机问题和数字时代的黎明，1930到1960年彻底改变了人类的历史 _car-t

文章图片

两千多年来，伟大的工程师、数学家和科学家们制造了各种各样的模拟计算机。从古代的天球仪到维多利亚时期的差分机。在20世纪30年代、40年代和50年代，大量的研究将人类从模拟时代带入数字时代。
1930年到1960年这段时间可以看作是历史的分界线。这30年的时间彻底改变了人类的历史。它始于机电式计算机的发展，以晶体管数字计算机的发展而告终。世界被彻底改变了，艾伦·图灵被认为是促成这一伟大改变的人之一。

1936年，图灵发表了一篇论文，题目是《论可计算数及其在判定问题中的应用》。这篇论文否定了大卫·希尔伯特和威廉·阿克曼的“判定问题”（Decision Problem），质疑是否所有问题都是可判定。正如梅勒妮·米切尔教授所描述的那样，

【停机问题和数字时代的黎明，1930到1960年彻底改变了人类的历史】是否总有一个明确的程序可以判定一个陈述是否真实？

图灵首先发明了一台理论上的数字计算机，也就是图灵机。这台计算机在包含0、1和空格的无限长的磁带上运行。读写头从磁带上读取输入，程序根据一些规则，将一些输出写入磁带，然后停止或移动读写头，重复操作。
所有的问题都可以编码为0和1 ，读取遵循一组简单的规则。尽管效率低下，但这个系统可以用来计算任何可计算的问题。
但为了证明并不是所有的问题都是可计算的，并证明判定问题是错误的，图灵使用了一种叫作“矛盾证明”的方法。他一开始假设，有可能制造出一台图灵机，它可以计算出一个程序在给定某种输入后是否会停止或永远运行。然后他证明，这台机器会导致一个矛盾，所以不可能存在。
图灵提到的这个想法，后来被称为停机问题。今天的软件开发人员将其称为无限循环，这是他们在编写循环或递归函数时遇到的一个问题。下面是一个c++中无限循环的例子，

图灵的停机问题悖论表明，如果建立一个无限循环检测机器，当它运行时，会导致机器处于真和假状态。这一矛盾表明，不可能建立一个无限循环检测机器。我将在另一篇文章中详细描述停机问题。
这对数学和计算机来说都是开创性的工作。
图灵严格地定义了“确定过程”的概念。其次，他对图灵机的定义为电子可编程计算机的发明奠定了基础。然后，他证明了很少有人预料到的事实：可计算的东西是有限度的。
随后，图灵机引出了图灵完备性的概念，图灵完备性成为现代计算机和编程语言的基准。图灵完备机是一个简单的机器或程序，可以模拟任何图灵机的行为。基本来说，这意味着它可以解决任何可计算的问题。第一台图灵完备机是美国人在1945年制造出的。
20世纪30年代，图灵通过研究判定问题和描述图灵机为数字计算机奠定了基础。到20世纪50年代末，他对计算的深刻见解导致了现代数字计算机的诞生。 1954年，图灵因性取向问题被英国政府迫害，自杀身亡。遗憾的是，他永远看不到他在现代世界中扮演的关键角色。