内容gydF4y2Ba 1920年,2020年和2万美元的奖金:宣布S Combinator挑战gydF4y2Ba

1920年,2020年和2万美元的奖金:宣布S Combinator挑战gydF4y2Ba

1920年,2020年和2万美元的奖金:宣布S Combinator挑战gydF4y2Ba

在光天化日之下躲了一个世纪?gydF4y2Ba

在gydF4y2Ba1920年12月7日,Moses Schönfinkel引入了S和K组合子gydF4y2Ba并且这样做提供了一个系统的第一个明确的例子,这个系统能够进行我们现在所说的通用计算。一百年后——正如我所准备的那样gydF4y2Ba庆祝组合公司诞生一百周年gydF4y2Ba我认为是时候尝试使用现代计算方法了,看看我们现在能从组合子中学到什么。在这个过程中,我得到了一个惊喜。gydF4y2Ba

S和K的通用计算已经很了不起了。但从我的探索中,我开始思考一些更了不起的事情可能是真的,事实上,S单独可能就足以实现普遍计算。换句话说,这只是应用了规则gydF4y2Ba

S f g xgydF4y2Ba→gydF4y2BafgydF4y2Ba[gydF4y2BaxgydF4y2Ba][gydF4y2BaggydF4y2Ba[gydF4y2BaxgydF4y2Ba]]gydF4y2Ba

一遍又一遍地做任何可以做的计算可能都是需要的。gydF4y2Ba

我不确定这是不是真的,虽然我gydF4y2Ba积累经验证据gydF4y2Ba这似乎指向了这个方向。今天,我宣布一项2万美元的奖金(是的,“20”与1920年发明的组合子和2020年做出我的猜想有关),用于证明(或否定)仅S组合子就能支持通用计算。gydF4y2Ba

为什么知道很重要?显然,如果事实证明,隐藏在普通视线中的一个世纪是一个比我们所知道的更简单的通用计算基础,那就太棒了。但更重要的是,确定是否只有S组合子是通用的,将提供一个重要的额外数据点,以绘制出通用计算的阈值所在的位置。gydF4y2Ba

实用的计算机都有复杂而精心设计的cpu。但是,这种复杂性真的需要支持通用计算吗?我的gydF4y2Ba对计算宇宙的探索gydF4y2Ba在过去的40年里,我得出了一个结论,那就是它绝对不是,事实上,即使是在有着最简单规则的系统中,通用计算实际上也是无处不在的。gydF4y2Ba

我已经制定了一个非常普遍的原则,我称之为gydF4y2Ba计算等价原理gydF4y2Ba这意味着,无论什么时候我们看到的行为在某种程度上并不明显简单,那么它实际上会对应于一个计算,在复杂度上与任何其他计算相等。这个原理的众多结果之一就是计算的普适性应该是无处不在的。gydF4y2Ba

30多年来,我一直在通过证明(或否定)特定系统的计算是通用的,来推动这方面的明确证据。由此产生了两个非常好的例子来验证计算等价原则:gydF4y2Ba110规则元胞自动机gydF4y2Ba

& # 10005gydF4y2Ba

RulePlot [CellularAutomaton [110]]gydF4y2Ba

和gydF4y2Ba2、3图灵机gydF4y2Ba:gydF4y2Ba

& # 10005gydF4y2Ba

RulePlot [TuringMachine[{596440年2、3}]]gydF4y2Ba

这两个系统我认为是他们类型中最简单的,可以想象是计算通用的,而且我预期这两个系统实际上都是计算通用的。gydF4y2Ba

但在这两种情况下,提出明确的证据都是一项艰巨的工作。在第一个案例中,证据是我书中的一部分gydF4y2Ba一种新的科学gydF4y2Ba(与大部分gydF4y2Ba这是我当时的研究助理做的重活gydF4y2Ba).在第二种情况下,我已经gydF4y2Ba的猜想gydF4y2Ba“在gydF4y2Ba一种新的科学gydF4y2Ba,但在gydF4y2Ba2007年我决定gydF4y2Ba搭起gydF4y2Ba真正解决问题的奖励gydF4y2Ba.我很高兴,仅仅几个月后,gydF4y2Ba找到了证据,奖品就到手了gydF4y2Ba.gydF4y2Ba

