因此, 巴贝奇的机器, 如果他能建造它, 本来可以 执行的现代计算机 的任何计算 虽然它需要很大的空间 和大量的蒸汽。 还有什么能够 进行通用计算? 那么,在复杂的系统中 我们有点享受 和喜欢 这些小例子, 通用的玩具, 元胞自动机。 因此,元胞自动机通常是 一维或二维网格, 并且在每个网格位置 我们都有一组有限的状态, 我们最喜欢的例子之一 也是一个流行的屏幕保护程序 是生命游戏 由约翰康威发明。 所以在生命游戏中, 每个网格方块都可以是存活的或死亡的状态。 这里有生命的部分用黑色表示, 无生命的部分用白色表示。 而且,就像在所有元胞自动机中一样, 有一个简单的, 每个网格点的局部规则, 在每一步,查看 自己状态和邻居的状态, 然后计算它的新状态 并且所有内容都会并行更新。 在这个特定规则中, 邻居是网格中的 8 个位置, 您可以随着 国际象棋王的移动而移动到该位置, 规则如下: 如果你是存活着, 并且你的 8 个邻居中有 2 或 3 个也是存活状态, 则你仍是存活状态。 如果邻居少于 2 个是存活的, 那么你死于孤独。 如果邻居有 4 个或更多个, 那么会死于人口拥挤。 故事是这样的。 这不是一个真正的生物模型, 但。 好的,还有 如果你是死的状态,那么你的方格是空的 并且当你正好有 3 个邻居 是存活着的, 之后 你将重新存活。 这就是整个规则。 康威玩弄这些数字, 这些规则, 基本上。为了活着或死去 直到它做了一些 有趣的事情, 所以在生命游戏中发生的 一件事就是我们称之 为“滑翔机”的小东西。 就是这个会摇摆不定的小动物 它穿过对角线, 它会保持移动 直到它撞到东西。 然后,还有一种东西 叫做“滑翔机枪” 它来回移动, 并产生一连串的滑翔机。 此外,还可以 精心设计碰撞 滑翔机之间, 构建小对象, 甚至进行逻辑运算。 我们可以使用滑翔机, 滑翔机流, 几乎像一根电线, 携带一点信息。 好吧,如果你结合 所有这些元素, 你非常聪明 有大量的空闲时间, 你可以从生命的游戏 中构建一个图灵机。 所以这里我们 有一个非常复杂的配置, 其中像素 几乎太小而无法看到。 我放大它 那里的滑翔机枪之一, 穿过对角线, 我们有图灵机的磁带, 这里有 图灵机的头部。 因此生命的游戏, 具有足够大的初始配置, 就可以模拟图灵机。 有一些有趣的问题 在这里可以吗 从配置开始 这是无限的,但周期性的。 这为您提供了 您可能需要的所有磁带, 或者,也许有一个聪明的方法 让滑翔机枪制作磁带 随着时间的推移, 随着时间的推移, 从有限区域之外的空白初始配置开始。 但无论如何 生命游戏可以计算。 它可以计算因为我刚刚向您展示了 如何在其中构建计算机。 记得很久以前 当我们谈论 某些问题的 NP 完备性 像平铺问题, 将拼图拼贴成 一定的形状, 或哈密顿路径问题, 我强调 这些问题很难, 因为你可以用它们构建计算机。 我们在这里建造 通用计算机, 在元胞自动机中, 并给予足够的空间和时间, 我们可以进行 任何计算, 而不仅仅是一个, 多项式时间或指数时间, 我们之前谈论的方式。 生命游戏是一个二维 元胞自动机, 这很容易 设置磁带, 和一个在磁带上 来回移动的磁头。 那么一维 元胞自动机 ? 嗯,这里有一个特别的 一维元胞自动机。 同样,我们只有 2 个状态, 0 和 1,或黑白, 在每个位置, 再重复。 我们看看我们最近的邻居, 以及我们自己的状态 这是我向你展示 的更新规则 8 个可能的邻居的 新状态是什么, 你自己的状态和 你邻居的状态的组合。 其实这是元胞自动机 规则 110 因为,如果这些黑色方块是 1 在规则中 白色方块是 0, 然后在二进制中, 这拼出 110。 Stephen Wolfram (斯蒂芬沃尔夫勒姆) 发明了该编号方案 作为探索给定大小的 元胞自动机规则 的一种方式。 因此,这里是规则 110 的 典型运行的时空图。 在顶部我们有 顶行是一些初始设置, 网格中的所有单元格, 时间向下。 当你看到这个时, 是各种各样的滑翔机 立刻跳出来的。 有各种不同的粒子, 类似于 生命游戏中的滑翔机, 但种类繁多, 当我们向下移动时, 可以向左或向右移动 在不同的速度下, 你可以看到 当他们相撞时, 复杂的事情发生。 所以不禁让人联想到 我们可以以此为基础 构建一个图灵机。 这是斯蒂芬沃尔夫勒姆推测的 然后 Matthew Cook (马修库克) 证明 他们两个发表了这篇论文 并表明,规则 110 能够进行通用计算 因此, 它的长期行为, 最终会发生什么 从某个初始状态, 是不确定的。 还有 Turlough Neary 和 Damien Woods 改进了他们的模拟, 并表明,事实上, 它可以模拟图灵机 只有多项式开销, 换句话说, 可以模拟 图灵机 t 步 有一段时间 这只是多项式NT。 这意味着预测它, 即使是有限的时间, 也需要你做大量的工作, 大约与 运行图灵机所需的 工作量一样多。