上周末的可计算性读书会第四次探讨
27 views
Skip to first unread message
Mingli Yuan
Apr 18, 2014, 5:06:27 PM4/18/14
to swarmagents_ai
嗨，各位，
因为工作比较忙，抱歉这么晚才把学习材料和当时的一些疑问和讨论整理出来。学习材料见附件。
此次学习的重点是如何利用可计算性来研究不可解问题
- 相对可计算性如何引入
- 给递归函数增加一个初始的不可计算的函数
- 神谕图灵机
-
如何利用可计算来规约出问题的等价类
- 多一规约
- 图灵规约
- 图灵度、图灵跳跃与图灵度偏序关系的结构
因为这部分内容不是我以前学过的，且这次整理时间也比较有限，所以讲的时候不是很通畅，有一些疑问。当时也有一些同学有疑问，我也一并整理下来。
1、神谕是如何把不可计算的判断告诉下层的图灵机的细节过程。
之所以想了解细节，是因为当时有同学问，既然不可计算，神谕纸带怎么能够存在？存在性如何保障？
对此问题，我个人目前的理解是，我们要假定神谕纸带可以存在才能展开讨论。这里有一个隐含的世界观—世界是不可计算的，可计算的结构仅仅是漂浮在海面上的薄薄的泡沫。
同学之所以有疑问，我想是他假定了一种机器和世界的交流方式—机器和世界只能交流字节一类的有规律的、非常有限的消息。
当时的讨论，还提及了《The new kind of Science》，如果个人理解正确，我觉得 Stephan Wolfram 过于高估了人类的理性能力，才会认为世界是可计算的。世界不是可以计算的，并不意味着世界不能够被有限度的模拟。Stephan Wolfram 对元胞自动机的着迷，其实是在于计算机模拟的能力。
可计算-不可计算、随机的-可描述的是有趣的对立关系。从可描述，到可计算，到可预测，这些知识给智能体的生存带来有益的贡献。所以，世界的可计算部分是一种稳定的不变的核，它植根于智能体的演变过程。
2、不可计算探讨的对象可以扩展到不可数的数学对象上，哥德尔定理探讨的是有限的、可数的形式系统，这个不同如何理解？
我个人理解：这其实是语言和世界的问题。语言是一种形式系统，它有有限的基础，是可数的；世界则比语言丰富的多。哥德尔定理探讨的是一个复杂的形式系统不可能在自身内部判断解决其完备与否。
关于哥德尔定理，下次会有一个大活动，相信大家可以有更多的讨论。
3、关于图灵跳跃，能够看出来也是一种对角线方法的使用，但我看到的参考书证明及其简略，不是非常理解，希望有人能够讲解。怎么理解停机问题 0 可以被某类神谕图灵机解决，而 0’ 则是该类神谕图灵机的停机问题，随着图灵度增高，底层的停机问题总能被高层的神谕图灵机解决，但本层的神谕图灵机解决不了本层的停机问题。
4、正如停机问题 0 非常不自然，因此人们找到了一些自然一点的等价问题。我的问题是，有 0‘ 对应的自然的问题吗？
以上是简略的回顾，如有错误还请指正。
明理
jake
Apr 18, 2014, 9:03:02 PM4/18/14
to swarmagents_ai
有些西方人是很死硬理性派的,他们也许不可体会到不可计算之美。
我觉得关于Oracle，我们还需再深入一些了解，还有Hypercomputation, Turing degree，还有creative set等等。
另外，最近还有一些新的进展，例如iteractive computation，这个和“人类计算”还有观察者都有关系。
在我的哲学体系里，我把Oracle、量子还有观察者以及真随机都是近似划等号的。
--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到swarmagents_a...@googlegroups.com。
要发帖到此论坛，请发送电子邮件至swarmag...@googlegroups.com。
要在网络上查看此讨论，请访问https://groups.google.com/d/msgid/swarmagents_ai/CAGDRuAjNtVuoZJ49Gg2LPu9wGa6WsRsazKa-4ffcKdLAeP7RqA%40mail.gmail.com。
要查看更多选项，请访问https://groups.google.com/d/optout。
jake
Apr 18, 2014, 9:10:56 PM4/18/14
to swarmagents_ai
昨天晚上看了这个电影，transcend，中文翻译居然叫《超验骇客》，巨恶俗的一个名字。
影片讨论了终极AI的实现、奇点（Singularity）的最终到来，以及有关上帝的终极问题。
最让我觉得有意思的是，影片的观点跟我们讨论的Oracle有些关系，因为编剧认为，AI的最终实现必须要上传一个Oracle，即一个活人的意识。于是，最终的奇点终于来了，在那一刻，机器开始超越人类。而这种超越也正是我喜欢的那种超越，非暴力的，没有硝烟的，悄无声息地超越。
只是，影片的结尾很烂，怎么滥法你自己去看吧，不再剧透了。
PS，这部影片完全没必要看3D版本，也许2D的画面会更好。
要在网络上查看此讨论，请访问https://groups.google.com/d/msgid/swarmagents_ai/65aabd0a.34.14577820997.Coremail.jakezj%40163.com。
要查看更多选项，请访问https://groups.google.com/d/optout。
LI Xi
Apr 18, 2014, 11:39:32 PM4/18/14
to swarmagents ai
一旦人造的机器超越人，这些机器就可以用更短的时间造出超越自身的机器，然后。。。更短的时间超越。。。然后。。。迅速收敛到奇点。
一般搞AI的人还是认为现实世界是可计算的，他们讨论的Singularity虽然不可计算，但也不过是\Delta_2^0的，允许可计算的逼近。
因为已有的所有应用数学（包括量子力学背后的那些数学）都可以在原始递归算术PRA里重新构造出来，大部分人乐观的估计，随着这种数学的持续发展，现实世界是可以被认识的，所以相信现实世界（包括人）是可计算的。
最恶心的是，图灵度结构太混乱复杂了，有实数那么多不能图灵归约的oracle，即使是递归可枚举集里不等度的oracle也极度复杂。
递归论里随机性的定义有太多的层次，如果你把真随机看做martin-lof随机的话，那么在此之下不能彼此图灵归约的oracle仍然是极度混乱复杂的，可以用各种随机性对图灵度进行分分层，但不能直接划等号。量子、意识这些目前还太模糊，不过如果用可计算的数学可以搞的清的话貌似没必要非要假设oracle，而且直接把一种说不清的东西（意识）跟另一种说不清的东西（量子）完全等同貌似也是一种死硬的理性乐观主义，希望哪天一个的解决同时解决另一个。如果把它们看做一种oracle的话，在实数那么多不等度的oracle里，哪个那么特别恰好是我们的意识呢？
即使意识是可计算的，它仍然可以模拟现实宇宙（包括“模拟宇宙”自身的模拟行为）并保留“自由意志”的错觉，如果作为“模拟宇宙”的“意识”精度不足，或速度远远滞后于现实宇宙的进化，那么作为“模拟宇宙”的意识有一种非决定论的错觉是很自然的。即使允许精确快速地模拟（这或许是可能的，虽然“模拟宇宙”必须比现实宇宙的演化速度快，“模拟宇宙”又是现实宇宙的很小很小的子部分，但是，或许借助某种自指或固定点定理，理论上有可能实现），也仍然不意味着可以排除“自由意志”的假象——因为，如果把现实宇宙看做一个形式系统（或图灵机）𝑇，“模拟宇宙”如果想比现实宇宙演化快的话，必须严格强于现实宇宙，因为，只有在一个严格强于𝑇的系统𝑇œ'里，对于同样的命题的最短证明长度才会短于𝑇里的证明长度，也就是说，一方面，从表达力和证明强度上说，现实宇宙𝑇可以看做“模拟宇宙”𝑇'œ的子系统，另一方面，“模拟宇宙”𝑇'œ又要通过编码方式可以嵌入到现实宇宙𝑇中，问题是：虽然强系统𝑇œ'可以编码到弱系统𝑇中，但是，只要这种编码嵌入可行，那么，如果“模拟宇宙”想确保自己是现实宇宙精确且可靠的模拟的话，它的一致性就应该借助现实宇宙𝑇来证明，第二不完全性定理否定了这种可能性，即使放宽一步，试图通过“模拟宇宙”𝑇œ自身证明也不可能。所以第二不完全性定理有可能是认知不确定性不可逾越的障碍，这就为意识能够产生“自由意志”的错觉提供了可能。
另外，明理说的"哥德尔定理探讨的是一个复杂的形式系统不可能在自身内部判断解决其完备与否"貌似不严谨，第二不完全性定理说自身不能证明自身的一致性，至于存在不可判定的真命题这个第一不完全性定理可以在很弱的系统里得到证明，比如在原始递归算术或鲁宾逊算术里，都可以证明所有比它强的形式系统只要是一致的且递归公理化的那么都不完备。
貌似我看过的书里都是用0表示递归用0'表示停机集的度，明理手误？虽然递归可枚举集丢番图可表示，但这都是人造的表示，所以算不上跟停机集等价的“自然”的问题。我见过的PA不可判定的“自然”的（在强系统中的）定理，比如Ramsey定理的一些变种，要么比停机问题强要么弱，完全等价的没见过。
XL
要查看更多选项，请访问 https://groups.google.com/d/optout 。
--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 swarmagents_a...@googlegroups.com 。
要发帖到此论坛，请发送电子邮件至 swarmag...@googlegroups.com 。
要在网络上查看此讨论，请访问 https://groups.google.com/d/msgid/swarmagents_ai/65aabd0a.34.14577820997.Coremail.jakezj%40163.com 。
要查看更多选项，请访问 https://groups.google.com/d/optout 。
--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 swarmagents_a...@googlegroups.com 。
要发帖到此论坛，请发送电子邮件至 swarmag...@googlegroups.com 。
要在网络上查看此讨论，请访问 https://groups.google.com/d/msgid/swarmagents_ai/37994b9.46.1457789478d.Coremail.jakezj%40163.com 。
要查看更多选项，请访问 https://groups.google.com/d/optout 。
--
LI Xi
Center for Logic,Language and Cognition
Department of Philosophy
Peking University
Beijing, 100871, China
Tel: 0086 151 2005 3510
Email: x...@pku.edu.cn
一般搞AI的人还是认为现实世界是可计算的，他们讨论的Singularity虽然不可计算，但也不过是\Delta_2^0的，允许可计算的逼近。
因为已有的所有应用数学（包括量子力学背后的那些数学）都可以在原始递归算术PRA里重新构造出来，大部分人乐观的估计，随着这种数学的持续发展，现实世界是可以被认识的，所以相信现实世界（包括人）是可计算的。
最恶心的是，图灵度结构太混乱复杂了，有实数那么多不能图灵归约的oracle，即使是递归可枚举集里不等度的oracle也极度复杂。
递归论里随机性的定义有太多的层次，如果你把真随机看做martin-lof随机的话，那么在此之下不能彼此图灵归约的oracle仍然是极度混乱复杂的，可以用各种随机性对图灵度进行分分层，但不能直接划等号。量子、意识这些目前还太模糊，不过如果用可计算的数学可以搞的清的话貌似没必要非要假设oracle，而且直接把一种说不清的东西（意识）跟另一种说不清的东西（量子）完全等同貌似也是一种死硬的理性乐观主义，希望哪天一个的解决同时解决另一个。如果把它们看做一种oracle的话，在实数那么多不等度的oracle里，哪个那么特别恰好是我们的意识呢？
即使意识是可计算的，它仍然可以模拟现实宇宙（包括“模拟宇宙”自身的模拟行为）并保留“自由意志”的错觉，如果作为“模拟宇宙”的“意识”精度不足，或速度远远滞后于现实宇宙的进化，那么作为“模拟宇宙”的意识有一种非决定论的错觉是很自然的。即使允许精确快速地模拟（这或许是可能的，虽然“模拟宇宙”必须比现实宇宙的演化速度快，“模拟宇宙”又是现实宇宙的很小很小的子部分，但是，或许借助某种自指或固定点定理，理论上有可能实现），也仍然不意味着可以排除“自由意志”的假象——因为，如果把现实宇宙看做一个形式系统（或图灵机）𝑇，“模拟宇宙”如果想比现实宇宙演化快的话，必须严格强于现实宇宙，因为，只有在一个严格强于𝑇的系统𝑇œ'里，对于同样的命题的最短证明长度才会短于𝑇里的证明长度，也就是说，一方面，从表达力和证明强度上说，现实宇宙𝑇可以看做“模拟宇宙”𝑇'œ的子系统，另一方面，“模拟宇宙”𝑇'œ又要通过编码方式可以嵌入到现实宇宙𝑇中，问题是：虽然强系统𝑇œ'可以编码到弱系统𝑇中，但是，只要这种编码嵌入可行，那么，如果“模拟宇宙”想确保自己是现实宇宙精确且可靠的模拟的话，它的一致性就应该借助现实宇宙𝑇来证明，第二不完全性定理否定了这种可能性，即使放宽一步，试图通过“模拟宇宙”𝑇œ自身证明也不可能。所以第二不完全性定理有可能是认知不确定性不可逾越的障碍，这就为意识能够产生“自由意志”的错觉提供了可能。
另外，明理说的"哥德尔定理探讨的是一个复杂的形式系统不可能在自身内部判断解决其完备与否"貌似不严谨，第二不完全性定理说自身不能证明自身的一致性，至于存在不可判定的真命题这个第一不完全性定理可以在很弱的系统里得到证明，比如在原始递归算术或鲁宾逊算术里，都可以证明所有比它强的形式系统只要是一致的且递归公理化的那么都不完备。
貌似我看过的书里都是用0表示递归用0'表示停机集的度，明理手误？虽然递归可枚举集丢番图可表示，但这都是人造的表示，所以算不上跟停机集等价的“自然”的问题。我见过的PA不可判定的“自然”的（在强系统中的）定理，比如Ramsey定理的一些变种，要么比停机问题强要么弱，完全等价的没见过。
XL
--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 swarmagents_a...@googlegroups.com 。
要发帖到此论坛，请发送电子邮件至 swarmag...@googlegroups.com 。
要在网络上查看此讨论，请访问 https://groups.google.com/d/msgid/swarmagents_ai/65aabd0a.34.14577820997.Coremail.jakezj%40163.com 。
--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 swarmagents_a...@googlegroups.com 。
要发帖到此论坛，请发送电子邮件至 swarmag...@googlegroups.com 。
要查看更多选项，请访问 https://groups.google.com/d/optout 。
--
LI Xi
Center for Logic,Language and Cognition
Department of Philosophy
Peking University
Beijing, 100871, China
Tel: 0086 151 2005 3510
Email: x...@pku.edu.cn
Reply all
Reply to author
Forward
0 new messages