Discrete Thoughts


于是我写了个网站给她当生日礼物

由于这个月拔智齿导致金融危机(当然实际情况是每个月我都金融危机),蒂凡尼估计是比较困难。

今年是Alan Turing诞辰100周年,我办公室对门一直挂着一个庆祝他老人家诞辰的会议海报。啊哈!我何不写个网站给她当生日礼物呢?在网站上大家可以创建虚拟的图灵机,并且能够发现和分享其他人的发明。

那什么是图灵机呢?

想象你有一条无穷长的纸带,纸带从左到右被分割成了无数个小格子,一个小机器人正辛勤地在纸带上工作。因为是小机器人,所以它只能看到一个格子上写着什么字。这个小机器人还有一个专门记录当前自己所处的状态的记忆单元。除此以外,机器人始终遵循着一个指令列表行事。指令列表的每一行写的内容是:“如果我看见这个字符,并且在这个状态,我就写下那个字符,并且调整到那个状态,最后左右移动一步或者原地不动。”如果在给小机器人设定一个初始状态的话,一台图灵机就完成啦。

下面就是传说中的教程。首先登录awesometuringmachine注册帐号,注册成功并登录之后选择菜单栏 My Turing Machine 下的 Create New,这里要创建的图灵机是一个只会左右移动的图灵机,所以取名 Busy Beaver。在 Table of Rules 中设定指令列表,为了实现这种一左一右的抽风行为,需要如下两条指令:

  1. 如果处在状态0并位于空白格子,则切换到状态1并右移。
  2. 如果处在状态1并位于空白格子,则切换到状态0并左移。

最后将初始状态设置为0就可以了。生成Busy Beaver的截图如下。

注意,初始情况下所有的格子都是blank的!另外在 view more options 可以设置纸带上的初始值。另外,空格(也就是选择symbol时的一个字符)和blank不是一个概念。

目前整个系统对于空格的存储还有一些小的 bug,所以大家目前尽量不要选择空格,而是用blank。这个 bug 会在这周末修复。

Busy Beaver
Busy Beaver

保存后点击 Play 就可以看到一左一右的效果了,是不是很二呢?这里还有一个更二的例子 Two to Infinity,这个图灵机的主要功能是写下2之后不断右移……

当然我们也能做一些浪漫的图灵机。笨笨!生日礼物猛击这里

具体的剖析参看 Awesome Turing Machine

comments powered by Disqus
← prev next →