简单图灵机、通用性、编码等。

(这篇文章最初是发在NKS论坛.)

以下是我在数学基础(FOM)邮件列表中与讨论有关的一些评论Wolfram 2,3图灵机奖.虽然我所说的大部分内容在NKS社区中都得到了很好的理解,但我认为在这里可能会感兴趣。


有几个人在邮件列表上转发给我关于我们的2,3图灵机奖的帖子。

我很高兴看到它引发了讨论。也许我能说几句概括性的话。

我们从简单的通用图灵机中学到了什么?

约翰·麦卡锡写道:

在20世纪50年代,我认为最小可能的(符号状态乘积)通用图灵机可以说明计算的本质。不幸的是,它没有。

我猜想,当时人们的想象是,通过发现最小的通用机器,人们会发现一些“计算的火花”——一些使通用计算成为可能的必要规则中的关键成分。(在当时,似乎仍然有可能在系统中发现“生命之火”或“智慧之火”。)

我记得当我在20世纪70年代初第一次听说《Game of Life》中的普遍性时,我并不认为它有什么特别的意义;这看起来像是一个聪明的黑客。

但是几十年后,在建立了整个框架之后一种新的科学,我有完全不同的看法。

我现在认为,计算能力的广泛传播是非常重要的。

我们在自然界中遇到的典型系统是普遍的吗?或者它们在计算上更简单?

我们能指望通过搜索可能系统的空间找到非平凡的计算行为吗?或者我们只能通过特定的设置来达到这样的行为,比如使用传统的工程方法?

我认为这些问题对科学技术的未来都是非常重要的。例如,在科学领域,它们会告诉我们,在多大程度上,我们有望为我们所研究的系统找到“计算简化”的模型。在技术方面,它们告诉我们,仅仅通过搜索“计算宇宙”,我们可以期望在多大程度上发现有趣的实用算法和其他东西。

我不认为哪个图灵机是通用的,哪个不是通用的,这些细节都很重要。然而,重要的是普遍性的普遍程度。目前我们唯一能做的就是证明图灵机的普适性和非普适性。

我们的标准直觉倾向于认为具有简单规则的系统必须以简单的方式运行。但我们通过研究计算宇宙的经验发现,这是不正确的。

所以现在的问题是要对它有一个科学的理解,并做出精确的表述。

我在这个方向上的努力产生了一个成果,我称之为计算等价原理。这是一个相当大胆的假设,有很多话可说。第十二章).

但它的预测之一是,即使在规则非常简单的系统中,普遍性也应该是可能的。我一直渴望验证这一预测。寻找小型通用图灵机是一个很好的方法。

对小型通用图灵机感兴趣还有其他原因。

也许人们甚至可以用它们作为原料,用分子等部件制造出有用的计算机。Alex Smith为2,3图灵机编写的编码显然不实用(也不打算如此)。但现代科技的一个教训是,一旦一个人知道某种东西在原则上是可能的,那么它被付诸实践往往只是时间问题。

还有一些计算机科学的理论理由让我们对小型通用机感兴趣。一个例子是理解算法复杂度和计算复杂度之间的权衡。

