Note12 Computability

• 笔记

• Liar's Paradox 撒谎者悖论 --- Paradox是构造反证的一种重要方法

  • 实际上撒谎者悖论并不是真正的paradox
  • 一个真正的悖论 This statement is false, self-reference导致了悖论
  • 罗素的barber paradox也是一种paradox

• Self-Replicating Programs

  • 我们可以使用自引用来设计一个输出自身的程序吗？可以
  • Quines and the Recursion Theorem
    • Quines：一个打印自身的程序被称为quine(奎因是以哲学家和逻辑学家威尔德·范·奥曼·奎因的名字命名的，正如道格拉斯·霍夫斯塔特在其著作《哥德尔、艾舍尔、巴赫：永恒的金色螺旋》中所普及的那样)
    • Recursion Theorem：递归定理指出，对于任何程序 P(x, y)，我们总能将其转换为另一个程序 Q(x)，使得 Q(x) = P(x, Q)，也就是说，Q的行为与P相同，如果P的第二个输入是程序Q的描述。在这个意义上，我们可以将Q视为P的“自我意识”版本，因为Q本质上可以访问其自身的描述。

• The Halting Problem

  • 是否存在计算机无法执行的任务？例如，在编译程序时，我们可能会问以下基本问题：它是否会进入无限循环？1936年，艾伦·图灵表明，没有程序能够执行这项测试
  • Halting Problem 是不可计算的Uncomputable
  • TestHalt(P,x)是不存在的，利用Turing历程的self-reference导出paradox进行反证(证明任意程序任意输入上的停机-->不存在)
  • TestEasyHalt(P)也是不存在的(证明任意程序在特定输入上的停机-->不存在),由该版本构造TestHalt(P,x)因此也不存在

• Godel's Incompleteness Theorem --- 两个关键问题不完备补充

  • Is arithmetic consistent? 算术是一致的吗
    • 算术一致性的定义：是否有可能同时证明一个命题P及其否定¬P。如果可能，则称算术是不一致的；否则称算术是一致的
  • Is arithmetic complete? 算术是完备的吗
    • 算术完备的定义：算术中每一个真命题是否都可以被证明？如果如此，则称算术是完备的

  • 1930年库尔特·哥德尔证明了事实恰恰相反：任何==足够丰富以形式化算术的形式系统==，要么是不一致的（存在可以被证明的假命题），要么是不完备的（存在无法被证明的真命题）

  • Godel's proof 的概要

    • 假设我们有一个形式系统 F，它由一组公理和推理规则组成，并且假设 F 足够表达，以至于我们可以用它来表达所有的算术
    • 现在假设我们可以写出以下陈述：S(F) = “这个陈述在F中不可证明。”

    • 一旦我们有了这个声明，有两种可能性：

      1. 案例1：S(F)是可证明的。那么陈述S(F)是真的，但通过检查陈述本身的内容，我们发现这暗示S(F)不应该被证明。因此，在这种情况下，F是不一致的
      2. 案例2：S(F)不可证。通过构造，这意味着陈述S(F)是真实的。因此，在这种情况下，F是不完备的，因为存在一个真实的陈述（即S(F)）是不可证的

    • 为了完成证明，现在只需要构造这样一个陈述S(F)。这是哥德尔证明的难点部分，它需要将符号和命题巧妙地编码（所谓的“哥德尔编号”）为自然数

层面	我们做的事	是否属于系统
元语言层（meta-level）	我们说“PA 是不完备的”、“存在不可证明的真命题”	❌ 在系统之外（我们用自然语言描述）
对象语言层（object-level）	系统自己通过符号和算术表达这些命题	✅ 系统内部（纯形式推理）

• Halting Problem 与 Godel's proof
  • 利用Halting Problem 编码Godel‘s proof

---