科技: 人物 企业 技术 IT业 TMT
科普: 自然 科学 科幻 宇宙 科学家
通信: 历史 技术 手机 词典 3G馆
索引: 分类 推荐 专题 热点 排行榜
互联网: 广告 营销 政务 游戏 google
新媒体: 社交 博客 学者 人物 传播学
新思想: 网站 新书 新知 新词 思想家
图书馆: 文化 商业 管理 经济 期刊
网络文化: 社会 红人 黑客 治理 亚文化
创业百科: VC 词典 指南 案例 创业史
前沿科技: 清洁 绿色 纳米 生物 环保
知识产权: 盗版 共享 学人 法规 著作
用户名: 密码: 注册 忘记密码?
    创建新词条
科技百科
  • 人气指数: 10886 次
  • 编辑次数: 3 次 历史版本
  • 更新时间: 2009-07-09
高兴
高兴
发短消息
方兴东
方兴东
发短消息
相关词条
戴夫·海厄特
戴夫·海厄特
最佳编程语录大全
最佳编程语录大全
程序员笑话大全
程序员笑话大全
下一代程序员
下一代程序员
女程序员
女程序员
彼得·诺维格
彼得·诺维格
Russ Cox
Russ Cox
15名程序员界性感的奇葩
15名程序员界性感的奇葩
Mike Kruzeniski
Mike Kruzeniski
Jeff Fong
Jeff Fong
推荐词条
希拉里二度竞选
希拉里二度竞选
《互联网百科系列》
《互联网百科系列》
《黑客百科》
《黑客百科》
《网络舆情百科》
《网络舆情百科》
《网络治理百科》
《网络治理百科》
《硅谷百科》
《硅谷百科》
2017年特斯拉
2017年特斯拉
MIT黑客全纪录
MIT黑客全纪录
桑达尔·皮查伊
桑达尔·皮查伊
阿里双十一成交额
阿里双十一成交额
最新词条

热门标签

微博侠 数字营销2011年度总结 政务微博元年 2011微博十大事件 美国十大创业孵化器 盘点美国导师型创业孵化器 盘点导师型创业孵化器 TechStars 智能电视大战前夜 竞争型国企 公益型国企 2011央视经济年度人物 Rhianna Pratchett 莱恩娜·普莱契 Zynga与Facebook关系 Zynga盈利危机 2010年手机社交游戏行业分析报告 游戏奖励 主流手机游戏公司运营表现 主流手机游戏公司运营对比数据 创建游戏原型 正反馈现象 易用性设计增强游戏体验 易用性设计 《The Sims Social》社交亮 心理生理学与游戏 Kixeye Storm8 Storm8公司 女性玩家营销策略 休闲游戏的创新性 游戏运营的数据分析 社交游戏分析学常见术语 游戏运营数据解析 iPad风行美国校园 iPad终结传统教科书 游戏平衡性 成长类型及情感元素 鸿蒙国际 云骗钱 2011年政务微博报告 《2011年政务微博报告》 方正产业图谱 方正改制考 通信企业属公益型国企 善用玩家作弊行为 手机游戏传播 每用户平均收入 ARPU值 ARPU 游戏授权三面观 游戏设计所运用的化学原理 iOS应用人性化界面设计原则 硬核游戏 硬核社交游戏 生物测量法研究玩家 全球移动用户 用户研究三部曲 Tagged转型故事 Tagged Instagram火爆的3大原因 全球第四大社交网络Badoo Badoo 2011年最迅猛的20大创业公司 病毒式传播功能支持的游戏设计 病毒式传播功能 美国社交游戏虚拟商品收益 Flipboard改变阅读 盘点10大最难iPhone游戏 移动应用设计7大主流趋势 成功的设计文件十个要点 游戏设计文件 应用内置付费功能 内置付费功能 IAP功能 IAP IAP模式 游戏易用性测试 生理心理游戏评估 游戏化游戏 全美社交游戏规模 美国社交游戏市场 全球平板电脑出货量 Facebook虚拟商品收益 Facebook全球广告营收 Facebook广告营收 失败游戏设计的数宗罪名 休闲游戏设计要点 玩游戏可提高认知能力 玩游戏与认知能力 全球游戏广告 独立开发者提高工作效率的100个要点 Facebook亚洲用户 免费游戏的10种创收模式 人类大脑可下载 2012年最值得期待的20位硅谷企业家 做空中概股的幕后黑手 做空中概股幕后黑手 苹果2013营收 Playfish社交游戏架构

比尔·高斯珀(Bill Gosper)麻省理工的计算机专家,早期传奇黑客之一。

个人主页:http://gosper.org/

目录

[显示全部]

个人简介编辑本段回目录

Ralph William Gosper, Jr., (born 1943) known as Bill Gosper, is an American mathematician and programmer from Pennsauken Township, New Jersey.[1] Along with Richard Greenblatt, he may be considered to have founded the hacker community, and holds a place of pride in the Lisp community. He is also noted for his work on continued fraction representations of real numbers, and for suggesting Gosper's algorithm for finding closed form hypergeometric identities.

(图)Bill GosperBill Gosper

Gosper enrolled in MIT in 1961, and received his bachelor's degree in mathematics from MIT in 1965. After taking a course on programming in his second year with John McCarthy, Gosper became affiliated with the MIT AI Lab. His contributions to computational mathematics include HAKMEM [1] and the MIT Maclisp system. He also made major contributions to the Macsyma computer algebra system at MIT, later working with Symbolics and Macsyma, Inc. on the greatly improved commercial versions.

He became intensely interested in the Game of Life shortly after John Horton Conway had proposed it. Conway conjectured on the existence of infinitely growing patterns, and offered a reward for an example. Gosper was the first to find such a pattern (specifically, the Glider gun), and won the prize. Gosper was also the originator of the hashlife algorithm that can speed up the computation of Life patterns by many orders of magnitude.

