software_1_lesson_2

无穷集和对角线法

简单概括就是，先构造实数序列（0-1），将自然数与实数序列一一对应，然后试图构造新的一个实数序列：将第一个实数的第一位小数取反，再将实数的第二位小数取反，依次构造出不等于任何已有实数序列的新实数。

Input: 一个巨大的 std::vector<std::string>，里面存了无数个长度无限的 01 字符串。

Algorithm: 遍历这个 vector，取第 i 个字符串的第 i 位，做 !bit 操作。

Result: 得到一个新的 string。

Assertion: find(vector.begin(), vector.end(), new_string) == vector.end() 永远为真。）

希尔伯特的野心：万能判定机

希尔伯特在 1928 年提出这个挑战时，他的设想非常宏大。
他想知道：是否存在一个算法（程序），当你输入任何一个数学命题（用逻辑符号写成），它都能在有限的时间内给你一个明确的答复： True 或 False

输入： 一段符合语法规则的“逻辑代码”（一阶逻辑符号系统）。

处理： 一个清楚明白的“验算程序”（算法）。

输出： return true; 或者 return false;。

罗素悖论

设命题函数 P(x) 表示 "x ∈\ x"，假设由性质 P 确定了⼀个类 A = { x : x ∈\ x } A ∈ A 是否成⽴？ 若 A ∈ A → A 是 A 的元素 → A 不具有性质 P → A ∈\ A ⽭盾！ 若 A ∈\ A → A 具有性质 P → A 是由所有具有性质 P 的类组成的 → A ∈ A ⽭盾！

哥德尔的不完备定理

「我不可在系统 T 内被证明」
G = 非Bew(G) （Bew(x) 返回值：如果能证明，则为“真”；否则为“假”）

停机问题

图灵通过 D 集合证明了：无论你的 Scanner 写得多么复杂，我都能根据你的 Scanner 源码 ，构造出一个 悖论程序 。

从 God_algo 出发，导出⼀个新的算法：

bool Satan_algo(char* program)
{
    if (God_algo(program, program)) {
        while (1);       // loop forever!
        return false;    // can never get here!
    }
    else
        return true;
}

如果程序确实停机，运行它，有限步内就能知道
如果程序不停机，我们只能永远等下去

状态	可判定（decidable）	可识别（recognizable）
能确认	能确认	能确认
⽆法确认	能确认	⽆法确认

停机问题：可识别，但不可判定

莱斯定理（rice）

简单来说就是： 只要你想写个工具来预判一个程序 “运行时的行为” ，这个工具就一定是 不可判定 的。

type	⼯具能做到	做不到
编译器类型检查	语法语义类型	运⾏时所有 bug
静态分析器	启发式检测	零误报零漏报
测试	验证已测⽤例	证明所有输⼊正确

图灵的通⽤计算机

(⼀台图灵机单凭自身就可以完成任何图灵机可能做到的任何事情)
五元组 初始状态 注视符号 改写符号 移动⽅向 变化状态

邱奇-图灵论题

The Church–Turing thesis states that a function is algorithmically computable if and only if it is computable by a Turing machine

Busy Beaver ( 忙碌的海狸 )

定义: 在所有只有 n 个状态（指令）且最终能停机的图灵机程序中，寻找那个运行步数最多的“冠军”。它是一个确定的自然数（比如 BB(4)=107），但它是一个不可计算函数。
Q: 为什么它“不可计算”?
前提： 想要算出 BB(n)，你必须先从所有程序中剔除那些“死循环（不停机）”的程序。但图灵停机问题证明了：不存在一个通用的算法能 100% 判定一个程序是否死循环。既然你分不清谁是“跑得久”谁是“死循环”，你就永远无法确定谁才是真正的 BB(n)。所以，BB(n) 无法通过算法得到。总之，BB(n) 是一个确定的数（就像宇宙中确实存在最忙的那只海狸）。但“得到这个数”的操作是违法的（因为它违反了停机问题的逻辑底层）。
应用：
Adam Yedidia 把哥德巴赫猜想编码为有 4888 个状态的 Busy Beaver 图灵机：如果让这台图灵机跑起来，只要跑了 BB(4888) 步后还没有停机，那就证明了哥德巴赫猜想为真！他还写了⼀个验证黎曼猜想的图灵机，有 5372 个状态

