找规律填数问题

引子

很多人都见过“找规律”问题。找规律问题的初衷是良好的——培养发现规律、归纳总结的能力；但是有一些很糟糕的找规律问题，其标准答案的规律不能服众。这就自然引出一个疑问——如何定义“服众”？

我在《一种讨论“逻辑简单”的框架》已经阐述过一种计算机科学的定义，并在我的 blog 文章 Is the pattern you found persuasive? 里改用英语更好地组织、总结了问题。

这篇在 V2EX 的帖子是 blog 文章的主旨的翻译。完整的文章仍然应该以 blog 为准。

为了解决这个问题，我们诉诸简单、诉诸奥卡姆剃刀原则。我们定义“服众”为“简单”，从而问题变成：如何定义“简单”？为了这个目的，假设存在一种大家都同意使用的编程语言，并定义如下概念：

数列、部分数列 一个数列是指定义域是自然数、取值是自然数的函数。一个部分数列是一个数列删除一些项（留下空位）后得到的序列。

有限、部分 一个部分数列是有限的，当且仅当它只有有限项是给定的（其他项都被删除留空）。对于自然数 n，一个数列保留它前 n 项而删除之后所有项并留空的序列，叫做它的 k-部分。

解一个程序是一个部分数列的解，是说该程序输入所有自然数都停机、输出一个自然数，且程序在部分数列里给出的项上输出等于该部分数列。

简单不等长程序，更短者更简单；等长的程序，字典序更小者更简单。

规律若一个部分数列有解，则它的解中最简单者，叫做它的规律。

补全若一个部分数列有解，则它的规律产生的数列叫做它的补全。

避免太抽象，举两个简单的例子——至于为什么我只用简单的例子，后面的命题会表明。假设我们使用 JavaScript ES2015，要求代码必须是一个表达式，且求值得到一个方法，这个方法在参数是 n 时的输出就当作是程序的输出。

例 1 考虑部分数列：0、空、空……一个解是 function (n) { return n ? 123 : 0; }，但它的规律（最简单的解）是 function(){return 0}，所以补全是：0、0、0 ……

例 2 考虑部分数列：0、1、空、空……它的规律是 function($){return $}，因此它的补全是：0、1、2、3 ……

我们可以导出如下命题：

可计算条件 一个部分数列有解，当且仅当它是一个可计算数列删除一些项得到的。

推论有限部分数列总是有解。

规律和补全的锁定 对一个数列，下列命题等价：

不可计算性 不存在一个算法，输入一个有限部分序列，输出它的规律。

回到开始的主题，任何“找规律”问题都是给定一个有限部分数列，寻求它的规律或补全的问题。用刚刚的定义，可以给出一个服众的标准答案（如果大家同意用同一个固定的编程语言）——标准答案应该是该部分数列的补全的对应位置的项。这个定义也导致“找规律”问题是困难的——因为不存在一个算法用来“找规律”。

可计算条件和不可计算性构成了这个框架的辨证矛盾。不可计算性表明：

寻求最简洁的、解释我们的观测到的现象的理论不是纯粹机械的工作。

此外，注意规律锁定这一命题实际上和选定的编程语言无关（只要是图灵完备即可）——无论是什么语言，逐渐增加对一个可计算数列的观察，最终补全都会锁定到原来的数列上，所以：

即使人人迥异，只要尚是可教之才，在经过足够的观察后，大家会得到相同的掌管自然的规律。

* “可教之才”翻译自 knowledgeable，但我想表达的是“愚不可及”的反义词，显然这些概念是和 Turing (in-)complete 对应的。