Theory of Computation

计算理论(Theory of Computation) 是计算机科学底层、最数学化的一块基础理论。它研究的是：

• 什么可以被计算
• 计算需要什么模型
• 哪些问题根本算不出来
• 能算出来的问题，代价有多大

它本质上是在研究：计算这件事本身的边界

计算理论的三大核心

自动机理论(Automata Theory)

这是“计算机器”的抽象模型研究

它研究：

• 一个机器如何读取输入
• 如何根据状态变化
• 如何接受/拒绝字符串

最经典的是：

• FSM（有限状态机）
  • 游戏AI状态切换
  • 编译器词法分析
  • UI流程
  • 网络协议
  • 正则表达式引擎
• DFA（确定有限自动机）
  • 状态唯一确定，没有歧义
• NFA（非确定有限自动机）
  • 一个输入可以同时走多个状态，理论上更抽象，但NFA和DFA计算能力相同
• 正则语言
  • 自动机理论中的一条巨大主线：正则表达式 -> 有限自动机 -> 形式语言

可计算性理论(Computability Theory)

本质问题：是否存在问题，本质上无法被计算机解决
答案是：有，而且很多
这说明，计算是有极限的，不是性能问题，不是算力问题，而是宇宙级别的不可计算

图灵机(Turing Machine)

核心模型：Alan Turing 提出的理论机器

它极其简单：

• 一条无限纸带
• 一个读写头
• 一套状态规则

但能模拟任何现代计算机
因此，图灵机 = 计算的数学本质

停机问题(Halting Problem)

最著名问题：是否存在一个程序，能判断另一个程序会不会停
结论：不存在。这是数学证明出来的

计算复杂性理论(Complexity Theory)

核心问题：能算的前提下，代价是多少

比如：

• 时间复杂度
• 空间复杂度
• 指数爆炸
• NP问题

P vs NP 计算机科学最大未解问题之一
核心：

P:
容易求解的问题

NP:
容易验证的问题

容易验证是否意味着容易求解？没人知道

复杂度类