⾃然数的⽪亚诺公理系统

1 1是⾃然数
2 每⼀个确定的⾃然数 a，都有一个确定的后继数 a’，a’ 也是⾃然数
3 如果⾃自然数 b、c 的后继数都是 a，那么 b = c
4 1 不是任何⾃然数的后继数
5 任意关于⾃然数的命题，如果证明了它对 1 是对的，⼜假定它对 n 为真时，可以证明它对
n’ 也真，那么命题对所有⾃然数都真。（数学归纳法）
(若将 0 也视作⾃然数，则公理中的 1 要换成 0。)

原始递归函数

常数函数 0 元常数函数 0 是原始递归的
后继函数 S 接受一个参数，返回后继数 S(n) = n + 1
投影函数P 接受 n 个参数，返回第 i 个

加法的递归定义

直觉上我们把加法递归定义为：
add(0,x) = x
add(n+1,x) = add(n,x) + 1

严格的原始递归定义：
add(0,x) = P₁¹(x)
add(S(n),x) = S(P₁³(add(n,x), n, x)) (= S(add(n, x)))
(S(n) 就是“后继函数”，它的唯一功能就是把自然数 n 变成它的下一个数，也就是 n+1)

减法的递归定义(同理)
⾸先定义前驱函数：
pred(0) = 0
pred(S(n)) = P₂²(pred(n), n)
然后定义有限减法（截⽌到 0）：
sub(0,x) = P₁¹(x)
sub(S(n),x) = pred(P₁³(sub(n,x), n, x))

阿克曼函数

它证明了：存在一种逻辑，它比任何多项式、指数、阶乘都要高级。这迫使科学家定义了更广义的“全递归函数”。但它仍是可计算函数。

μ算子

Q: 原始递归（for 循环）不够用？
在原始递归的世界里，所有的循环都是这样的：for (int i = 0; i < n; i++) { ... }
在循环开始之前，你就已经知道它最多跑 n 次。它必然会停机 , 它被叫全函数（Total Function）。
但是阿克曼函数告诉我们，有些计算逻辑极其复杂，你根本没法预先拍脑袋说“它一定在 n 步内算完”。所以需要引入 μ算子。

μ 算子： 引入了无界搜索（Unbounded Search）。它的逻辑用 C++ 伪代码写出来就是：

int μ_operator(int x) {
    int y = 0;
    while (f(y, x) != 0) { // 只要结果不是 0
        y++;               // 就一直试下一个 y
    }
    return y;              // 找到了，返回最先找到的那个 y（y的最小值）
}

一大典型的区别（μ算子与原始递归之间）：
（全函数（total） ：对所有输⼊都有定义，必然停机
（部分函数（partial）： 仅对部分输⼊有定义，其余不停机）

Q:为什么我们需要这个“危险”的算子？
因为只有允许了“不停机”的可能性，我们的计算系统才拥有了模拟宇宙中所有逻辑的能力。这就是著名的 “邱奇-图灵论题” 的数学表达：所有能被人类大脑或计算机处理的算法，本质上都可以用“原始递归 + μ 算子”来表达。

lambda 演算（暂时看不懂，略去）

图灵机：

⼀台图灵机是⼀个七元有序组 （现代标准定义）（（五元组（图灵原始形式）））

转移函数 的具体展开。每一行的格式都是： 当前状态, 读到的符号 -> 新状态, 写入的符号, 移动方向

图灵机与寄存器的等价：

