最后一次计算理论读书会

[Mingli Yuan]

嗨，各位，

最后一次计算理论读书会将于本周日（5月11日）下午两点半在蕴味咖啡举行，欢迎各位到时参与。

此次读书会原定教材的章节安排是讨论抽象的计算理论，不再是基于自然数，或者基于和While语言相关的树结构。

因为最近的一些探讨，我决定此次读书会主题将聚焦在一个争议话题上—可计算性和物理世界的关系。搜集的文献已经比较丰富，有六、七十篇论文，我正在抓紧时间阅读和整理，我目前还不能确定最终整理成型的内容大纲。

内容不会很深入，但会尽量澄清几个问题上的争论和探讨：

• 物理世界是否可计算？
• 超计算（Hypercomputation）或者其他的计算形式是否可行？
• 认知的限度在哪里？
• 这个话题的核心研究者有哪些？

这个话题在上世纪中叶已经有零星讨论，从九十年代开始逐渐升温，到最近几年一直都有不间断的讨论。

因为学科跨度比较大，理解错误在所难免，我只能尽力而为，也请大家多指正。

明理

[Mingli Yuan]

嗨，各位，

最后一次讨论的学习材料见附件。这次学习活动来了好几位有意思的新朋友，可见大家对这个话题有兴趣。

虽然搜集了不少论文，但我发现总结起来很困难，因为各种观点很多，可又缺乏统领全局的理论。

最后努力之下，只能有一个非常粗浅的总结：

• 计算主义的一些代表人物和观点
• 用巨石阵的一种假说来说明神谕机
• 简单介绍了奇性和芝诺机

不过，在读书会开始前的上午，我读到了 Robert Rosen 的一篇老文章 Effective Process and Natural Law ，觉得可以起到提纲挈领的作用。我也把此论文附在本邮件里。

我会争取本周末也把这篇论文的读书笔记发出来讨论。

明理

[Mingli Yuan]

Robert Rosen 的 Effective Process and Natural Law 写于1995年，作为一系列论文中的一篇编入文集 The Universal Turing Machine - A Half-Century Survey 。在这篇论文里 Robert Rosen 剖析了 Turing-Church 论题和有效过程的概念，并探讨了有效过程同自然律的关系。

论文全文共分 5 节，

• 第一节：介绍
  
• 第二节：形式系统里的 Turing-Church 论题
  
• 第三节：蕴含与因果关系
  
• 第四节：Turing-Church 论题在物理意义上对吗？
  
• 第五节：模拟的角色

每一节都有一些有意思的论点，以下是我提取的摘要：

图灵机把人类在进行数学计算时的心智过程外化为一种数学形式。 本节剖析算法和有效过程的关系：算法是通过有效过程来解决一个问题时的表现。算法是确定的机械过程，可以给予形式的数学描述；而有效过程却是一个模糊的、非形式的概念。Turing-Church 论题的一种表达就是：任何有效过程都可以表达为图灵机上的一个算法。

 

一个疑问是：

• 人类计算的心智过程是一个实际发生的物质过程；该物质过程抽取出一个纯粹形式的框架—图灵机—可以模拟心智过程；于是，是否能够存在其他的物质过程，也可以模拟心智过程？

这是 AI 的核心问题。

 

一旦当我们考虑物质的、物理的过程，我们就有软件／硬件的差异。这个差异是关于计算的理论中所没有考虑到的。来自Martin Davis的一个疑问是：

• 物理世界允许超越图灵计算能力的过程吗？

一旦将物理过程引入到理论中，有效过程会怎么样？

• 是 Turing-Church 论题给物理世界施加了一个深远的限制？还是相反？

• 如果 Turing-Church 论题可以被物理世界违反，那么递归性会怎么样？

通过对一个物理系统施加扰动 $\alpha$ 并观测结果 $\beta$ 的实验，我们可以定义一个函数：

 

$$f: \alpha \mapsto \beta$$

 

如果实验是可重复的，则 Turing-Church 论题蕴含 f 的可计算性。

 以上我个人感觉最有启发性质的是把有效过程、算法两个概念分离开来讨论。

[Mingli Yuan]

哦，没写清楚。以上是第一节的摘要，其他四节的摘要会逐一给出。

[Mingli Yuan]

第二节（形式系统里的 Turing-Church 论题）的笔记我只做了一部分，原因有一部分关于蕴含的没有理解很透，不敢妄自乱写。

我先把这部分笔记给出来，疑问在后面给出。

任何形式系统里的逻辑推理都可以归结为字串操作，后者是纯粹语法性的操作。

希尔伯特形式主义想法的核心是希望下述过程成立：

  总是可以把语义的替换为语法的，并且可以保证逻辑上没有任何信息的丢失；

  如此，任何涉及语义的推理最终都在形式系统里有一个纯粹语法的对应物。

在这样一个系统里，真是内在的。我们无需从外部引入真，只是承认公理为真，利用推理规则，把真从

公理传递到定理。

哥德尔 1931 年的定理表明，这种构造式的内在的真，和预先赋值的形式化算术里的外在的真值，是不