现在我希望在S组合子的情况下也会发生类似的情况。我期望它会被证明是计算通用的,但如果它被证明不是,那可能会更有趣。gydF4y2Ba

在过去,人们可能会看到证明一个简单系统是(或不是)计算是一种普遍的好奇心,有点像解决一个特定的数学难题。但是,计算等价性原则和我在探索计算宇宙时所做的所有科学,现在把这样一个问题放在更广泛的背景下,并表明它远不是一种好奇心,实际上是一个中心问题艾尔。gydF4y2Ba

例如,计算的普适性gydF4y2Ba计算不可约性gydF4y2Ba,gydF4y2Ba不可判定性gydF4y2Ba.了解这些现象在自然系统,数学系统和技术系统中有多普遍对于什么时候可以做出预测,以及什么样的问题可以得到回答都有重要的基础和实际意义。gydF4y2Ba

确定计算通用性的阈值对于制造分子规模的计算机也有直接的意义,例如,在计算机安全方面,可以知道某些程序的某些部分是否真的是通用性的,因此它可以被编程去做坏事。gydF4y2Ba

基本设置gydF4y2Ba

在通常的S, K组合子设置中,一个人通过设置一个初始的组合子表达式来编码他想要做的计算,然后重复应用组合子规则,直到1gydF4y2Ba到达一个不动点gydF4y2Ba这可以解释为计算的结果。当然,不是所有的计算都停止,对于不停止的计算,永远不会达到固定点。gydF4y2Ba

的年代gydF4y2Ba单独使用直接输入→输出表示的组合运算是行不通的。原因是有一个gydF4y2Ba详尽但有限的描述gydF4y2Ba,这个特征的存在意味着停止的S组合子进化没有足够的丰富度来表示任意计算。gydF4y2Ba

然而,仍有许多不间断的S组合子演进。这里是最简单的:gydF4y2Ba

& # 10005gydF4y2Ba