In the 1970s Gosper moved to California for a three year stint at Stanford, where he lectured and helped Donald Knuth write volume II of The Art of Computer Programming.

Since that time, he has worked at or consulted for Xerox PARC, Symbolics, Wolfram Research, the Lawrence Livermore Laboratory, and Macsyma Inc.

Gosper has created numerous packing problem puzzles, such as "Twubblesome Twelve".

STL之父A.Stepanov专访编辑本段回目录

问:
我认为STL和泛型编程标志着一个不同于一般C++编程风格(我发现这种风格基本上是从SmallTalk继承过来的)的新起点。你赞成这个说法吗?

答:
是的。STL不是面向对象的。我认为面向对象和人工智能差不多,都是个骗局。我已经看到了来自那些OO的人们写的“有趣的”代码。从某种程度上说,我对人工智能(AI)有偏见。我听说好多关于MIT AI实验室的一帮人的东西了,他们真正干了一些基础性的工作:Bill Gosper的Hakmem是程序员最好的读物之一。AI或许没有一个严肃的基础,但它制造出了Gosper和Stallman(Emacs), Moses(Macsyma)和Sussman(Scheme, 连同Guy Steele)。我发现OOP在技术上是荒谬的,它妄图依照因单个类型而异的接口来分解世界,为了处理实际问题你需要多种代数方法─横跨多种类型的接口族;我发现OOP在哲学上是荒谬的,它声称一切都是对象。即使真的是这样这也不是很有趣,说一切都是对象跟什么都没说一样;我发现OOP的方法论是错误的,它从类开始,就好像数学要从公理开始一样。你不是从公理开始,你是从证明开始。直到你找到了一大堆相关证据后你才能归纳出公理,你是以公理结束。在程序设计方面存在着同样的事实:你要从有趣的算法开始。只有很好地理解了算法,你才有可能提出接口以让其工作。

细胞自动机编辑本段回目录

细胞自动机是什么意思呢?比如说我们下象棋、下围棋,棋盘上有一个一个方格,上边放一个棋子,就可以相当于一个一个细胞。然后又一定的规则,按这些规则动的话就可以产生出棋局。细胞增值机的思想就是这样一个思想,他希望把这个世界划成一个一个方格,方格里面可以有物质,这些物质交互作用,如果说有一定的配置,最后这个配置就能够实现自组织功能,就像我们的生命,实际上也就是一个细胞自动机。

(图)Bill GosperBill Gosper

这样,他就把生命和机器抽象成一个细胞自动机。然后,他构想了一个不仅仅是一般的细胞自动机,而是一个能够自我复制的细胞自动机。它有三个部分,一个是存储带,一个是建构器,在一个就是受建构器指导的建构臂。

图中模型的左下角是一个存储带控制器,信息都在这里面,左上方是建构器,右上方是建构臂。这样一个系统就可以实现自我繁殖,而这种自我繁殖,冯·诺伊曼本人非常喜欢这个概念,因为这个系统既简单抽象,完全可以进行数学分析,同时又丰富多彩,使他能够解决他想解决的问题。不过,非常遗憾的是,冯·诺伊曼还没有完成自己的工作,就因为癌症而离开了人世。应邀编辑他在这方面工作的科学家勃克斯(A. W. Burks)填补了冯·诺伊曼所未完成的细节,于1966年以《自我繁殖的细胞自动机理论》为名结集出版。

勃克斯证明这个系统原则上可以在计算机上进行模拟,尽管由于它非常复杂,迄今还没有人在任何种类的真实的计算机上成功地完成这种建构。但是冯·诺伊曼的自我繁殖的自动机确实存在的事实说明,一旦我们把自我繁殖作为生命的独一无二的特征,那机器也完全可以做到这一点,也就是说我们完全可以创造出一个机器,让这个机器实现自我繁殖。当然,这个系统会非常非常复杂,每一个细胞代表一种状态需要29种状态。后来人们不断地简化,其中有人就简化出了非常简单的自我复制的结构,后面我们会说。

冯·诺伊曼去世之后,很少有人继续他的工作。这一方面是因为这个问题本身是一个非常艰深的问题,像冯·诺伊曼这样的天才都难以完成,其他人完成就更加困难;另一方面是因为当时的计算机的能力有限。因此,冯·诺伊曼未完成的工作,在他去世多年后,才由康韦(John Conway)、沃弗拉姆(Stephen Wolfram)和兰顿(C. Langton)等人进一步发展——学数学的人可能对他们都非常熟悉了。其中剑桥大学的康韦研究了一个“生命”游戏的程序,这个程序很有意思,引起了广泛的讨论。这个程序由几条简单的规则控制——这是两条规则,非常简单的两条规则:第一,一个活的细胞保持活的状态,如果它具有2个或3个活的邻居;否则它就变成死的状态;第二,一个未被占据的死的细胞变成被占据的活的细胞,如果它恰好具有3个活的邻居。它就是根据这两条规则控制,有了这两条规则,然后就让这个系统像一个棋盘一样,给它一个初值,然后看下一个状态是什么样子,再看下下个状态是什么样子,最后产生了一个非常复杂的结构。

(图)游戏游戏

这一意想不到的结果吸引了一大批计算机科学家研究“生命”程序的特点。其中,我们知道有一个叫Scientific American,一个非常有名的杂志,它上面曾经有一个比赛,编出好玩的程序可以奖励1美元。虽然很少,但有好多好多人去玩——首先,如果能在Scientific American上发表一篇文章就很好了,所以说这些人也不是为了钱,但有了这个钱以后很多人都去参与。结果最后证明了细胞自动机与图灵机等价——厉害不厉害?你看,很简单的一个东西,跟一个计算机、图灵机可以等价。当然,这需要一个无限大的“棋盘”。这也就是说,给定适当的初始条件,细胞自动机可以模拟任何一种计算机——这个结论很重要。因为图灵机理论上被定义为具有无限磁带的计算系统,原则上可以执行任何计算。

