课程引论¶

说是引论数大模型教不来的

每个学科的基本问题¶

Computer Science 的基本问题：

直觉上"什么都能算"（打游戏、大模型……），但跳出来看：人心能不能计算？一百年前"计算"这个词本身都还没有定义。这门课就是回到计算机科学最初的基石——计算的本质。

这门课的目的：

判定标准：一个问题若能被图灵机形式化描述、并且图灵机最终停机 → 可计算；不能被图灵机建模 → 不可计算
图灵机是人造的数学模型，而"问题"是客观存在的东西——两者"等价"这件事既无法证明、也无法证伪（找不到反例，但也证不了普适），这正是图灵机厉害的地方
尽管形式极其简单，它是一切计算机算法最本质的抽象模型：大模型、自动驾驶、王者荣耀……最终都可以抽象成这么一个"玩具"；你的笔记本、手机都是图灵机的一种具象化实现

课件 · 图灵机的 Wikipedia 定义与一种具象化

定义（图灵机，1936）→ 实现（冯·诺依曼架构的通用计算机）→ 应用（以大模型为代表的 AI）

课件 · 计算的定义、实现与应用

箭头是单向的：图灵机不一定非要用冯·诺依曼架构实现
Hardware lottery（DeepMind）：AI 的成功很大程度押注在 GPU 这种图形渲染芯片上——恰好发现它能训神经网络，是历史路径依赖（"左脚踩右脚"），不是必然
先进计算（存内计算、量子计算、光计算、生物计算、脑机计算等）的动机之一：换一种载体去实现计算

二战破译 Enigma：图灵基于图灵机的思想参与设计破译机器（Bombe），把"按固定规则人工套模板"变成自动化枚举——图灵机最早的落地应用之一
图灵 1936 年论文 《On Computable Numbers, with an Application to the Entscheidungsproblem》（论可计算数及其在可判定问题上的应用），时年 24 岁；原始动机之一：想造一台机器自动枚举实例来验证黎曼猜想 → 计算数论 (computational number theory) 的先驱
当代回声：OpenAI 声称用下一代模型 88 小时证明了 Navier–Stokes 方程相关难题（百万美元问题之一）——本质仍是"基于图灵机去证明数学问题"，只是实现的版本能力强了很多；由此引出的 AI 创造力界定、训练数据泄露、学术伦理是开放问题

Problem → 形式化 (Sets of Symbols) → Language ↔ Computational Model

课件 · 课程主线：语言与计算模型的等价关系

Tip

图灵机是这门课最重要的内容，重点考察： - Basic Concepts & Properties - Foundations for its Invention

图灵机实在是太抽象了，所以课程会花超过一半的讲课时间在 foundation（FA、PDA 和数学基础）上；但考试的重点在图灵机本身。前面讲得多、考得少，反而越要掌握——不然第四、五章跟不上。

总评 = 平时 30% + 期末闭卷 70%（三个平行班考核标准一致）
平时：随堂限时测试，例如 10 分钟 20 道判断/选择（约 30 秒一题，来不及查大模型）；迟交按迟到时间乘 0.5~0.8 的系数
期末：闭卷、英文题目，选择 + 判断 + 大题，题量大、时间紧（2 小时）
- 重在理解课程思想，只背公式和推导拿不到高分；理解的基础上能背多少背多少
教材：Elements of the Theory of Computation（Lewis & Papadimitriou，1981 第一版 / 1995 第二版），推荐读英文原版——中文版可辅助理解，但最终要回归英文的严谨表述