ResourceFunction [" CombinatorEvolutionPlot "][文本[ResourceFunction[“CombinatorPlot”][ReplaceAll [#, {s - >组合子,k - > CombinatorK}],“CharactersLeftAssociative”、“SKGlyphs”- - - > {s、k},“ApplicationGlyph”——>“\ [NegativeVeryThinSpace ]"]] & /@ ResourceFunction[“CombinatorEvolveList”][s [s] [s] [s [s]] [s] [s], 8日“SKGlyphs”- - - > {s、k}],“StatesDisplay”)gydF4y2Ba

下面是表达式大小序列的示例gydF4y2Ba在各种这样的进化中获得的gydF4y2Ba:gydF4y2Ba

& # 10005gydF4y2Ba

Grid[Partition[Labeled[ListStepPlot[Differences[ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][#, 1000, "SKGlyphs" -> {s, k}]], ImageSize -> 130, PlotRange -> All, Frame -> True, FrameTicks -> None, Filling -> Axis, FillingStyle -> Hue[0.56, 0.02, 0.9500000000000001], PlotStyle -> Hue[0.56, 0.68, 0.71]],文本(风格(ResourceFunction[“CombinatorTraditionalForm”][#],12 ]]] & /@ { (年代[s [s [s]] [s]]] [s] [s], s [s] [s] [s [s [s]]] [[s]], s [s] [s] [s [s [s [s] [s]]]] [s], s [s [s [s]] [s [s [s]] [s]]] [s] [s], s [s] [s] [s] [s] [s] [s [s [s]]] [s], s [s] [s] [s [s [s [s] [s]] [s]]] [s], s [s [s] [s] [s [s]]] [s [s] [s]] [s], s [s] [s] [s [s [s]]] [s [s]] [[s]], s [s] [s] [s] [s [s] [s]] [s] [s] [s] [s],s [s] [s] [s [s [s [s [s]] [s]] [s]]] [s], s [s] [s] [s [s] [s [s [s [s] [s]]]]] [s], s [s [s [s]] [s] [s]] [s [s [s]] [s]] [s]}, 4]]gydF4y2Ba

而且很有可能通过“附带”这些不停止的进化来进行计算。从你想要做的计算的说明开始。现在将其编码为无限个可能的不间断组合子进化之一的初始条件。然后运行组合子进化,直到某个特定的特性出现。然后从这一阶段的结果解码计算的输出。gydF4y2Ba

要证明S组合子能够支持通用计算,必须证明这样的东西对任何可能的计算都有效。换句话说,我们必须证明一个S组合子系统gydF4y2Ba可以模拟其他系统吗gydF4y2Ba(比如S, K组合子1)已经知道是普遍的。通过“仿真”,我们这里的意思是,可以找到一个合适的“编码器”、“检测器”和“解码器”,允许被仿真系统中的任何进化映射到S组合子系统中相应的进化。gydF4y2Ba

然而,有一个重要的警告:必须确定编码器、检测器和解码器本身不能进行通用计算。如果幸运的话,它们会以足够直接的方式运行,很明显它们不是通用的。但一般来说,要证明它们不是普遍的是很重要的。根据设置的不同,一种方法可能是表明,对于所有输入,它们必须在某个有限的时间内停止。gydF4y2Ba

如果S组合子系统不是计算通用的呢?怎么能证明呢?一种可能是证明所有的,甚至是无限的进化,只有有限的,或本质上有限的不同的形式。另一种方法是确定这种进化的任何“调制”必须总是在有限的时间内消失,因此它实际上必须与停止的计算相对应。gydF4y2Ba

另一种稍有不同的方法是,证明S组合子演化可以“求解”到某个点,在该点上,经过任意数量的步骤后,其性质可以通过一些有界计算来确定。gydF4y2Ba

我们一直在讨论用组合符“进行计算”。但这其中有一个微妙之处。因为一般来说gydF4y2Ba许多不同的可能的评估指令gydF4y2Ba为了组合子的进化。如果进化停止了,那么可以保证它总是到达相同的固定点,不管评估的顺序如何。但如果它不停止,就会有一个整体gydF4y2Ba可能序列的多向图gydF4y2Ba的结果。gydF4y2Ba

那么计算普适性是什么意思呢?就像我gydF4y2Ba讨论了其他地方gydF4y2Ba,一个强大的潜在定义是要求由组合子系统生成的多路系统能够有效地模拟由多路(或非确定性)图灵机生成的多路系统。但一个较弱的替代定义可能只是要求人们找到一些可以执行任何给定(确定性)计算的路径(例如,一些计算顺序)。或者,例如,一个可能有检测器和解码器功能,可以在某些分支或所有分支上工作,以某种方式总能重现人们想要的计算。gydF4y2Ba

S组合者挑战的操作gydF4y2Ba

我不知道这需要多长时间,也不知道会有多困难,但我希望有一天会有信息到达,成功地解决了S Combinator的挑战。这条信息必须包含什么内容?gydF4y2Ba

就我而言,最好的情况是具体的gydF4y2Ba沃尔夫拉姆语gydF4y2Ba实现解决方案的代码。如果S组合子实际上是通用的,那么代码应该提供一个gydF4y2Ba使用图灵机或元胞自动机规范的“编译器”gydF4y2Ba,并生成S组合子的初始条件,以及“检测器”和“解码器”的代码。但是我们如何验证这段代码是“正确的”呢?gydF4y2Ba

可以想象,它可能足够简单,可以直接进行人类分析。但更有可能的是,它需要某种程度的自动化分析。首先,可能只是进行显式测试。但是有人可能会尝试生成一个gydF4y2Ba自动化的证明gydF4y2Ba检测器和解码器总是会停止,甚至可能会确定这个过程所需时间的上限。gydF4y2Ba

如果S组合子不是通用的,那么我们可以通过代码来证明这一点,该代码可以“向前跳”任意数量的步骤并显式地确定结果,但它本身总是停止。或者可能有代码可以有效地实现对任何“调制”发生的情况然后证明这个代码导致的行为,比如说,总是停止,或者最终显示出完全的规律性。gydF4y2Ba

但是,可能不会有实现解决方案的显式代码,而只会有可能实现的抽象证明。可以想象,这可以以标准的面向人类的数学证明的形式出现。但我认为更有可能的是,它会足够复杂,以至于必须用系统的计算方法来表示。最后,如果要证明,就必须从某些公理开始。gydF4y2Ba

可以使用什么公理?gydF4y2Ba人们会希望gydF4y2Ba数学的标准公理gydF4y2Ba“就够了。”也许只需要皮亚诺公理。但如果需要超限归纳法,我也不会感到惊讶,因为这需要集合理论的公理。当然,也会出现一些奇怪的情况,证明是可能的,比如,一个关于连续统假说的假设,而另一个则不然。gydF4y2Ba

还有其他奇怪的事情可能发生。例如,可以证明通过无限时间运行组合进化获得的完整的无限结构可以重现任何计算,但人们可能不知道这在有限进化中是否可能。或者,只有当一棵无限树(比如说由超限数指定)作为初始条件时,才能进行构造。gydF4y2Ba

也可以想象,S组合子的行为可以对应于gydF4y2Ba中级程度gydF4y2Ba“计算能力并具有不可判定的特征,但不具有普遍性。我不认为这会发生,但如果确实如此,我会认为这是S组合挑战的一个解决方案。gydF4y2Ba

当然,还有意料之外的事情。在我gydF4y2Ba探索计算世界的经验gydF4y2Ba在过去的40年里,人们经常会遇到这种情况。这是意料之外的情况。一种似乎不可能的中间情况。一种人们从未想过的新行为形式。有时这些是最有趣的发现。但不可避免的是,它们让我们很难对“S Combinator挑战”所需要的东西给出一个明确的定义。gydF4y2Ba

不过,值得记住的是,S Combinator挑战是关于回答人类提出的问题“S Combinator计算是否通用?”最终,可能需要人类来决定某些特定的潜在解决方案是否真的能回答这个问题。gydF4y2Ba

从某种意义上说,S Combinator Challenge已经是一个百年故事了。但我当然希望这个问题能在不到100年的时间里得到解决。通过这样做,我们将学习到关于组合子和一般计算世界的重要知识。gydF4y2Ba

发布:gydF4y2Ba计算科学gydF4y2Ba,gydF4y2Ba数学gydF4y2Ba

7评论gydF4y2Ba

  1. 定理。s约简在计算上不是通用的。gydF4y2Ba
    证明。没有表示自然数的函数,它总是为零。假设有一种编码使这成为可能。选择一个编码大于0编码的数字n。现在,s -约简不能使组合变小(这是K的工作),所以对n进行编码的函数约简不能变成对0进行编码。gydF4y2Ba
    矛盾。gydF4y2Ba
    QED。gydF4y2Ba

    巴里·杰gydF4y2Ba
  2. 正式地说,S组合子本身不能用来表示所有可计算函数。具体来说,不可能仅仅从S组合子构造K组合子。S组合子永远不能消除任何项,只能重复它们。从它的定义可以清楚地看出这一点。输入表达式中的每一项在输出中至少复制一次。因此,没有“S-expression”可以做K所做的事情,至少在正式意义上没有。gydF4y2Ba

    另一方面,我相信这个问题在博客文章中得到了一定程度的解决。虽然没有正式可能仅复制K和S的行为,可能会存在一些什么K有效的等价表示,但这需要一种“封存”的术语,K会消除,这样也许显然被忽略在表示。gydF4y2Ba

    有趣的是,我昨天还在想如何构造一个数据表示来消除消除。它本质上可以跟踪计算的历史,就像可逆计算所必须做的那样。它当然不会是一个紧凑的一般表示,但它肯定可以清楚地表明什么是期望的输出相对于剩余的簿记。这也是我在这里要做的,因为我们不能期望正式地消除任何项。顺便说一句,Barry Jay提出的不能表示0的问题假设0只有一种表示。但是在不可能消除的可逆计算场景中,零可以(非唯一地)表示为相同(或至少相等)项的差。它类似于从不减少任何分数,所以任何x/x都代表单位只要x不等于零。gydF4y2Ba

    我这么做的原因是把宇宙想象成一台电脑。在我看来,物理学的可逆性意味着可逆的计算正在进行。这意味着没有任何东西被丢弃或取消,表示只是无限增长。这并不是说数值永远不会减少。只是削减保留了我们通常认为不必要的部分。这就是时间发挥作用的地方。gydF4y2Ba

    例如,考虑一个位移的可逆4-D时空计算。你可以从4个对称的时空单位向量中构造一个“基”,每个向量代表一个三维空间平移和一个正的时间位移的组合(可能以普朗克时间为单位)。加引号的原因是,只有当我们将代数限制为加法而没有加法逆时,这些向量才构成基础。这样,只有正值(和空)组合是可能的。这种增加仍然可以减少为正的时间位移和任何方向上的有效三维空间位移的组合,尽管是在稍后的时间,因此实际上只能观察到相对于其他物体的位移。从我们的角度来看,我们只需测量3-D相对位移,在大多数情况下,都会忽略时间分量。但从宇宙的角度来看,这一部分被保留了下来,正是它阻止了我们在没有时间的情况下测量空间!从物理上讲,您无法取消时间分量,那么为什么要使用允许它的数字表示呢?没有一台计算机能做物理本身做不到的事情,所以公平的做法是,只保留物理上可能的东西。gydF4y2Ba

    现在回到手头的问题……我们需要一种表示法,能够清楚地表明何时一个项从计算中有效地消除,这样当没有更多的收益时,这个过程可能会提前停止。在我的脑海中,我会尝试类似于将不需要的项封装在一个无限循环表达式中,以保持返回复制自身的副本。这种复制可以被检测到并停止,因为很明显,复制自身的表达式只能做这些。如果我们被迫从左到右求值,那么我们需要继续推“垃圾”直到所有输入都被消耗掉。然后,当只剩下自复制项时,过程可能会终止。他们可能需要在过程中吸收的不仅仅是垃圾,但从理论角度来看,只要在有效计算结束时,它仍然是一个有限的量,它需要增长,这就无关紧要了。gydF4y2Ba

    我相信可能有其他的方法来实现这一点,我想从宇宙如何计算事物的角度来思考。另一个例子是在时空中能量和动量是如何联系在一起的。如果没有正的时间能量,就不可能有非零的空间动量。反之亦然,在可逆表示中,一个没有净动量的非零能量,例如静止质量(E=mc^2)需要是一些4-D动量-能量基的正(甚至是整数)组合,类似于前面描述的位移基。同样,“抵消”的空间动量分量将保留进入计算的历史,同时允许以净零值出现,至少在3-D空间投影中是这样。这些隐藏的信息反而显示为一个正能量的质量,不能被任何物理过程消除。gydF4y2Ba

    赛斯霍伊特gydF4y2Ba
  3. 我想知道的一件事是,为什么只关注S组合子当Chris Barker已经构建了普遍的iota组合子S和K组合子都可以恢复?如果我们的目标是将语言减少到一个组合符,这是否就足够了,或者是否有一个特定的原因来关注S ?gydF4y2Ba

    赛斯霍伊特gydF4y2Ba
  4. 亲爱的杰伊先生,我对你有趣的证据有两个怀疑。gydF4y2Ba

    第一:应该有可能在所有自然数上定义一个常数为零的函数的组合表示,参见Barendregt, Lambda微积分,关于初始函数和Lambda可定义函数定义的第6章。gydF4y2Ba

    第二:s -约简可以生成“更小”的组合子(= n),然后初始“长度”:s[k][A][B] = B对于每个B个组合子。gydF4y2Ba

    所以我认为你的证据是基于未经验证的陈述,抱歉。gydF4y2Ba
    谢谢gydF4y2Ba

    蒋禄卡ArgentinigydF4y2Ba
    Mathematica用户,意大利gydF4y2Ba

    蒋禄卡ArgentinigydF4y2Ba
  5. 当Wolfram提出一个未解决的开放问题时,我希望奖金在20万到200万美元的范围内gydF4y2Ba:-)gydF4y2Ba

    迈克尔·金gydF4y2Ba
  6. 我自己的第一个攻击:我们能不能用s组合子来使用其他的组合子?再问一遍,有多少种?示例:使用s组合子压缩/折叠。为了区分s组合子,就像四色定理一样仍然通过(s组合子)就像所有四种颜色都是s组合符的一部分。gydF4y2Ba

    贾斯汀zijlstragydF4y2Ba
  7. 注意-添加:如果事情不是s组合符溢出,它必须被视为不同。gydF4y2Ba

    贾斯汀zijlstragydF4y2Ba
Baidu