这就是“生命”游戏的结果。并且康韦还是给他的规则作出了一个“生物学”的解释——它为什么叫“生命”游戏。他的规则有三个:第一个叫生存——一个活的细胞要继续生存,至少需要2到3个活的邻居,因为生命需要生命,生命需要从其它生命那里得到它的食物并且繁殖;死亡——然而,如果一个细胞的活的邻居多于3个,它就死亡,因为生命的资源有限,过度的拥挤导致细胞没有生存下去的足够的资源;还有出生——如果一个未被占据的细胞恰好具有3个活的邻居,生命就会在那里出现,或者通过出生,或者通过移民。这就是它为什么叫“生命”的原因。

利用这个生命游戏可以构建计算机。上边这个结构叫Glider Gun,就是“滑动的枪”。用这个结构可以产生计算机的非门。同时我们也可以用生命游戏上的一些特殊的变化构造出与门、或门,通过这种构造,制造出“生命”游戏的计算机,可以对这个计算机进行编程,然后可以让它运行程序。

所以,面对“生命”这个令人惊异的宇宙,高士伯(Bill Gosper)——高士伯是MIT的一个计算机专家,他赢得了康韦的那个大奖,就是Scientific American上的那个——他就说:“开始的时候,我们不清楚,在这种宇宙中可能发生的事情是否像在我们的宇宙中可能发生的事情差不多一样多。可是接下来,仅仅通过一步步的小的发现,一点一点地,我们清楚地看到,我们能够描述的任何事情都能在‘生命’中发生。”

(图)Bill GosperBill Gosper

康韦自己也曾经自信地认为,任何可以想象得到的生命形式,不管是现实的还是非现实的,都可以在他的“生命”上突现出来。他说:“在足够大的规模上,你将真正看到活的配置;看到真正的生命,无论什么理性的定义你愿意给予它。演化,复制,为了领土而斗争,变得越来越聪明,撰写学术上的Ph.D论文。毫无疑问,在一个足够大的板子上,在我心里有这种事物将发生。”

这就是说,康韦认为他的“生命”游戏看似简单,但是它可以产生出要多复杂就有多复杂的东西,最后能产生出意识——能不能呢?那么下边我们还要进一步地说。

在康韦之后,80年代,美国的一个著名数学家沃弗拉姆——他是美国一个著名程序公司的总裁,他在这方面发了大财,他作为一个数学家,凭着编的一个程序,成立了一个巨大的公司,全球都在卖他这个软件——而他自己对细胞自动机的研究很感兴趣,他在这个领域也是非常著名的一个科学家,他出版了一本书叫《一种新科学》。他对细胞自动机分类,发现康韦,或者我们所研究的细胞自动机有四种类型:类型Ⅰ的细胞自动机可以演化为一个均质的状态;类型Ⅱ的细胞自动机通常演化到周期性的循环模式;类型Ⅲ的细胞自动机可以演化为“混沌”模式;类型Ⅳ的细胞自动机可以演化成一个非常复杂的结构。并不是所有的细胞自动机都能产生在科学上有意义的结构,只有一部分可以。所以只有在类型Ⅳ的细胞自动机中发现有突现行为,因此类型Ⅳ的细胞自动机是最有趣的,康韦的“生命”游戏就是一个非常有名的属于类型Ⅳ的细胞自动机。

朗顿的人工生命游戏编辑本段回目录

   虽然克里斯·朗顿对人工生命的诞生已经记不清确切的日期了,但却仍然清楚地记得那一时刻。那是在1971年底,或1972年初,反正是在冬天。他就像个标准的计算机狂那样,独自一人呆在波士顿麻省综合医院的六层楼上,坐在心理学系的一架像书桌那么巨大的PDP-9型计算机的控制台前,凌晨三点了还在修正计算机编码的错误。
   他说,不管怎么说,在那个待殊的夜晚,我正在修改编码错误,因为明知这一阵子他无法在机器上运行任何东西,所以他就从计算机的大阴极射线管前面的盒子里抽出其中的一卷纸磁带,把它插入磁带阅读器,开始在计算机上运行“生命游戏”。

