欢迎来到机器与计算建模的世界！
各位计算机科学家，你们好！本章听起来可能非常理论化，但实际上，它探讨的是构成所有计算机、手机和电子游戏底层逻辑的基本准则。
我们将探索如何利用简单的理论机器来表示复杂的现实系统。理解这些基本的构建块至关重要，因为它们定义了计算机能够做什么以及不能做什么。如果起初觉得有些晦涩也不要担心——我们会用生活中的例子把一切拆解开来！
第 1 节：什么是计算建模？
理解模型的需求
在计算机科学中，计算模型 (Computational Model) 是对现实世界过程、系统或对象的简化表示。我们利用这些模型来研究复杂系统，而无需在现实中进行构建或实验。
可以把它想象成在制造全尺寸汽车之前先制作一个汽车模型。这个微型车（模型）可以帮助工程师以低成本、高效率的方式理解物理特性、性能表现及设计缺陷。
计算建模的主要用途：
- 预测 (Prediction)： 预测接下来会发生什么（例如：天气预报）。
- 理解 (Understanding)： 帮助我们观察复杂系统是如何相互作用的（例如：交通流量建模）。
- 测试 (Testing)： 在安全环境下尝试各种场景（例如：在模拟器中测试飞行控制）。
- 设计 (Design)： 在编写实际程序代码之前制定计划。
核心要点： 模型将复杂的世界简化为计算机可以处理的、可控的规则。
第 2 节：有限状态机 (FSMs)
引入最简单的机器模型
最常见且最容易理解的计算模型之一就是有限状态机 (Finite State Machine, FSM)。FSM 是一种在任何给定时刻只能处于有限且固定的几种情况（称为状态）之一的机器。
机器会根据它接收到的特定输入在这些状态之间进行切换。这种切换被称为转换 (Transition)。
FSM 的三个核心组成部分：
- 状态 (States)： 机器当前的状况或条件。状态的数量始终是有限的。
- 输入 (Inputs)： 触发机器做出反应的信号或数据。
- 转换 (Transitions)： 决定机器在接收到特定输入后跳转到哪个状态的规则。
现实生活示例：交通信号灯
交通信号灯是有限状态机的绝佳例子。
想象一个控制单车道交通的交通灯。
状态：
- 状态 1：红灯（停止）
- 状态 2：红黄灯（准备通行）
- 状态 3：绿灯（通行）
- 状态 4：黄灯（准备停止）
转换（使机器跳转到下一个状态的因素）：
- 如果灯处于红灯状态，输入（时间经过）将导致转换至红黄灯。
- 如果灯处于绿灯状态，输入（时间经过）将导致转换至黄灯。
请注意，红灯不能直接跳到绿灯——它必须遵循设定的转换路径！
✅ 快速回顾：FSMs
FSM 非常适合为具有固定规则和有限选项的系统建模，例如简单的用户界面、验证检查（如检查密码是否有效）或控制系统。
第 3 节：通用模型——图灵机
阿兰·图灵与计算的极限
虽然 FSM 对于简单系统非常有用，但 20 世纪 30 年代，数学家阿兰·图灵 (Alan Turing) 开发了一种理论模型，它能够执行现代计算机可以执行的任何计算任务，无论其有多复杂。这个模型被称为图灵机 (Turing Machine, TM)。
图灵机不是你可以买到的物理计算机；它是一个思想实验，用于精确定义什么是计算，以及哪些问题是可以由机器解决的。
图灵机的构成是什么？
图灵机结构出奇地简单，但功能却异常强大。它由三个主要部分组成：
- 无限磁带 (Infinite Tape)： 这相当于机器的内存。它被划分为一个个单元格，每个单元格保存一个符号（通常是 1 或 0，或者空白符）。关键在于，磁带长度是无限的，意味着机器永远不会耗尽内存。
- 读写头 (Read/Write Head)： 该装置一次悬停在磁带的一个单元格上。它可以：
- 读取当前单元格中的符号。
- 写入一个新符号到当前单元格。
- 向左或向右移动一个单元格。
- 状态寄存器 (State Register)： 用于保存机器当前的状态（类似于 FSM 中的状态）。状态决定了读写头接下来的动作。
分步过程： 机器读取符号并查看当前状态。根据这两者（符号 + 状态），它遵循规则进行：1) 写入新符号，2) 移动读写头（左/右），以及 3) 切换到新状态。它会不断重复此过程，直到进入“停机 (HALT)”状态。
为什么图灵机很重要？
当今的任何计算机系统，从最快的超级计算机到最简单的智能手机，在功能上都等同于图灵机。
- 能够模拟任何其他图灵机的机器被称为通用图灵机 (Universal Turing Machine, UTM)。
- 这一概念证明了单一类型的标准机器可以解决所有可计算的难题。这就是为什么你的笔记本电脑既能运行游戏，又能运行电子表格和网页浏览器——因为它是一台 UTM！
💭 你知道吗？图灵完备性
如果一种编程语言或计算设备的功能强大到足以执行任何图灵机可以完成的计算，它就被称为图灵完备 (Turing Complete)。你所听到的几乎所有通用编程语言（如 Python 或 Java）都是图灵完备的。
第 4 节：可解性与计算的极限
机器能解决哪些问题？
图灵机模型帮助我们确定一个问题是可计算的 (computable)（可由机器解决），还是不可计算的 (non-computable)（无法通过算法解决）。
对于一个可计算的问题，我们必须能够创建一组有限的、清晰明确的步骤（即算法），让图灵机能够遵循这些步骤得出解决方案，并最终停机 (halt)。
常见陷阱：停机问题
不可计算问题最著名的例子之一就是停机问题 (Halting Problem)。
停机问题问的是：是否有可能编写一个通用算法，能够检查任何其他程序及其输入，并正确判断该程序最终是会结束（停机），还是会陷入无限循环永远运行下去？
阿兰·图灵证明了这样的算法是不存在的。机器不可能可靠地预测*任意*其他程序是否会停机。这为计算机的能力设定了一个基本的限制！
记忆小贴士： 计算机固然强大，但它们也有局限性！停机问题证明了计算机无法完美预测所有其他程序的未来行为。
关键点总结
我们使用计算模型（如 FSM 和图灵机）来定义、简化并测试现实系统。
- 有限状态机 (FSM) 使用有限的状态和预定义的转换来对简单过程建模。
- 图灵机 (TM) 是计算的理论定义，使用无限磁带和读写头。它证明了单一的简单机器可以执行任何可解决的任务。
- 停机问题表明计算存在极限；某些逻辑问题从根本上是不可计算的。
请继续练习如何在简单场景（如电灯开关或挂锁密码）中识别状态和转换。你已经掌握了定义现代计算的核心概念！做得好！