这是一个创建于 2549 天前的主题，其中的信息可能已经有所发展或是发生改变。
引子
很多人都见过“找规律”问题。找规律问题的初衷是良好的——培养发现规律、归纳总结的能力；但是有一些很糟糕的找规律问题，其标准答案的规律不能服众。这就自然引出一个疑问——如何定义“服众”？
我在《一种讨论“逻辑简单”的框架》已经阐述过一种计算机科学的定义，并在我的 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 ……
我们可以导出如下命题：
可计算条件 一个部分数列有解，当且仅当它是一个可计算数列删除一些项得到的。
推论 有限部分数列总是有解。
规律和补全的锁定 对一个数列，下列命题等价：
- 它可计算。
- 存在 K 使对任意 k>K，它 k-部分的规律和它 K-部分的规律是一样的。
- 存在 K 使它的 K-部分的补全是原来这个数列自己。
不可计算性 不存在一个算法，输入一个有限部分序列，输出它的规律。
回到主题
回到开始的主题，任何“找规律”问题都是给定一个有限部分数列，寻求它的规律或补全的问题。用刚刚的定义，可以给出一个服众的标准答案（如果大家同意用同一个固定的编程语言）——标准答案应该是该部分数列的补全的对应位置的项。这个定义也导致“找规律”问题是困难的——因为不存在一个算法用来“找规律”。
哲学启示
可计算条件和不可计算性构成了这个框架的辨证矛盾。不可计算性表明：
寻求最简洁的、解释我们的观测到的现象的理论不是纯粹机械的工作。
此外，注意规律锁定这一命题实际上和选定的编程语言无关（只要是图灵完备即可）——无论是什么语言，逐渐增加对一个可计算数列的观察，最终补全都会锁定到原来的数列上，所以：
即使人人迥异，只要尚是可教之才，在经过足够的观察后，大家会得到相同的掌管自然的规律。
* “可教之才”翻译自 knowledgeable，但我想表达的是“愚不可及”的反义词，显然这些概念是和 Turing (in-)complete 对应的。
广告回放
- 本文原文、全文 Is the pattern you found persuasive?
- 欢迎访问 geelaw.blog 的其他文章
 |
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
|
Select Language