V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
geelaw
V2EX  ›  分享创造

找规律填数问题

  •  
  •   geelaw ·
    GeeLaw · 2018-01-04 13:38:31 +08:00 · 2581 次点击
    这是一个创建于 2504 天前的主题,其中的信息可能已经有所发展或是发生改变。

    引子

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

    我在《一种讨论“逻辑简单”的框架》已经阐述过一种计算机科学的定义,并在我的 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 ……

    我们可以导出如下命题:

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

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

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

    1. 它可计算。
    2. 存在 K 使对任意 k>K,它 k-部分的规律和它 K-部分的规律是一样的。
    3. 存在 K 使它的 K-部分的补全是原来这个数列自己。

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

    回到主题

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

    哲学启示

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

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

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

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

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

    广告回放

    3 条回复    2018-01-24 17:17:28 +08:00
    sennes
        1
    sennes  
       2018-01-04 13:51:22 +08:00
    想起了一个我比较喜欢的序列

    1
    11
    21
    1112
    3112
    211213
    312213
    212223
    114213
    31121314
    41122314
    31221324
    21322314
    21322314
    ...
    noe132
        2
    noe132  
       2018-01-04 14:44:02 +08:00
    常用的工具
    https://oeis.org
    整数序列查询
    sennes
        3
    sennes  
       2018-01-24 17:17:28 +08:00
    @noe132 #2 哈哈 谢谢!
    我说的就是这个序列 : https://oeis.org/A005151
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3637 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 00:11 · PVG 08:11 · LAX 16:11 · JFK 19:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.