匹配的。更进一步，图灵关于确定性的定理指出，不存在内在的推理机制来决定一个命题是否是定理。

由此，我们要么把自己局限在算术系统的片段之中；要么我们必须允许一种非形式化的推理机制；而后者

从 Turing-Church 论题的角度讲，不是一个有效过程。

本节的疑问主要有两个

1、我理解的本节大意应该是：从 Turing-Church 论题的角度看形式系统里的哥德尔定理，他指出如果我们接受算术系统整体，哥德尔定理蕴含着非有效过程的存在？但对这样的叙述，我不是特别理解究竟意味着什么？

2、我没写笔记的关于蕴含的这一段：作者应该是描述了蕴含的两种定义，一种语法的，一种语义的。语法的作者没讲，而语义的定义作者是这样处理的：从集论出发，在一个集合 S 上定义了一系列代数结构，对于 $S \times S$中的一个映射，这个映射就可以做成蕴含。更进一步，作者讨论了该映射如果是语法、语义彼此吻合，那么就是可计算的；否则不可计算的。

对于蕴含的语法、语义的两种定义还都要去查阅资料。

如果大家有什么批评指正，或者评注，欢迎在此给出。

[Xi Li]

明理好，文章我没看，就猜着说了，看过的请指正。

关于疑问1，估计说的是，如果所有（或至少非递归可枚举的那么多）算术真理都真的刻画了现实世界的某种物 理规律的话，那么不可判定的真命题就可能正好刻画了某个物理区域的演化过程，如果这个过程可计算，那么形式系统内就“可表示”，表示它的那个真命 题当然可 推出，所以不完全性定理蕴涵非有效过程的存在。但这个前提是否成立不知道，比如，假如现实世界是有穷离散的话，那么肯定有形式系统可以完全把握 它，关于它 的所有命题都可以判定，只要我们真的把这个形式系统当作一种抽象的存在（跟现实物理世界没任何关系），可如果把形式系统也看作一种需要物理表征的 实体机器 的话，即使对于有穷离散的世界这也不一定。

疑问2，这里应该还是“可表示性”，一个映射可看作初态到末态的演化（估计是这里说的语义蕴涵），你给的没作任何限制的映射当然包含很多不可计算 的函数， 形式系统内可表示的函数看作语法蕴涵，有定理证明，只要稍微强一点儿的（可以很弱）形式系统，可表示的函数都是可计算的函数，可计算的也都可表 示。当然那 些不可表示的就是不可计算的了。

On 06/02/2014 10:41 PM, Mingli Yuan wrote:

第二节（形式系统里的 Turing-Church 论题）的笔记我只做了一部分，原因有一部分关于蕴含的没有理解很透，不敢妄自乱写。

我先把这部分笔记给出来，疑问在后面给出。

任 何形式系统里的逻辑推理都可以归结为字串操作，后者是纯粹语法性的操作。

希 尔伯特形式主义想法的核心是希望下述过程成立：

  总是可以把语义的替换为语法的，并且可以保证逻辑上没有任何信息的丢失；

  如此，任何涉及语义的推理最终都在形式系统里有一个纯粹语法的对应物。

在 这样一个系统里，真是内在的。我们无需从外部引入真，只是承认公理为真，利用推理规则，把真从

公 理传递到定理。

哥 德尔 1931 年的定理表明，这种构造式的内在的真，和预先赋值的形式化算术里的外在的真值，是不

匹 配的。更进一步，图灵关于确定性的定理指出，不存在内在的推理机制来决定一个命题是否是定理。

由 此，我们要么把自己局限在算术系统的片段之中；要么我们必须允许一种非形式化的推理机制；而后者

从 Turing-Church 论题的角度讲，不是一个有效过程。

本节的疑问主要有两个

1、我理解的本节大意应该是：从 Turing-Church 论题的角度看形式系统里的哥德尔定理，他指出如果我们接受算术系统整体，哥德尔定理蕴含着非有效过程的存在？但对这样的叙述，我不是特别理解究竟意味着什 么？

2、我没写笔记的关于蕴含的这一段：作者应该是描述了蕴含的两种定义，一种语法的，一种语义的。语法的作者没讲，而语义的定义 作者是这样处理的：从集论出发，在一个集合 S 上定义了一系列代数结构，对于 $S \times S$中的一个映射，这个映射就可以做成蕴含。更进一步，作者讨论了该映射如果是语法、语义彼此吻合，那么就是可计算的；否则不可计算的。

对于蕴含的语法、语义的两种定义还都要去查阅资料。

如果大家有什么批评指正，或者评注，欢迎在此给出。

2014-05-26 0:02 GMT+08:00 Mingli Yuan <mingl...@gmail.com>:

哦，没写清楚。以上是第一节的摘要，其他四节的摘要会逐一给出。

2014-05-25 23:22 GMT+08:00 Mingli Yuan <mingl...@gmail.com>:

Robert Rosen 的 Effective Process and Natural Law 写于1995年，作为一系列论文中的一篇编入文集 The Universal Turing Machine - A Half-Century Survey 。在这篇论文里 Robert Rosen 剖析了 Turing-Church 论题和有效过程的概念，并探讨了有效过程同自然律的关系。