(例如,我在传统计算复杂性问题的实证研究中取得了一些进展,通过观察小型图灵机12.8节

但最重要的是,我认为找到小型通用图灵机的重要之处在于,它帮助我们建立关于什么类型的系统是通用的直觉,所以当我们在计算机科学、数学、自然科学或其他领域遇到系统时,我们有更好的机会知道它们是否可能是普遍的(因此,例如显示不确定性)。

如何定义普遍性?

对于任何概念,人们都希望有一个有用且可靠的定义,并以此为基础进行构建。

显然初始条件不需要一台通用计算机来设定。但它们究竟能包含什么呢?

我认为“显而易见的答案”自20世纪50年代以来已经改变了。在20世纪50年代(那绝对是在我那个时代之前),我的印象是,人们想象一台计算机的存储器——或者说是图灵机的磁带——会以某种方式在它的每个单元格中都以0开头。(事实上,即使是这样,我也怀疑当一个人启动电脑时,它的内存中可能存在随机数据,这些数据需要明确地清除。)

现在,特别是当我们研究与自然系统的对应关系时,有一个无限的0序列似乎不是很自然。为什么没有1s?或1块?(比如有整数和有理数的数字序列,等等)

我必须说,我认为最优雅的做法是用一个基本上只是重复的初始条件来建立普遍性。但是重复有什么特别之处呢?还有很多其他的模式可以想象。似乎唯一可靠的区别是模式本身是否需要通用计算来建立。

毫无疑问,一些很好的计算机科学理论可以使所有这些概念更加紧密。

也许真的存在一个“普适性水平”的层次结构——系统在准备输入时需要不同的计算水平来实现普适性。(有人可能会想象块通用vs.有限自动机通用vs.上下文无关通用,等等。)

我自己的直觉是,虽然可能存在一些边界情况,即某些形式的输入可能具有普遍性,而其他形式则不具有普遍性,但这种情况将非常罕见——在大多数情况下,一个系统要么是“完全普遍的”,要么根本不具有普遍性。

很可能在某些情况下,特殊形式的投入妨碍了普遍性。甚至可能是无穷序列的0阻止了“奖品”2,3图灵机的通用性(它在0字段中有相当特殊的行为)。但我猜,如果考虑更健壮的编码类,那么使用哪个类通常无关紧要。

我猜情况和中等程度差不多。原则上有一些系统显示出不可判定性而不是普遍性,但这是极其罕见的。

当然,如果有一个简单的图灵机或其他系统,从根本上表明了不可判定性而不是普遍性,那就太棒了。尽管我有点怀疑这在任何稳健的意义上是否可能。毕竟,如果我们看看现有的中级学位的例子,它们似乎总是具有“内在普遍性”。

好吧,那么2,3 "奖"图灵机呢?Alex Smith的证明是关于由相当复杂(但非普遍)的计算产生的初始条件的普适性。它能推广到更简单的初始条件吗?我当然希望初始条件能简单得多。

它们会是嵌入无限零的海洋中的有限区域吗?显然我不知道。虽然找出答案会很有趣。

顺便提一下,我认为还有其他2、3(和3、2)图灵机也是通用的。它们中的一些对于无穷序列的0有非常不同的行为。

机器越简单,编码就会越复杂吗?

我们的标准直觉总是倾向于,我们想要得到的东西越复杂,我们要输入的东西就越复杂。

但最重要的一点是一种新的科学(封装,例如,在计算等价原理)是,这通常不是真的。

Alex Smith对2,3图灵机的编码既复杂又低效。但当一个人有一个简单的基础系统时,这是不可避免的吗?

我不这么想。但到目前为止,我还没有确凿的证据。

不过,这里有一个略微相关的观察。

我做了一件事一种新的科学(并且认为这相当不错)就是为布尔代数找到最简单的(方程式)公理系统。原来只是一个公理:((公元前)。)。(b。(意向书)。b)) = =。(见12.9节

现在的问题是:基于这个小公理系统的证明是否必然比基于更大(“工程的”)公理系统的证明要长?(例如,他们是否总是必须首先证明更大的公理系统的公理作为定理,然后再从那里继续下去?)

我的经验是,更大的公理不一定更有效。(这可能不是一个可靠的结果;这可能取决于定理证明算法的细节。)

事实上,正如http://www.wolframscience.com/nksonline/page-1175d-text表明,即使是单公理公理系统也不是非常低效——至少在它证明了交换性之后。我发现的最小公理系统明确地包含交换性- {(a.b).(a.(b.c))==a, a.b==b。A}——似乎和任何东西一样高效。

这与编码的通用性没有直接关系,但也许它给出了一些指示。

我试图获得编码证据的另一种方法是,通过使用,看看我能在覆盖有限元胞自动机计算的空间中走多远基于不同长度块的编码

令人鼓舞的是,我认为不通用的细胞自动机并没有涵盖很多内容,但我认为通用的细胞自动机却涵盖了很多内容。

我稍微研究了一下更复杂的规则是否允许更小的块集(“更小的编码”)覆盖给定的细胞自动机计算空间区域。却没有找到任何证据。

我不太确定一般如何表述编码的复杂性问题。

毕竟,对于给定的系统,不可避免地会有难以编码的计算。

但问题是,在给定的系统中,“合理的”或“有趣的”计算是否可以以一种简短的方式进行编码。

这有点像问一种编程语言需要什么才能让你以一种简短的方式编写你想要的程序。

对于像我这样的语言设计师来说,这是一个重要的实际问题。我希望能有一个更好的理论公式。

(我们的“开放代码”示范项目有一些非常有趣的例子,说明了简短的Mathematica程序能做什么,偶尔不能做什么……)

获奖之后会发生什么?

显然,我花了大量的精力来追求我对NKS的兴趣,并写下我所做的事情。我认为这是很重要的事情,而且我一直热衷于让其他人参与进来。

我们在这方面取得了很多成功暑期学校.但有了这个奖项,我们想尝试用另一种方式来刺激这个领域。

到目前为止,这个奖项的实验似乎非常成功。

这个奖品是图灵机的终点吗?绝对不会。关于它还有很多需要研究和建立的地方。也许它会被证明在某种意义上它不可能是普遍的。也许会有更简单的普适性证明。也许有人会“简化到数论”,或者从空白的磁带中找出一些类似的细节行为。尽管它有如此简单的规则,但它显然是一个值得研究的丰富系统。

看到这个奖项的发展,我现在有动力考虑设立其他奖项……

Baidu