元胞自动机

1827846396

标准元胞自动机是一个由「元胞、元胞状态、邻域和状态更新规则」构成的四元组，用数学符号可以表示为A=(L,d,S,N,f)
& z0 G& m) g4 D: nA代表一个元胞自动机系统
/ ?1 Q- p/ {0 ]( [# }. \! tL表示元胞空间
9 e' Q5 T# M: d" ~+ `d表示元胞自动机内元胞空间的维数，是一正整数
6 W' _* t7 X$ gS是元胞有限的、离散的状态集合
% L' G: f4 x5 l8 i" b8 u4 \N表示某个邻域内所有元胞的集合
. }) P4 e2 T( }& Y) D" A) b& A7 @f表示局部映射或局部规则。
1 `5 ?- j8 k) @. C2 P具体描述：
- ?5 R, ?' _; g) ~. m7 H; E

) `, n& R) X, _' \元胞空间
元胞是构成元胞自动机的最基本单元，而元胞空间是元胞所分布的空间网点集合。
理论上，元胞空间是在各维向上无限延展的，但实际中无法在计算机上实现。因此，需要定义不同的边界条件。
, n2 n5 @/ _) J. @; h9 ^元胞空间的边界条件主要有三种类型：周期型、反射型和定值型。
! z: M, I  H$ t9 S+ F元胞状态
/ {: j+ o0 J7 y1 i: ]( n通常在某一个时刻一个元胞只能有一种元胞状态，而且该状态取自一个有限集合，如{0,1}，{生,死}或{0,a1,a2,an}。
在社会科学领域中，元胞状态可以用来代表个体所持的态度、个体特征或行为等。
邻域
! u" l# [' p" i7 e- S  }在空间位置上与元胞相邻的细胞称为它的邻元，由所有邻元组成的区域称为它的邻域。
0 h* e( C% E) {, A) K在一维元胞自动机中，通常以半径r来确定邻域，距离某个元胞r内的所有元胞均被认为是该元胞的邻域。
一维元胞自动机的邻域：
! {) ]- E9 z% A5 e
# ?, ]% D) J8 b9 U$ Y. R  @& p5 y
在二维元胞自动机中，通常有以下几种类型的邻域：
( M( d% R2 r7 K3 j/ L- _% {冯·诺依曼型(vonNeumanNeighborhoods)
+ R  f) z2 |' I& \4 z5 q# }% F& p摩尔型(MooreNeighborhoods)
$ R; r* [+ H) n- W  }- ~+ E' {马哥勒斯型(MargolusNeighborhoods)
& G4 Q; Y& ~! ?1 Q3 m% R! }它是每次将一个2×2的元胞块做统一处理，而上述前两类邻域中，每个元胞是分别处理的
2 O  e5 x/ c, f) B

* g( e0 V5 K) T! X, L' ]' s+ y同样，也可以定义二维以上的高维元胞自动机的邻域
: ]: l* S0 d' j! q4 ?) l5 P. v状态更新规则
1 Y* r. @5 k+ ~8 _- e3 v3 s是指根据元胞当前状态及其邻域中元胞的状态决定下一时刻该元胞状态的状态转移函数。
状态更新规则可以写为，为t时刻的邻域状态组合，称为元胞自动机的局部映射或局部规则。
; t. s7 k, g/ h, y7 c( Q5 A9 Q; A/ z5 @

6 ^' i% R* {& B