科学:公共生活

(这篇文章最初发表在沃尔夫勒姆博客.)

我们的2007NKS暑期学校大约两周前开始的,我在那里的一个角色是展示如何NKS完成了。

在过去,以任何一种活生生的方式展示这一点都是非常不现实的。但是计算机实验,尤其是计算机实验数学软件现在,人们可以在现场观众面前实时做出真正的发现。

我现在已经做了几十个“现场实验”(在这里是2005年的一个账户)。我的计划如下。在现场实验前的几个小时到几分钟,我提出了一个我很确定以前从未研究过的主题。然后,在我真正面对现场观众之前,我会尽量避免去想它。

然后,一旦实验开始,我就有有限的时间去发现一些东西。只是跑步数学软件.最好能得到观众的一点帮助。偶尔也能得到网上参考资料的一点帮助。

每一次现场实验都是一次冒险。几乎每到一半的时候,事情看起来都很糟糕。我们试过很多东西。我们已经打开了很多线程。但什么都没有。

但是,不知何故,事情几乎总是设法走到一起。我们设法发现了一些东西。这通常很有趣。(现在仍有论文发表,这些论文是基于我在我们第一所暑期学校(回到美国)做的现场实验2003).

我通常把我在每所暑期学校的第一个现场实验做成一个“纯NKS”:对计算宇宙中一些简单程序的抽象研究。

今年,我决定看一看最近有人提醒我的一个“老栗子”:一个简单的计划(尽管当时人们并不这么认为),实际上早在1920年就开始了调查。

故事是这样的。1920年,普林斯顿大学一位名叫埃米尔·波斯特(Emil Post)的年轻数学研究生试图理解怀特黑德(Whitehead)和罗素(Russell)的结构数学原理当前位置他们试图将数学基础形式化的非常复杂的尝试。波斯特做了任何一个优秀的现代NKS学生都应该做的事情:他尽可能地简化事情。

最终,他提出了一个抽象的系统,他认为这个系统可以捕捉怀特黑德和拉塞尔所做的事情的本质。他的系统是这样工作的。它有一个0和1的序列,比如0111010101。它按照一系列步骤进行。在每一步中,它都会切断序列中的前三个元素。然后,如果这些元素中的第一个是0,则在末尾追加00,如果第一个元素是1,则追加1101。

它继续这样做。

很简单,是吗?波斯特早在1920年就开始使用这个系统了。他认为他能够“破解”这很容易。但并不是那么简单。他发现这个系统可以做一些相当复杂的事情。实际上,他不知道这个系统在做什么。经过几个月的工作,他放弃了。他决定写一篇关于更传统的数学领域的论文。

也许如果他一直坚持下去,波斯特可能早在1920年就想出了NKS。事实上,几年后,波斯特也差一点发现了艾伦·图灵在图灵机器上的发现。在20世纪40年代早期,波斯特再次回到了他的“标签问题”(他称之为类似NKS的系统)。但他从未破解过。在经历了一段艰难的生活后,他于1954年去世。

所以,我决定看看我们现在如何处理埃米尔·波斯特1920年的问题。我在将近15年前就已经研究过这个问题了NKS书籍,但我认为数学软件6.,我可以走得更远。

下面是我做的现场实验中完整笔记本的屏幕截图:

现场实验笔记本屏幕截图

如果你看这样的图,序列长度和时间

序列长度与时间的关系图

你知道为什么波斯特出了问题。从11010101011000011001开始,在系统稳定到周期性行为之前,它需要超过2000个步骤。当然,这只需要几分之一秒就可以发现数学软件今天。再看看其他许多案例,看看他们是否安定下来。

在实验过程中,我们发现了很多关于Post标签系统的新东西。但很抱歉,我们没有完全破解它。事实上,我猜它至少和我们最近研究的2,3图灵机器一样难破解.

但我们所做的一件事是看看Post的系统在某种意义上应该是什么:我们发现了Post类型中最简单的标记系统,它显示了复杂的行为。

它在每一步只删除两个元素,并添加01或100。非常简单。但它的序列长度是从10开始的:

从10开始的序列长度图

事实上,这不是序列的长度。奇怪的是,我们发现序列长度似乎平均增加了Sqrt[2] -每一步1个(这将是有趣的证明)。因此,上面的图是“去渲染”序列长度。

我们在美国东部时间6月25日17:12:12发现了行为复杂的最小标记系统。这是一个非常有趣的系统。例如,据我们所知,它具有完美的随机性。非常显著。也许在某些方面,它是迄今为止发现的最简单的系统。

继续研究它会很有趣。我希望人们现在也会这么做。这将有助于撰写一些非常有趣的论文,我期待着阅读…

但事实上,我被告知我们必须在下午5:30之前完成,否则每个人都会错过晚餐。所以我停了下来。在几个小时的现场实验中,我们至少发现了一件有朝一日会出现在教科书中的东西。

我现在终于有时间写这篇关于我们实验的文章了,在写这篇文章的时候,我想我应该使用手机>笔记本历史记录…中的菜单项数学软件看看我们实验的实际历史。

这是我得到的情节:

活体实验的历史

它几乎像是我们正在研究的系统之一。但事实上,它显示了我们是如何建立实验笔记本的。每个点代表一个区域的变化细胞在笔记本上。单元格沿页面向下运行,时间在页面上运行。

所以我们看到的是,我们开始有点慢。然后真的加速了。然后在下午4点左右被卡住了(我的“中途点”现象)。但最后在下午5点左右,我们又退出了,一点之后,我们有了主要的发现。甚至连晚饭都不缺。

Baidu