前些日子查资料的时候发现逻辑学家 George Boolos (不是 boolean 类型的 George Boole) 曾经给出过 Gödel 定理的一个新证明. 看了之后觉得十分有趣.

Review of Gödel's Proof

关于 Gödel 的原始证明, 网上已有许多解释, 如刘未鹏的这篇文章. 这里再从数理逻辑角度简单回顾一下, 因为 Boolos 的证明用了许多 Gödel 的思想.

证明的第一步是建立 Gödel Numbering, 也即建立一套编码系统, 使得形式系统中任意公式可与自然数一一对应. 这种思想及其方法在有了计算机的今天是十分轻易的, 在 Gödel 的文章里, 他用了不同素数表示形式系统中的最基本符号, 从而实现了这一点, 这种方法后来被称为 Gödel Numbering.

在知乎上看到这么一道题, 原题描述的不太严谨, 其大意是:

一幢 200 层的大楼, 给你两个鸡蛋. 如果在第 n 层扔下鸡蛋, 鸡蛋不碎, 那么从前 n-1 层扔鸡蛋都不碎. 这两只鸡蛋一模一样, 不碎的话可以扔无数次. 已知鸡蛋在 0 层扔不会碎.

提出一个策略, 要保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

貌似中文标题的都偏吐槽向.

现状

清华的 "工科数学基础课", 课堂教学方式大致都是 抄课本.

当然, 抄有不同的抄法. 有的老师抄在黑板上, 有的抄在一学期改一页的 ppt 上. 一般他们在抄的同时会把文字部分匹配出来读一读, 遇到公式的话有的会读, 有的用指示代词替换掉了, 每个知识点下面抄一个例题. 总之像是个可以写程序控制机器人来完成的活.

没错, 这篇文章其实是 Cantor, Gödel, Turing 这个主题. 我发现只要关于他们的东西都很容易让我看 high..

最近在看那本 The Annotated Turing. 书中第三章以 David Hilbert 为主线, 介绍了 20 世纪初的几十年里数理逻辑与集合论的发展. 想一想的话, Hilbert 的确是将 Cantor, Gödel, Turing 联系起来的关键人物, 然而这段历史我以前知道的并不细致, 而且关于 Hilbert's Program, Hilbert's Problems 的故事各个地方说的都乱七八糟的自己也不清楚了, 于是做个记录.

今天听老师说了一些关于 Yitang Zhang 的八卦相当感慨

因为文革原因, 上北大的时候已经 20 多岁了

78 级北大数院公认最优秀的毕业生

硕士在北大师从老潘学解析数论

84 年丘先生回国到处演讲招学生, 挑选了很多优秀的中国学生, 当时身为 San Diego 院长的他一年招了 20 多个中国学生去 San Diego, 他们几乎都成为了当今最牛的中国数学家

人智课一次作业是写一个 A* 程序算八数码问题的最优解. 一个自然的问题是, 什么样的初始状态有解?

一个熟知的结论是, 将矩阵元素排成一排, 忽略空格, 当且仅当逆序对个数为偶数时此问题有解.

必要性很好证明, 因为观察可知所有的移动操作不会改变逆序对个数的奇偶性. 那充分性呢?

要证明充分性, 需要将矩阵用另一种方式展开成一排:.

面试中曾经遇到这么一道概率题:

一只猴子随机敲键盘上的 26 个字母, 期望在多少次之后能首次打出 "hulu"?

当时只是直觉觉得答案应该是 , 没有想出很好的做法. 想出来的唯一方法是列一个四元线性方程组, 四个变量定义如下, 有点像 Markov Chain 的感觉:

1. 打出 hulu 的期望次数
2. 已打出 h, 从现在开始算打出 hulu 的期望次数
3. 已打出 hu, 从现在开始算打出 hulu 的期望次数
4. 已打出 hul, 从现在开始算打出 hulu 的期望次数

概率论课, 一项作业是写篇小论文. 错排数是高中就总结过的, 恰好概率论某次习题课还讲到, 就花了一周时间又整理了下错排数 (Rencontres Number) 有关的东西. pdf 放在 github.

对于排列 , 设 是它的不动点集合:

设 是所有可能 元排列的集合, 则错排数 可定义如下:

数据结构课上, 比较二分查找与 Fibonacci 查找. 举例时为了方便, 就让数组长度是 8, 因为 8 既是 2 的幂又是 Fibonacci 数, 方便演示算法. 邓俊辉老师随口问了一句像这样的数还有没有呢. 答案是没有的.

Fibonacci 数有一个有趣等价条件: 是 Fibonacci 数当且仅当 中某一个数是完全平方数.

• 必要性很好证. 验证如下等式: 其中 是以 定义的 Fibonacci 数, 是以 定义的 Lucas 数

• 充分性: 于是 为 中的单位元, 那么 , 就可以得到 了.

有了这个性质之后, 只需要考虑 有没有非平凡解即可. 这个很容易就.. 略了.

后来发现一个很强的 Carmichael 定理, 可以直接秒这道题. 定理的内容是: 对每个 必定包含一个没有在之前的 Fibonacci 序列中出现的因子.

在翻 Matrix67 的思考的乐趣的时候, 看到集合论那里, 依次证明了有理数, 代数数, 可计算数, 可定义数的可数性, 甚舒畅. 然后用经典的 Cantor's Diagonal Argument 证了实数的不可数性, 并说明了此方法对有理数不可用, 因为对角线生成的新数未必是有理数.

然后我想, 对角线法用在可计算数上似乎也可以啊.. 假设可计算数可数, 排成一列 之后, 按照对角线法取出一数, 保证取出数 满足 , 则 也没有被列出. 而进一步, 如果我们规定取数时的对应法则 , 令 无不动点, , 那么取出的新数也就是可计算的了. 那按照 Diagonal Argument, 可计算数不就不可数了?