很多人都见过“找规律”问题。找规律问题的初衷是良好的——培养发现规律、归纳总结的能力;但是有一些很糟糕的找规律问题,其标准答案的规律不能服众。这就自然引出一个疑问——如何定义“服众”?
我在《一种讨论“逻辑简单”的框架》已经阐述过一种计算机科学的定义,并在我的 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 对应的。
1
sennes 2018-01-04 13:51:22 +08:00
想起了一个我比较喜欢的序列
1 11 21 1112 3112 211213 312213 212223 114213 31121314 41122314 31221324 21322314 21322314 ... |
2
noe132 2018-01-04 14:44:02 +08:00
|
3
sennes 2018-01-24 17:17:28 +08:00
|