(图)Bill GosperBill Gosper

   这是他最喜欢的计算机游戏之一。朗顿说:“我们从比尔·高士泊(Bill Gosper)小组那儿弄到了这个软件程序,他们在麻省理工学院玩‘生命游戏’。我们也在玩这个游戏。”这个游戏有不可抗拒的诱惑力。这个前些年由英国数学家约翰·康卫(John Conway)开发的程序不是真的可以让你玩的游戏。它更像是一个可以按照你的意愿演化的缩微宇宙。开始时,计算机屏幕上只出现这个宇宙的一个影像:一个平面坐标方格上布满了“活着的”黑方块和“死了的”白方块,最初的图案可以任你摆布。但一旦你开始运作这个游戏后,这些方块就会根据很少几条简单规则活过来或死过去。每一代的每一个方块首先要环顾其四周的近邻,如果近邻中早就有太多活着的方块了,则这个方块的下一代就会因为数额过剩而死去。如果其近邻中存活者过少,则这个方块就会因为孤独而死去。但如果其近邻中存有两个或三个“活着的”方块,比例恰到好处,则这个方块的下一代就能存活下去。也就是说,要么是这下一代已经活着,能够继续存活下去,如果不是这样,就会产生新的一代。
   就这么简单。这些规则只是一种漫画式的生物学。然而“生命游戏”的奇妙之处在于,当你把这些简单的规则变成一个计算机程序之后,就好像真的能够让计算机屏幕活起来。与当今你所能看到的计算机屏幕相比,这个游戏的动作相当缓慢、迟钝,就好像是让录像机用慢动作重播一遍似的。但如果你用心观察,就可以看到计算机屏幕沸腾着各种活动,就像是在一台显微镜下观察一滴池塘水里的微生物。开始时你可以随意设置一些活着的方块,可以观察到它们如何很快自组织成各种连贯一致的结构。其中有的结构翻滚不已,有的结构的振荡有如野兽呼吸。你还会发现“滑翔机”,即一小簇以常速滑过屏幕的活细胞。你还会看到稳定地发射出新的滑翔机的“滑翔机枪”,以及在那里气闲心定地吞食滑翔机的其他结构。如果你走运的话,甚至还可能看到《爱丽丝梦游仙境》里的那种“切夏猫”,它缓慢地销声匿迹,只留下微笑和足痕。每重玩一次,出现在屏幕上的图案都会有所不同,没有人能够穷尽其可能性。朗顿说:“我看到的第一个图案是大而稳定的宝石型的结构。但当你从外部加入一个滑翔机,就会打乱这个完美无缺的晶体美。其结构就会慢慢消亡至无影无踪,就好像滑翔机是一种外来的传染病。这就好像是安德洛墨达的世系一样。”
   所以那天晚上,计算机在出声地运转,计算机屏幕上活跃着各种小图案,而朗顿在修改编码错误。“有一次我抬头扫了一眼,计算机屏幕上的生命游戏正在弯弯曲曲地逝去。然后我重又扫了一眼我正在修改的计算机编码。这时我颈后的汗毛倒竖了起来。我感到还有其他人在这个房间里。”
   朗顿回头环顾,以为他的一个同事正偷偷站在他身后。这是一间拥挤不堪的屋子,放有PDP-9型机的巨大的蓝色机柜、立着许多放置各种电子设备的架子,还堆放着一台老式脑电图记录机和示波管。有一些箱子挤在角落里,电线和管子长长地拖曳满地,还有许多从未使用过的东西。这是真正的计算机迷们的天堂。但并没有人站在他背后,没有人藏在那里,他完全是一个人呆在这里。
   朗顿回过头来看计算机屏幕。“我意识到,一定是‘生命游戏’在捣鬼。计算机屏幕上的某些东西是活生生的。我无法表达我在那一刻的感觉,我区分不出什么是硬件,什么是过程。我从某种深层次上认识到,在计算机上发生的一切和在我肉体上发生的一切其实并没有很大的区别。计算机屏幕上所显示的确实是这两件事的同一种过程。”

用 Java 语言进行算法作曲编辑本段回目录

利用计算机、数学和 Java Sound API,加入一些 Java 代码,就可以制作出一些独特迷人的音乐来。IBM 专职软件工程师 Paul Reiners 展示了如何用 Java 语言实现一些基本的算法作曲。他给出了代码示例和由 Automatous Monk 程序所生成的 MIDI 文件,这个程序使用了开放源代码 jMusic 框架,以一种名为细胞自动机的数学结构为基础进行作曲。

(图)HAKMEMBill Gosper

很多计算机程序员都是很出色的音乐家,很少有组织不起像样的室内乐队的软件公司。不过,许多程序员/音乐家可能没有意识到这样一个能让他们的职业和业余爱好统一起来的有意思的领域:算法作曲。算法作曲将严格的、定义良好的算法应用到作曲过程中。 细胞自动机(Cellular automata,CA)??这是一种随时间而进化的数学结构??为算法作曲展现了一条迷人的大道。计算机特别适合计算细胞自动机(CA)的进化并以图形方式显示它们。还可以用声音表现进化,包括音乐。但是寻求将 CA 进化映射为动听和有意思的音乐不是一个简单的问题。本文展示了用 Java 语言进行基于 CA 的作曲的一些技术,并探讨了得到特别出色结构的某些映射。

细胞自动机概述
CA 包括:

细胞矩阵或者网格,每个细胞可以处于有限种状态中的一种。
定义细胞状态如何随时间更新的规则。
细胞矩阵可以有任意多维。给出一个细胞和它的邻居在时间 t 时的状态,规则会决定在时间 t + 1 时细胞的状态。(在分析了几个具体例子后会看得更清楚。)

基本细胞自动机
在本文中我将集中讨论一维细胞自动机,它的细胞可以有两种状态:0 或者 1。因为 CA 是一维的,所以可以将它想像为一行细胞。细胞在时间 t + 1 的值将只取决于这个细胞和它的左右邻居在时间 t 时的值。这种 CA 称为 初级细胞自动机。

(图)Bill GosperBill Gosper

CA 图使用白表示 0,黑表示 1。最上面一行显示这个细胞和它的左右邻居可以有的八种颜色组合。底下一行显示中间这一个细胞下一步的颜色。例如,考虑图 1 中第四个方块。在这个方块中,可以看到如果细胞是白色的,它的左邻是黑色的,右邻是白色的,那么这个细胞在下一步将是黑色的。习惯称它为 150 规则(rule 150):如果想像黑白细胞分别表示二进制 0 和 1,那么底下一行就是加上二进制形式的十进制数 150。图 1 是 150 规则的虚拟表示。用音乐表示 CA 时,150 规则会生成一些有意思的曲调,因此在本文中我将用它作为例子。

图 1. 150 规则

现在,考虑一个 150 规则 CA,开始时,除了中间的细胞为黑色,其他所有细胞都是白色。这个 CA 会按照图 2 所示的一系列步骤进化。

