用 Java 语言进行算法作曲

　　利用计算机、数学和 Java Sound API，加入一些 Java 代码，就可以制作出一些独特迷人的音乐来。IBM 专职软件工程师 Paul Reiners 展示了如何用 Java 语言实现一些基本的算法作曲。他给出了代码示例和由 Automatous Monk 程序所生成的 MIDI 文件，这个程序使用了开放源代码 jMusic 框架，以一种名为细胞自动机的数学结构为基础进行作曲。
很多计算机程序员都是很出色的音乐家，很少有组织不起像样的室内乐队的软件公司。不过，许多程序员/音乐家可能没有意识到这样一个能让他们的职业和业余爱好统一起来的有意思的领域：算法作曲。算法作曲将严格的、定义良好的算法应用到作曲过程中。细胞自动机（Cellular automata，CA）??这是一种随时间而进化的数学结构??为算法作曲展现了一条迷人的大道。计算机非凡适合计算细胞自动机（CA）的进化并以图形方式显示它们。还可以用声音表现进化，包括音乐。但是寻求将 CA 进化映射为动听和有意思的音乐不是一个简单的问题。本文展示了用 Java 语言进行基于 CA 的作曲的一些技术，并探讨了得到非凡出色结构的某些映射。

细胞自动机概述
CA 包括：

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

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

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 的未来状态。

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

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

一个未决问题
当然，CA 是纯数学结构，CA 的直观表示帮助我们理解和讨论它们。