主题：谈谈陈经的"预测和自由意志"的例子 -- CatOH
- 复 复杂到什么程度
家园 数论 可以定义数论命题就可以了这个说法和自指等价吗？
- 复 数论
家园 我觉得不是太一样 其实关键问题不在自指，而在于无限集合的阶，算法集合是可数无穷多的，而结果的集合是不可数无穷多。所以无法形成一一映射。康托对角线法就是这种不一致的体现。
凭印象说的，未必正确...
- 复 我觉得不是太一样
家园 花，问专家 印象里“算法集合”和图灵机的“可递归的函数”应该是等价的。而递归总是出现自指，所以我一直以为“可以定义数论命题”和“可以自指”和“可以实现if...goto的算法”三者是等价的。不知我理解是否有误？
- 复 花，问专家
家园 简单的说一下我的理解 一个形式系统FS，如果在FS中蕴含了皮亚诺的五条关于整数公理，那么就说它可定义数论命题。这五条公理是：
· 1是自然数；
· 每一个确定的自然数a，都有一个确定的后继数a' ，a' 也是自然数；
· 如果b、c都是自然数a的后继数，那么b = c；
· 1不是任何自然数的后继数；
· 若任何集合X, 如果1属于X, 并且n属于X可以推出n'属于X，另外X不包含其他的元素，则X等同于自然数集合。
Godel证明，如果FS可定义数论命题，则FS要么是不一致的（可能有A 和非A两个命题同时存在），要么是不完备的（其中有一个用FS表述的命题，其真假性无法判定）。
所谓自指没有明确的数学定义。事实上能够定义出罗素悖论的系统可以很简单，反过来说，可以修改公理体系来避免罗素悖论，但这个体系仍然可以包含数论命题。
至于if…then…goto则属于更基本的算法描述上，它不是形式系统的组成部分。或者可以说它是一种简写，方便人们对算法的理解而存在的。
家园 忙死了，好久没有上来，花谢专家 受教了，花谢:D
另有问题：
Godel的证明是否是构造了一个自指的命题？（印象里似乎是这样的）
可以定义皮亚诺的五条关于整数公理对我们的逻辑有什么要求？
我需要去好好看看书了，hehe
- 复 花，问专家
家园 不敢当 这三个概念应该是不同的，等有时间我来说一下我的理解，大家研讨一下。
- 复 请教
家园 ID读作亲氧化猫，hehe 所谓复杂到一定程度，就是说此系统能够表达自指的叙述，比如这一类的命题：“CatOH无法证明此命题”。
这个就是一个我无法证明的命题。但是对于你来说，明显可知此命题为真--这并不能推出你总是胜过我的，仅仅是因为对于此命题我们不是对等可比较的双方。
希望解释清楚了...
家园 嗯…… 关键是自指，对吗？
就是说，系统里面可以定义定义这个系统的人(不一定是人了，也可能是上帝啥的，总之代指创造这个系统的东东)，yes？
-------------
咋想起用猫了？能介绍下id的来源不？我猜里头肯定有故事：）
- 复 请教
家园 我来瞎掰一下。。。 能否说说的现实含义？什么样的复杂可以被认为是到一定程度了？此外，“无法证明真伪”的表现是什么？是指无法回溯到原始命题，还是由原始命题出发得不到确定的解释？这个“复杂到一定程度”，就是当能够找到一个命题，在此系统中无法证明真伪的时候。。。
“无法证明真伪”，应该是从原始命题出发得不到确定的解释。。。空间填不满。。。你可以看得见，但摸不着。。。