图 2. 150 规则步骤序列

注意尽管自动机是一维的,但是用一组连续的行从上到下显示它的进化。图 2 显示 CA 前五步的进化(包括初始状态)。可以看到每一个细胞的颜色都是由上一行中它自己的颜色和最近的邻居的颜色根据 150 规则所决定的。同时,还要注意考虑一行中所有细胞的值是在进化的每一步中同时更新的。

图 3 显示 CA 在 100 步进化后的样子:

图 3. 150 规则 100 步后

图 3 中 CA 的进化碰巧是对称的,但是并不是所有 CA 进化都是对称的。

Wolfram 对细胞自动机的研究
CA 半个世纪以来一直是研究的对象。Stanislaw Ulam 和 John von Neumann 于 20 世纪 40 年代发明了 CA 的概念,并于 40 和 50 年代作出了很多重要的发现。John Horton Conway 和 Bill Gosper 于 70 年代对 Conway 发明的一种称为 Life 的特殊二维 CA 进行了更深入的研究。Stephen Wolfram 于 80 年代开始研究 CA(请参阅 参考资料)。

通过研究初级细胞自动机,Wolfram 发现简单的机制可以产生出复杂的行为。例如,考虑 30 规则。像所有初级细胞自动机一样,它的定义??如图 4 所示??是相当简单的:一个小图就可以完全定义它。

图 4. 30 规则

不过,30 规则所产生的进化是相当复杂的。图 5 显示了使用 30 规则时,这个 CA 100 步后的进化。

图 5. 30 规则 100 步后

分析了 256 个初级 CA 和其他更复杂的 CA 后,Wolfram 发现 CA 可以分为四类。数学家和作家 Rudy Rucker 在其报告“Things Computer Science Tells Us About Philosophy”中准确地描述了这四种类型(请参阅 参考资料)。

第 1 类:恒定。 (所有种子都“死了”)
第 2 类:重复。 (循环,条带)
第 2A 类: 嵌套。(正则分形)
第 3 类: (伪)随机。 (激变)
第 4 类: 复杂。 (“不规则”。滑行。 一般性计算)

Wolfram 作出了似乎有道理的声明,大多数第 3 类和第 4 类 CA 可能是 无法省略计算的(computationally irreducible):给出一个初始状态,要找出某一细胞在第 n 步时的值,必须从初始配置开始,完成所有 n 步计算。就是说,没有公式或者快捷方式可以预测 CA 的未来状态。

(图)Bill GosperBill Gosper

音乐之外
CA 的计算能力是否可以用于作曲以外的地方呢?请看侧栏“细胞自动机的应用”。

CA 的计算能力
此外,Wolfram 和 Matthew Cook 还证明了 110 规则在计算上等同于一个一般性图灵机。(之前 Conway 对 Life 证明了这一点。)即,可以用 110 规则计算任何一般性图灵机可以计算的函数。这对于其他第 4 类的初级 CA 可能也成立。就是说,一些 CA 尽管定义很简单,但是可以用于执行任何所需要的计算。

一个未决问题
当然,CA 是纯数学结构,CA 的直观表示帮助我们理解和讨论它们。在“Open Problems & Projects”中,Wolfram 提出了这个问题:是否可以有一个声音表示的 CA 进化,它提供了视觉表示不能提供的内部信息?这是一个有意思的问题。可以慢慢研究一幅图像,并关注感兴趣的地方,但是对声音的感受是随着时间进行的,当它结束后,只能再重新播放它。Wolfram 认为由于这个原因以及其他原因,可能不会有这样的声音表示。

音乐问题
我将关注一个与此有些关系的问题:是否可以用 CA 得到有趣和好听的音乐?一些 CA 的图像表示可以是相当动人和漂亮的。这种美是否也可以用音乐的方式呈现出来?同时,利用 CA 的一般性计算能力作曲会是很好的事,特别是,找出将 CA 进化映射为动听或者至少是有趣的音乐的方式。

用 Java 语言作曲
由 Andrew Sorensen 和 Andrew Brown 开发的 jMusic 是一个用 Java 语言编写音乐程序的开放源代码框架 (请参阅 参考资料)。它建立于 Java Sound APi 之上,并让作曲家可以在音乐水平上进行创作而不用担心低层音频编程细节。在 jMusic 中乐谱的结构是优雅而直观的。它与纸上乐谱的结构相对应:音符构成乐句,乐句构成声部,声部构成乐谱。清单 1 中的例子展示了这种简单性。

清单 1. Harry Dacre 用 jMusic 编写的“Bicycle Built for Two”

int[] pitches = { C5, A4, F4, C4, D4, E4, F4, D4, F4, C4 };
double[] rhythmValues =
{
DOTTED_HALF_NOTE,
DOTTED_HALF_NOTE,
DOTTED_HALF_NOTE,
DOTTED_HALF_NOTE,
QUARTER_NOTE,
QUARTER_NOTE,
QUARTER_NOTE,
HALF_NOTE,
QUARTER_NOTE,
2 * DOTTED_HALF_NOTE };
Note[] notes = new Note[pitches.length];
for (int i = 0; i < notes.length; i++) {
// A note is made up of a pitch and duration
notes[i] = new Note(pitches[i], rhythmValues[i]);
}
// A phrase is made up of notes
Phrase phrase = new Phrase(notes);
Part pianoPart = new Part("Piano", PIANO);
// A part is made up of phrases
pianoPart.add(phrase);
// A score is made up of part(s)
int tempo = 180;
Score daisy = new Score("A Bicycle Built For Two", tempo, pianoPart);
// In key of F: 1 flat
daisy.setKeySignature(-1);
// In 3/4 time
daisy.setNumerator(3);
daisy.setDenominator(4);
// Display score in standard musical notation
View.notate(daisy);
// Write out score to MIDI file
Write.midi(daisy, "C:Daisy.mid");