纸带 = 数字想象图灵机的纸带上有无限 de 0 和 1。左侧纸带 m：把左边所有的 0 和 1 看成一个二进制数。当前格子 s：当前读写头下的数字。右侧纸带 n：把右边所有的 0 和 1 看成另一个二进制数。关键点来了：读写头右移，相当于把 n 的最后一位“挤”给了 s，把旧的 s “挤”进了 m 的末尾。在数学上，往末尾塞一个数就是 乘以 2 再加这个数；从末尾拿掉一个数就是 除以 2 取余数。2. 读写头移动的“数学公式” (PPT 61页)当你右移一格时，发生了三件事：左边变大了：m’ = 2m + s（旧的 s 贴到了 m 的屁股后面）。当前变了：s’ = n mod 2（从右边的 n 里抠出最后一位）。右边变小了：n’ = n / 2（n 删掉了刚才被抠走的那一位）。结论：图灵机所有的“左右移动”和“改写符号”，在寄存器机里全都变成了加、减、乘、除。

两个寄存器是怎么做到的？ 这里用到了哥德尔数（Gödelization）的天才想法：我们可以用素数的幂次方来打包数据。比如用一个寄存器 r 存储一个巨大的数字：r = 2^m * 3^s * 5^n。 想知道 s 是多少？看 r 能被 3 整除几次。想改 s？通过乘除法调整 3 的指数。另一个寄存器 z 永远保持为 0，专门用来配合 decjmpreg 实现无条件跳转。

如何实现“加法”？
假设你想算 A + B，结果存在 B 里。你的策略是：只要 A 还没空，我就从 A 里拿走一个，往 B 里放一个。 目标：B = B + A

LOOP: decjmpreg A, NEXT    ; 尝试从 A 拿走 1，成功则去 NEXT，失败（A=0）则跳出
      jmp HALT             ; A 拿空了，停机
NEXT: inc B                ; 给 B 加 1
      jmp LOOP             ; 回去继续拿
HALT: hlt

没有用 ADD 指令，只用 inc 和 dec 就完成了加法。

如何实现“乘 2”？（双倍搬运）
假设要把 A翻倍，结果存入 B。策略：每从 A里拿走 1 个，就往 B里丢 2 个。 目标：B = A * 2

L3: decjmpreg A, L4        ; 从 A 拿走 1 个（成功去 L4，失败去停机）
    jmp HALT
L4: inc B                  ; 第 1 个 inc
    inc B                  ; 第 2 个 inc（疯狂双倍！）
    jmp L3                 ; 回去继续，直到 A 被搬空
HALT: hlt

如何实现“除以 2”？（分批搬运）
这是最巧妙的。你想知道 A 里面有几个 2，余数是多少。我每次尝试从 A 里连续拿走 2 个球。如果能拿够 2 个，我就给商（Result）加 1；如果最后只剩下 1 个拿不够了，那它就是余数。 目标：Result = A / 2, Remainder = A mod 2

START:  mov Remainder, 0    ; 先假设余数为 0
LOOP:   decjmpreg A, TRY_2  ; 尝试拿第 1 个
        jmp FINISH          ; 1 个都拿不出，整除，结束
TRY_2:  inc Remainder       ; 暂时记余数为 1（因为拿出了 1 个）
        decjmpreg A, GOT_2  ; 尝试拿第 2 个
        jmp FINISH          ; 拿不出第 2 个，余数确定是 1，结束
GOT_2:  mov Remainder, 0    ; 拿够了 2 个，余数归零
        inc Result          ; 商加 1
        jmp LOOP            ; 继续下一轮尝试
FINISH: hlt

怎么实现 jmp 用一个 while 循环：只要 reg 不是 0，就一直 dec 它。最后它一定会变成 0。这就是那个寄存器 z 的妙用。我们规定 z 永远是 0。当你执行 decjmpreg z, lab，因为它一定是 0，所以它永远会直接跳转到 lab。