论文全文共分 5 节，

• 第一节：介绍
  
• 第二节：形式系统里的 Turing-Church 论题
  
• 第三节：蕴含与因果关系
  
• 第四节：Turing-Church 论题在物理意义上对吗？
  
• 第五节：模拟的角色

每一节都有一些有意思的论点，以下是我提取的摘要：

图 灵机把人类在进行数学计算时的心智过程外化为一种数学形式。 本节剖析算法和有效过程的关系：算法是通过有效过程来解决一个问题时的表现。算法是确定的机械过程，可以给予形式的数学描述；而有效过程却是一个模糊的、 非形式的概念。Turing-Church 论题的一种表达就是：任何有效过程都可以表达为图灵机上的一个算法。

 

一 个疑问是：

• 人类计算的心智过程是一个实际发生的物质过程；该物质过程抽取出一个纯粹形式的框 架—图灵机—可以模拟心智过程；于是，是否能够存在其他的物质过程，也可以模拟心智过 程？

这是 AI 的核心问题。

 

一 旦当我们考虑物质的、物理的过程，我们就有软件／硬件的差异。这个差异是关于计算的理论中所没 有考虑到的。来自Martin Davis的一个疑问是：

• 物理世界允许超越图灵计算能力的过程吗？

一旦将物理过程引入到理论中，有效过程会怎么样？

• 是 Turing-Church 论题给物理世界施加了一个深远的限制？还是相反？

• 如果 Turing-Church 论题可以被物理世界违反，那么递归性会怎么样？

通过对一个物理系统施加扰动 $\alpha$ 并观测结果 $\beta$ 的实验，我们可以定义一个函数：

 

$$f: \alpha \mapsto \beta$$

 

如 果实验是可重复的，则 Turing-Church 论题蕴含 f 的可计算性。

 以上我个人感觉最有启发性质的是把有效过程、算法两个概念分离开来讨论。

2014-05-15 18:28 GMT+08:00 Mingli Yuan <mingl...@gmail.com>:

嗨，各位，

最后一次讨论的学习材料见附件。这次学习活动来了好几位有意思的新朋友，可 见大家对这个话题有兴趣。

虽然搜集了不少论文，但我发现总结起来很困难，因为各种观点很多，可又缺乏 统领全局的理论。

最后努力之下，只能有一个非常粗浅的总结：

• 计算主义的一些代表人物和观点
• 用巨石阵的一种假说来说明神谕机
• 简单介绍了奇性和芝诺机

不过，在读书会开始前的上午，我读到了 Robert Rosen 的一篇老文章 Effective Process and Natural Law ，觉得可以起到提纲挈领的作用。我也把此论文附在本邮件里。

我会争取本周末也把这篇论文的读书笔记发出来讨论。

明理

2014-05-04 18:03 GMT+08:00 Mingli Yuan <mingl...@gmail.com>:

嗨，各位，

最后一次计算理论读书会将于本周日（5月11日）下午 两点半在蕴味咖啡举行，欢迎各位到时参与。

此次读书会原定教材的章节安排是讨论抽象的计算理论， 不再是基于自然数，或者基于和While语言相关的树结构。

因为最近的一些探讨，我决定此次读书会主题将聚焦在一 个争议话题上—可计算性和物理世界的关系。搜集的文献已经比 较丰富，有六、七十篇论文，我正在抓紧时间阅读和整理，我目 前还不能确定最终整理成型的内容大纲。

内容不会很深入，但会尽量澄清几个问题上的争论和探 讨：

• 物理世界是否可计算？
• 超计算（Hypercomputation）或 者其他的计算形式是否可行？
• 认知的限度在哪里？
• 这个话题的核心研究者有哪些？

这个话题在上世纪中叶已经有零星讨论，从九十年代开始 逐渐升温，到最近几年一直都有不间断的讨论。

因为学科跨度比较大，理解错误在所难免，我只能尽力而 为，也请大家多指正。

明理

--
您收到此邮件是因为您订阅了Google网上论坛中的“集智AI(人工智能)讨论组”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到swarmagents_a...@googlegroups.com。
要发帖到此论坛，请发送电子邮件至swarmag...@googlegroups.com。
要在网络上查看此讨论，请访问https://groups.google.com/d/msgid/swarmagents_ai/CAGDRuAgLG_eJkWY38GK7S2aSkaQZJbcnZ7GnOob9KSyLmVaGVw%40mail.gmail.com。
要查看更多选项，请访问https://groups.google.com/d/optout。

[Mingli Yuan]

多谢！

第一个疑问，我还不确定，有时间再读读。

第二个疑问，估计你的解答应该是在点子上的。我再去找找“可表示性”的文章看看。

要在网络上查看此讨论，请访问https://groups.google.com/d/msgid/swarmagents_ai/538DC538.1030106%40pku.edu.cn。
要查看更多选项，请访问https://groups.google.com/d/optout。

[Mingli Yuan]

最新的一篇关于这个题目的论文，发表于英国皇家学会的刊物上。