现在,聆听 得到的 MIDI 文件。

除了 MIDI 功能,jMusic 还有许多其他好功能。例如,可以用常规音符显示自己的乐谱。而且 mod 包可以对乐句进行转换,如置换或者换向。

Automatous Monk
以伟大的爵士钢琴家和作曲家 Thelonious Monk 命名的 Automatous Monk (又叫 Monk),是我用 Java 语言编写的一个开放源代码程序,它通过 CA 进化生成旋律 (请参阅 参考资料)。Monk 使用 jMusic 框架表示得到的音乐,因为 jMusic 乐谱可以保存为 MIDI 文件并播放。我将用 Monk 的代码示例和短的 MIDI 文件示例说明我的观点。

用 Java 语言表示 CA
我将不深入用 Java 语言表示 CA 的细节,不过如果了解如何用细胞的当前状态和其邻居的当前状态计算细胞的下一个状态会有帮助。如您所见,可以用一个二进制数表示一个规则,可以用一个整数表示 CA 细胞在给定步数时的状态。清单 2 中的代码计算细胞的下一个状态。

清单 2. 计算细胞的下一个状态

/**
* Computes the next state of a cell.
* @param nWCellState State of the cell to the left of the current cell in
* preceding generation.
* @param nCellState State of the current cell in preceding generation.
* @param nECellState State of the cell to the right of the current cell in
* preceding generation.
* @return Next state of the cell.
*/
int getNextStateOfCell(int nWCellState, int nCellState, int nECellState) {

// Find the index of the current state in the rule pattern
int index = 4 * nWCellState + 2 * nCellState + nECellState;
// Get the value of the digit in that place
int nextState = (rule >> index) % 2;

return nextState;
}

CA 进化的音乐表示
现在进入困难部分了:如何用 CA 进化构造音乐?有一个事实看来很明显:有了 CA 进化的直观表示,在页中向下走时,时间是增加的。这对于音乐表示也是有意义的。因此,CA 进化的每一行表示一个节拍。

我将在展示 Monk 中得到好的音乐结果的一些映射。嵌套的 CA 一般会得到好听的音乐,可以听到在音乐中反映出来的直观规律性。嵌套的 150 规则是一个好的例子。Wolfram 的 A New Kind of Science 一书简单描绘了一些用音乐表示 CA 的方式 (请参阅 参考资料)。我的映射就基于这些思路。

“键盘”映射
这个“键盘”映射可能是最明显的一个方法。CA 中每一个细胞(或者列)都对应于特定的音高(pitch)。可以将每一个细胞想像为钢琴键的映射。不过,我的实现使计算有些复杂,因为它考虑了所使用的音阶的类型??如半音阶、大音阶或者小音阶??和在这种类型的音阶中音符的音高。清单 3 中的映射计算给定细胞的音高。

清单 3. 计算细胞的音高

/**
* @param cellPos Position of the cell. The position of the center cell is
* 0, while positions to the right are positive and positions
* to the left are negative.
* @param normalize If true, make sure return value is a valid
* MIDI pitch. That is, make sure that it is between 0 and
* 128.
* @return The starting pitch of the cell.
*/
int getStartingPitch(int cellPos, boolean normalize) {
int[] scale = scaleType.getScale();
int interval;
int scaleWidth = scale.length;
// Compute the interval from middle C to this pitch.
if (cellPos >= 0) {
interval =
(cellPos / scaleWidth) * HALF_STEPS_IN_OCTAVE + scale[cellPos % scaleWidth];
} else {
interval = (-cellPos / scaleWidth) * HALF_STEPS_IN_OCTAVE;
if (-cellPos % scaleWidth != 0) {
interval += 12 - scale[scaleWidth - (-cellPos % scaleWidth)];
}
interval *= -1;
}

// Add interval to middle C, C4.
int pitch = C4 + interval;

if (normalize) {
pitch %= 128;
if (pitch < 0) {
pitch += 128;
}
}

return pitch;
}

现在,聆听 对这个映射使用 150 规则时的结果。

可以听到,结果有些不和谐(尽管大体可以听到它的嵌套结构)。“和弦”太密集了。在本文的其余部分,我将展示生成没有多个同时音符的简单旋律的映射。这些类型的映射结合正确的规则,可以生成异常吸引人和迷人的旋律。

“行到二进制数”的映射
“行到二进制数”的映射将每一行考虑为表示一个音高的二进制数。不过有一个微妙之处:如何排列数字?通常,从右到左排列,最右边的数字是最低有效位。不过,一个一维 CA 没有最右(或者最左)细胞。我们把 CA 的“宇宙”看作是在左右两个方向上无限扩展的。因此,在笛卡尔平面使用 x 轴时,考虑一个特定的细胞为原点。在原点右边的细胞为正数,原点左边的细胞为负数。本文中所有示例 CA 都以一个黑色细胞开始,因此自然就以这个细胞为原点。

为了从最低到最高有效位排列二进制数,从原点开始,向前排列。可以有两种方式,取决于是喜欢细胞原点左边还是原点右边的细胞:

喜欢左边:0, -1, 1, -2, 2, -3, 3, ...
喜欢右边:0, 1, -1, 2, -2, 3, -3, ...
不管是哪种情况,都可以将 CA 的一行作为二进制数相加。因为只有 0 和 128 之间的数指定 MIDI 音高,所以可以通过将这个数值取 128 的模将它转换为 MIDI 音高。清单 4 包含 Automatous Monk 中的相应代码。

清单 4. 重新排列一行并计算音高

