学习与停机问题

在笔者翻译的《有效过程与自然法则》译后记中,我提及一篇少为人知的论文

1996 年 R. Lathrop 在 ICML 上发表了 On the Learnability of the Uncomputable ,论文表明通过分析程序运行的时空行为, 在概率意义上停机问题可学习。论文在可计算性和可学习性之间给我们找到了一块落脚石,同时论文的分 析方法和算法信息论(AIT)里 Chaitin 常数 Ω 的渐进可计算性似乎有更进一步的联系。

在之前相关的文稿中,我有这样几段话,我把它们列在一起,来表明我的一种一致的观点

在工程实践中,我们有两种方式使用一个计算机程序。一种是使用它的最终 效果,一种是使用它的计算过程。前者的例子是程序库的各种标准例程, 比如 sin、cos 等等,我们不在乎它的实现细节和计算的中间状态,只在乎最终结果。后者的例子是打游戏,游戏程序循环的每一步, 都导致我们用户在音视频上的某种体验,整个计算过程都是我们需要的。

但在可计算性的理论里,我们仅仅考虑的是能够停机的偏函数,为什么我们不能考察整个计算过程呢?我的理解是,我们缺乏一种数学语言, 去刻画一个计算过程。这种数学语言的缺失,很早很早之前就埋在了数学的发展中。

人们常说,数和形是数学的基本主题。让我们看一下数的早期历史。从石器 时代非洲的骨刻,我们可以看到数的概念表征和计算过程是浑然一体的, 这种表征非常繁琐,计算的能力也非常有限。其后,数的表征,经过古埃及的 不成熟形态,到达了古巴比伦的数位制。在这个历史过程里, 人们遗忘了一个隐藏的巨大世界—那就是表达式,或者说计算过程。数作为一种表征,本来就是计算过程的高度凝练的表达,但它一旦符号化后, 就成为我们追求的目标。于是,我们往往关注计算过程的结果,而忽视了过程本身蕴含的众多信息。
过程比结果更重要。

算术表达式的几何提供了一种可能,在这里计算过程可以被实现为一个几何上的流。