原视频作者链接：

【从图灵机到 Lisp：编程语言的起点｜编程语言发展史 #1】

观前提示：

为了让讲解更加直观，作者将编程语言的发展过程抽象成为：

为了解决怎样的问题 - 提出/发明怎样的概念/编程语言来进一步解决这些问题

即 提出问题 - 发明结构 - 解决问题

编程语言的起点

1. 图灵

总结：图灵思想的贡献

  • 图灵机 为计算提供了最简洁的模型。

  • 图灵完备性 告诉我们不同编程语言和系统在能力上的等价。

  • 停机问题 揭示了计算的极限：它不仅说明了机器能算什么，也清楚地划定了机器永远无法算出的范围。

这是人类第一次为 计算的能力与局限 画下了清晰的边界。

1936 年， 图灵

他思考的核心问题：究竟什么可以被计算？有没有一种最简洁的模型可以揭示计算的本质？

于是提出了 图灵机。

图灵机

设想中的 图灵机 结构：

  • 一条无限长的纸带 —— 就像无限的内存或变量空间，用来存储数据
  • 一个读写头，能在纸带上移动 —— 像数据指针那样读取/写入符号
  • 一张状态转移表 —— 最早的程序逻辑，定义在不同状态和符号下该执行什么操作
  • 后来所有的计算机设备在计算能力上与图灵机等价；它们都能模拟通用图灵机。
图灵完备性
  • 如果一个系统能够模拟图灵机，就称其 图灵完备。

这意味着，从 Python、C、JavaScript，到 Excel，在理论上都能表达同样复杂的计算过程。

差别不在于 “能不能算”，而在于 “计算效率如何，表达是否简洁”。

停机问题

图灵还提出了一个更深刻的问题 - 停机问题

是否存在一个万能程序，能够判断任意程序最终会不会停机？

结论是：不存在这样的通用算法。

借助 理发师悖论 来理解这一点：

想象一个小镇，有一位理发师，只给村里”不给自己理发的人理发”。

  • 如果理发师给自己理发，那他就是给自己理发的人，就违反了他的规则。

  • 如果他不给自己理发，那他就是不给自己理发的人，就应该给自己理发。

这就陷入了逻辑矛盾。

回到停机问题，图灵的推理与此类似。

首先，假设存在一个万能判定器H，可以判定任意程序是否停机；

接着，构造一个特殊的程序D。它的规则是：

  • 如果H说它会停机，D就偏偏不停；
  • 如果H说它不会停机，D就立即停下。

最后，当我们让D判断自身时，矛盾出现了：无论判定器H给出怎样的答案，答案都会与事实相反。

这意味着，所谓的万能判定器并不存在。、

更严格的表述是：

  • 对于某些特定程序，我们仍然能分析出是否停机；

  • 但不存在一个通用算法，能对所有程序都给出正确答案。

随着第一批电子计算机的诞生，人类进入了真正的可编程的时代。

最初，所有的指令必须直接写成二进制。每一道程序都从手工排列的0与1开始。

为什么是0和1？

因为在最底层，计算机就是无数个开关，开关只有两种状态——通电或断电；在电路里对应高电平与低电平，换成符号就是1和0。

这些开关组成逻辑门——与门、或门、非门。

正是这三种最基本的逻辑，构建出加法器、乘法器，乃至整个CPU。

这就是为什么0与1足以表达所有计算。