/**
* Reorders a row according to significance of digits.
* @param rowIndex The generation number of the row
* @param cA The CA containing the row
* @param bias Left- or right-side bias
* @return The reordered row with least-significant digits to right
*/
int[] reorderRow(
int rowIndex,
CellularAutomaton cA,
HorizontalBias bias) {

int[][] cAHistory = cA.getGenerations();
int[] row = cAHistory[rowIndex];
int len = row.length;
int[] reordered = new int[len];
int mid = len / 2;
reordered[len - 1] = row[mid];
for (int i = 0; i < (len - 1) / 2; i++) {
// Note that this favors one side of the CA over the
// other side, but there seems to be no way to get around this.
if (bias.equals(HorizontalBias.LEFT)) {
reordered[len - (2 * i + 1) - 1] = row[mid - (i + 1)];
reordered[len - (2 * i + 2) - 1] = row[mid + i + 1];
} else {
reordered[len - (2 * i + 1) - 1] = row[mid + i + 1];
reordered[len - (2 * i + 2) - 1] = row[mid - (i + 1)];
}
}

return reordered;
}

/**
* Computes a MIDI pitch from a row of 0s and 1s.
* @param rowIndex The generation number of the row
* @param clllrAutmtn The CA containing the row
* @param bias Left- or right-side bias
* @return A valid MIDI pitch
*/
int getPitchFromRow(
int rowIndex,
InfiniteCellularAutomaton clllrAutmtn,
HorizontalBias bias) {

int[] reorderedRow = reorderRow(rowIndex, clllrAutmtn, bias);
int pitch = 0;
for (int i = 0; i < reorderedRow.length; i++) {
pitch = (2 * pitch + reorderedRow[i]) % 128;
}

return pitch;
}

现在,聆听 对这个映射使用 150 规则所产生的旋律。注意使用左或者右方式得到同样的结果,因为 150 规则是对称的。

“累积行到二进制数”的映射
“累积行到二进制数”的映射与上一个映射一样,但是累积行值??每次计算总值。清单 5 是这种映射的代码。

清单 5. 计算连续各行的音高总值

/**
* Converts the successive rows of a CA to a musical phrase.
* @param cA A cellular automaton
* @param bias Favor left- or right-side in generating pitches
* @return A musical phrase corresponding to cA
*/
public Phrase convertCAHistoryToPhrase(
CellularAutomaton cA,
HorizontalBias bias) {

Phrase phr = new Phrase();
int cumulativePitch = 0;
for (int i = 0; i < cA.getGenerationCnt(); i++) {
int pitch = getPitchFromRow(i, cA, bias);

// Need to take mod 128 to keep it a valid MIDI pitch.
cumulativePitch = (cumulativePitch + pitch) % 128;

Note n = new Note(cumulativePitch, CAConstants.DEFAULT_NOTE);
phr.add(n);
}

return phr;
}

现在,听听 它是什么样的声音。

这个结果比前一个例子旋律更动听,它听起来有一些像节奏片段。

组合映射
组合映射可以得到好的结果。例如,可以 将 150 规则与节奏片段组合在一起。还可以 将使用 60 规则的二进制与累积二进制映射组合起来。注意左右方式的映射是不同的,因为 60 规则不是对称的。这会得到四种声音和更丰富的音响。

必须承认我认为 60 规则是相当吸引人的!我曾花了大量时间(肯定比大多数人要多)聆听 CA,我经常发现 60 规则更适合于我。 我认为它是 CA 世界中的 Hanson 或者 Jackson 5。

如何将 MIDI 文件转换为手机铃声
如果能用 CA 生成手机铃声将是很好的事情。(Wolfram 提到过他希望在自己的手机上有这种铃声。)我不是这方面的专家,但是看来手机铃声机制在不同品牌的手机中是不一样的。不过,至少有几个开放源代码软件程序??Clint Levijoki 的 midi2rtx 和 Andreas Leitner 的 Midi2C25??可以将 MIDI 文件转换为手机铃声(请参阅 参考资料)。我没有用过这些程序,因为我没有手机??但是我有意找一个手机试试。


保持简单
如前所述,我发现最好专注于生成单音旋律的映射(虽然可能叠加这些旋律,正如我使用二进制和累积二进制映射一样),并本质上忽略和声和节奏。这并不像它看上去那样是一个很大的限制。很多巴洛克式音乐,如 J.S. Bachs 的音乐就是这种类型的。它甚至有一个单词: 复音(polyphony)。(当然,我作了相当的简化:在复音中,确实有不同声音的和声,节奏也没有完全忽略。)这些映射的复音组合是用 CA 创作音乐的很好的第一步。

我还发现简单映射会得到最动听的结果。不过,这并不意外,因为即使简单的直观映射??将 1 映射为黑方块,0 映射为白方块??也可以生成漂亮和复杂的样式。而且,考虑一些 CA,如 110 规则可以进行一般性计算这一事实。假设现在作曲是纯粹理性的行为??可以编写算法作曲。那么对于一般性 CA, 如 110 规则,可以自己生成音乐,而不用我们在映射内部“编写”任何音乐智能或者知识。当然,我一直只使用特别简单的开始状态,而 110 规则有可能要求更复杂的程序和在初始状态中编入更复杂的输入数据以生成真正动听的音乐。要点是从 CA 状态到音符的 映射 应当是相当“透明”的:“CA 应当完成所有作曲工作。”

