实施元胞自动机？ “规则110”

Question

我想知道如何使用 55 条线和 14 个单元格的规则 110。然后我必须将其显示在 LED 矩阵显示屏上。

不管怎样，我的问题是，我怎样才能实现这样的自动机？

我真的不知道从哪里开始，有人可以告诉我如何解决这个问题吗？

我必须遵循特定的方法吗？

谢谢

--使用的程序是-> C

编辑

char array[54][14];
for(v=0;v<55;v++){ 
  for(b=0;b<15;b++){ 
    if(org[v][b-1]==0 && org[v][b]==0 && org[v][b+1] == 0)                                                         
      {
        array[v][b]=0;
      }
      array[v][b]=org[v][b];
 }

}

这有意义吗？ org 代表原始

Answer 1

好的，每个元胞自动机都是围绕“递归关系”构建的，因此时间 t 的状态取决于时间 t-1 的状态。因此，每个元胞自动机都有一个基本结构，其中有一些代表状态的数据结构，例如数组。因此，抽象地讲，您的程序将类似于

State t
/* initialize t */
while(/* end condition isn't satisfied */){
    t = rule(t);
    /* display state somehow */
}

其中 rule(t) 是计算下一个状态的函数。

下一步是提出一个数据结构来表示状态。这实际上很简单——基本一维元胞自动机的状态只是一个由 1 和 0 组成的向量。

所以你需要一个由 14 个小数字组成的数组。空间不会成为问题，因此使用 int：

 int t[14] ; /* state vector*/

结束条件很简单 - 您应该执行 55 行，因此您需要

 int count = 0;
 while(count++ < 55)

注意，它为您提供第 0-54 行，即 55 行。 C 是从 0 开始，后递增，并测试小于。您用 C 编写的 10 个循环中可能有 9 个都会具有这种模式。

现在，最后的问题是如何实施您的规则。不幸的是，由于这是 C，所以你不能像我的描述那样简单地做到这一点；该规则必须更新向量。这看起来很像

void rule(int t[]){
     /* compute the update here */
}

现在，我不会确切地告诉您如何计算更新，因为那样您就不会获得任何乐趣。但您可能会发现关于规则 110 的维基百科文章很有趣。

当您阅读它时，请思考一下：这个简单的规则是“图灵完备的”——这意味着它能够（也许需要很多麻烦）表示任何计算。这个简单的规则本身就是理论意义上的“计算机”。

更新

好的，更多关于规则的内容。查看 Wiki 文章中的规则表。它显示的是您获取数组的三个单元格并确定三个单元格中中间一个的下一个值。

因此，在您的规则中，您需要传入的数组 t 和下一时刻的数组，将其称为 t1。

  void rule(int t[]){ // there's the original
       int t1[14];    // there's the new array
       int ix ;       // an index for the loop that's coming up

您想要遍历数组的每个单元格

       for(ix=0; ix < 14; ix++){

并检查该单元格以及左侧和右侧的单元格

            if(t[ix-1] == 0 && t[ix] == 0 && t[ix+1] == 0)
               t1[ix] = 0;
            else if(t[ix-1] == 0 && t[ix] == 0 && t[ix+1] == 1)
               t1[ix] = 1;

等等。您需要考虑边缘处发生的情况，即当 ix == 0 或 ix == 13 时。

最后，您需要另一个 for 循环将 t1 复制回 t。