自指与自复制教程.pdf

自指与自复制 Jake 集智俱乐部 《GEB》读书会,2011.2.27 提纲  哥德尔定理的回顾  哥德尔定理的推论  自打印程序  自复制自动机  印符遗传学  递归定理  冯诺依曼的自复制自动机理论 提纲  哥德尔定理的回顾  哥德尔定理的推论  自打印程序  自复制自动机  印符遗传学  递归定理  冯诺依曼的自复制自动机理论 哥德尔定理回顾  哥德尔不完全性定理：  任何具备与 《数学原理》同等能力的形式系统 都不能兼备：  一致性：A 和~A都是该形式系统的定理；  完备性：任何真命题都是系统中的定理。 哥德尔证明  哥德尔证明的关键：  用系统中支持的方法，构造了一个哥德尔 句子G  G=“G不是系统中的定理”  所谓系统中支持的方法：  哥德尔配数（为每个谓词命题编号）  Quine 函数Q(x)  是定理数的表述 对哥德尔句子的理解  G=“G 不是系统中的定理”  如果G是系统中的定理，也就是说可以构造一 个机械的步骤，从公理出发运用推理规则得到 G ，也就是接受字符串“G 不是系统中的定 理”，此字符串可以进一步被替换成~G ，这 样G与~G共存于系统中，一致性被破坏；  如果G 不是系统中的定理，那么根据观察者的 判断，G是一条真的判断。所以，G就是一个 真的命题，但却不是系统中的定理，所以该系 统是不完全的 提纲  哥德尔定理的回顾  哥德尔定理的推论  自打印程序  自复制自动机  印符遗传学  递归定理  冯诺依曼的自复制自动机理论 第十五章跳出系统  补救方法：  不争论G是否是系统中的定理了，而是把它作 为一条公理纳入到系统中；  但是，运用Godel 的方法，我们针对公理系统 A’={原公理集A,G} ，又可以构造出一个哥德尔 句子G’ ；  当然，你可以将G’纳入，形成新的公理体系 A’’={A,G,G’} ，但是我们还可以用类似的方法得 到G’’  …… 分叉图  于是，这个不断补救的过程就能形成分叉 图： 思考：这一过程意味着什么？  （2）、如何利用观察者？  既然理解“自我”和程序意义的关键因素就是观察者，那么我们能否开发一种方法来系统地 应用只有观察者才具备，而普通的计算机程序却没有的能力呢？答案应该是肯定的，我们将说明利 用上一章提到的图灵机-观察者模型，原则上是可以将计算机屏幕前面的观察者利用起来的。  假设观察者- 图灵机模型中的图灵机就是一个可以根据某个简单特征来判断程序X作用到y 上 是否停机的程序H(x,y) 。（例如，程序H可以简单地根据x 中是否包含“do while true”语句来粗暴地 判断X(y) 是否停机（输出0为不停，1为停），显然这个程序的判断是不完备的）。之后，我们便可 以根据那个破坏性的自指程序D(z):=1-H(z,z) ，而找到一个输入d （即D 的源程序）。使得这个时候 H(d,d)所给出的判断与我们观察者看到的程序D(d) 的行为完全相反。注意这一步的程序H和程序D都 是良定义的计算机程序，可以用图灵机自动产生，完全不需要观察者的涉入。  接下来，我们知道H(d,d)一定给出一个错误的判断（根据d 的定义）。但是，图灵机-观察者 模型中的观察者必然能够看出D(d) 究竟是否停机。根据前面的论述，观察者可以做出正确的判断。 于是，我们便可以让观察者开始介入，让他手动地修改图灵机程序H为H’ ，使得H’(d,d)能够给出正 确的判断，即D(d)是否停机。注意，此时