让映射复杂化的另一危险之处在于容易在映射中编写自己的音乐偏好(东方或者西方,有音调或者无音调)。编写一个计算机程序,让它可以写出肖邦或者巴赫风格的作品,并与肖邦或者巴赫作品几乎一样好,这可能是一个很困难的问题,但这是一个令人钦佩的成就:无论如何,有另一个“新的”肖邦或者巴赫的作品总是好事。但是为什么仅限于此呢?我认为算法音乐作曲只有不仅可以产生美妙的音乐,而且还能生成与我们以前没有听到过的完全不同类型的美妙音乐,才能算做真正成功。肖邦或者巴赫不仅因为写出伟大的音乐而伟大:他们伟大是因为他们带来了全新的音乐思路。我认为最好的结果将来自使用简单的映射并让 CA 生成所有音乐观念。

(图)Bill GosperBill Gosper

Gnarl
Rudy Rucker 定义了一个他称为 Gnarl 的概念:具有某种杂乱水平的东西,它正好处在有序与无序之间的边界。

当我第一次开始聆听 Monk 生成的 CA 音乐时,一些最好听的 CA 对我来说就像是 Gnarl 的例子。后来,我在 Rucker 的“Things Computer Science Tells Us About Philosophy”中了解到他认为第 4 级 CA 是 Gnarl 的例子。

不规则的 CA 听起来是什么样的? 聆听 225 规则。

当我聆听 225 规则时,我感觉几乎可以捕捉到它的结构,但是又不是很清晰。这样可以长时间地聆听它而不会乏味。另一方面,嵌套模式的 60 规则如果偶尔听一听是不错的,但是它不能让我长时间保持兴趣。60 规则结构太容易捕捉了,它可能是不错的、经嚼的、能嚼出声音(crunchy mind)的糖果,但是它不是 Gnarl 的例子。即使 225 规则从我给出的简单初始状态得到一个规则的、嵌套的模式??因而不是第 4 类??但是它对我来说听起来仍然是相当不规则的。(需要完整的另一篇文章来说明为什么 CA 听起来比看起来通常更不规则 。)

那么真正的第 4 类 CA 听起来是什么样的呢?110 规则是第 4 类的: 听听 它吧。

它听起来绝对像我们进入了 Gnarl 的老家。像许多好的音乐一样,需要听几遍才能欣赏它。

计算机作曲的应用
一些有意思的作品是主要由计算机作曲的。特别是,John Elliot 的 Transmusic 项目(请参阅 参考资料)完成了极其出色的音乐。Transmusic 使用二维 CA 进行作曲。

David Cope 的音乐智能试验(Experiments in Musical Intelligence,EMI)项目写出了一些由计算机作曲的、最令人印象深刻的作品。(请参阅 参考资料)。EMI 能够以任何作曲家的风格编写好的作品。不过,EMI 不仅仅是聪明的模仿作品生成器。它还可以以新的方式扩展音乐结构。


其他算法作曲项目
在算法作曲方面的研究比您所想像的要多得多。基本上有两种用计算机进行音乐作曲的方式:自上而下和自下而上。使用计算机程序作为辅助手段的作曲家大多数使用自上而下的方式??通过将音乐构造块加入到较大的结构中。Automatous Monk 采用了自下而上的方式:它在音符级别上创建音乐。

CAMUS
CAMUS 由 Eduardo Reck Miranda 编写,是另一种使用 CA 生成音乐的自下而上的方式(请参阅 参考资料)。它使用 Life 和 Demon Cyclic Space 生成音乐。与我展示的一维 CA 不同,Life 和 Demon Cyclic Space 都是二维 CA,就是说,细胞是排列在二维网格中的。Life 特别有意思(编写和观看都很有趣)。CAMUS 使用 Life 生成音符组,同时用 Demon Cyclic Space 生成各个音符的音色(或者音质)。

Music Sketcher
Music Sketcher 是一个 IBM alphaWorks 项目(请参阅 参考资料)。与 Monk 和 CAMUS 不同,Music Sketcher 使用自上而下的方式,将用户将段落或者重复段放入较大的音乐结构中。Music Sketcher 中特别有意思的是它能够用于创建作品的和弦数,同时程序完成必要的转换以保证构造块符合指定的和弦数。(这样,它成为苹果公司的新 GarageBand 应用程序的先驱。) 这是一个有趣的程序,我建议您试试它。

结束语
有许多使用 CA 进行算法作曲的有趣方式有待探索。我提供的例子只能说是简单的起始状态。如果利用更复杂起始状态的 CA 会是什么样的音乐呢?同时,大多数西方音乐作品的旋律要符合和弦数。设计一种映射技术,使 CA 生成符合特定用户和弦变化的旋律将会很有意思(换句话说,一种CA Charlie Parker),尽管使 CA 符合音乐偏见可能会限制它们。

当前版本 Monk 的一个限制是它只使用常规西方音高:128 MIDI 音调。在将 CA 行解释为二进制数的 128 模数时,实际上只用到了一行中的 7 个数或者单元。七个单元是完整 CA 的一个很窄部分,很多信息丢失了。我们可以通过使用微音程(microtone)而不是只使用西方音乐中的半音(semitone)来保留这些信息。这会产生音色更丰富的音乐还是只产生不和谐呢?我准备扩展 Monk 以检验其中一些想法。

Automatous Monk 和 jMusic 都可以在 SourceForge.net 上免费获得,我鼓励读者进行自己的试验。您也可从 Wolfram 的论文“Open Problems & Projects”中获得灵感。细胞自动机的研究可以有多种角度,并涉及不同程度的技术复杂性,从高中水平到研究生水平。用 Rudy Rucker 的话说,就是“寻找 Gnarl!”

参考文献编辑本段回目录

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
1

标签: Bill Gosper 比尔·高斯珀 Ralph William Gosper 比尔·高士泊

收藏到: Favorites  

同义词: Ralph William Gosper,Ralph William Gosper. Jr.,比尔·高斯珀,比尔·高士泊

关于本词条的评论 (共0条)发表评论>>

对词条发表评论

评论长度最大为200个字符。