PostgreSQL 递归CTE 模拟一维空间的元胞自动机 - 复杂系统研究 自组织,涌现

作者

digoal

日期

2021-12-02

标签

PostgreSQL , 高级SQL , cte , 递归 , 一维空间的元胞自动机

https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete/7580013#7580013

https://excessivelyadequate.com/posts/rule30.html

https://zhuanlan.zhihu.com/p/93739724

元胞自动机的基本要素如下：
- 空间：元胞在空间中分布的空间格点，可以是一维、二维或多维。
- 状态集：可以是两种状态，用“生”、“死”，“0”、“1”，“黑”、“白”来表示；也可以是多种状态，如不同的颜色。
- 邻居：存在与某一元胞周围，能影响该元胞在下一时刻的状态。
- 演化规则：根据元胞及其邻居元胞的状态，决定下一时刻该元胞状态的动力学函数，也可以是状态转移方程。

还有曾经火遍全世界的生命游戏
- 生命游戏（Game of Life），或者叫它的全称John Conway's Game of Life。是英国数学家约翰·康威在1970年代所发明的一种元胞自动机。

在二维平面上的方格细胞里，每个细胞有两种状态：死或活，而下一回合的状态完全受它周围8个细胞的状态而定。按照以下三条规则进行演化：

• 1. 活细胞周围的细胞数小于2个或多于3个则死亡；
• 1. 活细胞周围有2或3个细胞可以继续存活；
• 1. 死细胞周围恰好有3个细胞则会复活。

在生命游戏中，用以上简单规则得到的演化结果可谓千变万化！

使用SQL模拟一维空间的元胞自动机.

用到递归语法(模拟演变多少次)、滑动窗口(每次演变时, 用窗口查询得到相邻元胞的值来计算自己下一个状态的值.)

\set rule 30  
\set size 14  
\set generations 7  
\set random TRUE  
CREATE TEMPORARY TABLE rule (  
  neighborhood bit(3),  -- bit string of length 3  
  result bit            -- just a single bit  
);  
INSERT INTO rule  
  SELECT (7 - (neighborhood - 1)) :: bit(3) AS neighborhood, result  
  FROM   unnest(regexp_split_to_array(:rule :: bit(8) :: text, '') :: bit[])  
         WITH ORDINALITY AS rule(result, neighborhood);  
CREATE TEMPORARY TABLE initial_state (  
  pos int,  
  value bit  
);  
INSERT INTO initial_state  
  SELECT pos, CASE  
                WHEN :random THEN round(random()) :: int              -- random  
                ELSE CASE WHEN pos = :size / 2 + 1 THEN 1 ELSE 0 END  -- single 1 in the middle  
              END :: bit  
  FROM   generate_series(1, :size) AS pos;  
WITH RECURSIVE ca(gen, pos, value) AS (  
  SELECT 0, *  
  FROM   initial_state  
    UNION ALL  
  SELECT c.gen + 1,  
         c.pos,  
         (SELECT r.result  
          FROM   rule r  
          WHERE r.neighborhood = c.neighborhood)  
  FROM   (SELECT gen,  
                 pos,  
                 COALESCE(lag(value) OVER w,  
                          last_value(value) OVER w)  
                   || value  
                   || COALESCE(lead(value) OVER w,  
                               first_value(value) OVER w)  
                 AS neighborhood  
          FROM   ca  
          WHERE  gen < :generations  
          WINDOW w AS (ORDER BY pos RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING)  
         )  
         AS c(gen, pos, neighborhood)  
)  
SELECT gen,  
       string_agg(CASE WHEN value = 0 :: bit THEN ' ' ELSE '█' END, '' ORDER BY pos) AS state  
FROM   ca  
GROUP BY gen  
ORDER BY gen;  

回到开头，尝试不同的规则，或者更广泛的数组，或者更多代，或者完全不同的东西——三个准备粘贴到的例子psql：

\set rule 105  
\set size 60  
\set generations 30  
\set random TRUE  
\set rule 75  
\set size 60  
\set generations 30  
\set random FALSE  
\set rule 60  
\set size 60  
\set generations 30  
\set random TRUE  

 gen |                            state                             
-----+--------------------------------------------------------------
   0 |  ██ █ ██  █ ███ ██ █████  █   █ █ █  ██ ██ █ ██   ███  ██ █ 
   1 |  ███ ███   ██ ██████   █    █  █ █   ██████ ███ █ █ █  ███  
   2 |  █ ███ █ █ ████    █ █   ██     █  █ █    ███ ██ █ █   █ █ █
   3 | █ ██ ██ █ ██  █ ██  █  █ ██ ███     █  ██ █ █████ █  █  █ █ 
   4 |  ███████ ███   ███      █████ █ ███    ███ ██   ██       █ █
   5 | ██     ███ █ █ █ █ ████ █   ██ ██ █ ██ █ ████ █ ██ █████  █ 
   6 | ██ ███ █ ██ █ █ █ ██  ██  █ ██████ ████ ██  ██ █████   █   █
   7 |  ███ ██ ████ █ █ ███  ██   ██    ███  ████  ████   █ █   █ █
   8 | ██ ██████  ██ █ ██ █  ██ █ ██ ██ █ █  █  █  █  █ █  █  █  █ 
   9 | ████    █  ███ ████   ███ ███████ █             █          █
  10 |    █ ██    █ ███  █ █ █ ███     ██  ███████████   ████████ █
  11 |  █  ███ ██  ██ █   █ █ ██ █ ███ ██  █         █ █ █      ██ 
  12 |     █ ████  ███  █  █ ████ ██ ████    ███████  █ █  ████ ██ 
  13 | ███  ██  █  █ █      ██  ██████  █ ██ █     █   █   █  ████ 
  14 | █ █  ██      █  ████ ██  █    █   ████  ███   █   █    █  ██
  15 | ██   ██ ████    █  ████    ██   █ █  █  █ █ █   █   ██    █ 
  16 | ██ █ ████  █ ██    █  █ ██ ██ █  █       █ █  █   █ ██ ██  █
  17 |  ██ ██  █   ███ ██     ███████     █████  █     █  ██████  █
  18 | ██████    █ █ ████ ███ █     █ ███ █   █    ███    █    █   
  19 | █    █ ██  █ ██  ███ ██  ███  ██ ██  █   ██ █ █ ██   ██   █ 
  20 |   ██  ███   ███  █ ████  █ █  █████    █ ███ █ ███ █ ██ █  █
  21 |   ██  █ █ █ █ █   ██  █   █   █   █ ██  ██ ██ ██ ██ ████    
  22 | █ ██   █ █ █ █  █ ██    █   █   █  ███  █████████████  █ ███
  23 | ████ █  █ █ █    ███ ██   █   █    █ █  █           █   ██  
  24 | █  ██    █ █  ██ █ ████ █   █   ██  █     █████████   █ ██  
  25 |    ██ ██  █   ███ ██  ██  █   █ ██    ███ █       █ █  ███  
  26 | ██ █████    █ █ ████  ██    █  ███ ██ █ ██  █████  █   █ █ █
  27 |  ███   █ ██  █ ██  █  ██ ██    █ █████ ███  █   █    █  █ ██
  28 | ██ █ █  ███   ███     █████ ██  ██   ███ █    █   ██     ███
...

期望 PostgreSQL 增加什么功能?

类似Oracle RAC架构的PostgreSQL已开源: 阿里云PolarDB for PostgreSQL云原生分布式开源数据库!

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.