论文主体(jwf)...pdf

John von Neumann 1951 8 Neumann 0 1 22 5 4294967296 18 56 I 24 CA universality Neumann II Abstract Two Dimensional Symbolic Dynamics and Cellular Automata Abstract KeyWords cellularautomata CA two dimensionalsymbolic dynam ics universality topologically conjugate Neumann neighborhood global map III I Abstract III V 1 1 1 1 2 2 3 1 3 2 5 6 9 9 10 01 13 01 16 18 18 19 22 26 26 1 H56 27 2 H18 31 33 IV 35 39 44 44 44 46 52 53 V VI 1 1898 Hadamard 1 1921 Morse 2 1927 1935 Birkhoff 3 1938 Morse Hedlund 4 Levinson VanderPol Smale 5 1960 1970 Smale Bowen Rulle Sinai Metroplic M Stein P Stein 6 7 Berger Kastelyn R M Robinson 8 10 Milnor Thurston 1977 11 Guckenheimer Collet Eckmann 1980 1981 J Ford 12 Silnikov Lorenz 13 14 17 1 18 21 2 tiling systems statistical mechanics 22 15 23 25 undecidable 21 1990 26 29 10 ent X lim n log Bn X n2 B X X n 30 ice model 2005 27 systematic scheme n An Bn An Bn 18 20 31 33 A 11 10 34 2 35 26 projectional entropy 36 26 37 38 n An Bn n 2 primitive 39 checkable scheme An Bn n 2 primitive Ak Bk k 3 primitive 26 40 1 Cellular Automata CA Cantor John von Neumann 1951 Stanislaw Ulam 1948 Neumann 41 Stanislaw Ulam 29 Neumann A W Burks 42 1970 Conway 43 game of life 2 8 Hedlund 44 1969 Hedlund 1980 Stephen Wolfram 3 2 1 Elementary Cellular Automata ECA 45 VLSI 46 53 Stephen Wolfram 54 55 I 1 1 II 1 2 III 1 3 IV 1 4 1 1 ECA 136 1 2 ECA 56 1 3 ECA 90 1 4 ECA 110 4 Wolfram Christopher Langton Artifi cial Life 56 Norman Packard Christopher Langton the edge of chaos 57 Santa Fee 46 50 53 58 60 2002 Wolfram A New Kind of Science 61 L O Chua Wolfram 62 67 ordering turbulence chaos fractality 2 5 cell lattice neighborhood rule 68 0 1 Neumann Moore 1 5 61 Neumann Moore 1 5 Neumann 1 0 Neumann 5 32 Cij xij Neumann x i 1 j xi j 1 xi j 1 x i 1 j yij yij N x i 1 j xi j 1 xij xi j 1 x i 1 j xij 0 1 i j Z2 1 1 N N P31 i 0 i 2i i S i 0 1 31 22 5 4294967296 CNN 7 6 CNN CNN Neumann 0 1 22 5 4294967296 Neumann T T UD TLR T D 1 1 x i 1 jxi j 1 xijxi j 1 x i 1 jyijx i 1 jxi j 1 xijxi j 1 x i 1 jyij 00000 010000 16 00001 110001 17 00010 210010 18 00011 310011 19 00100 410100 20 00101 510101 21 00110 610110 22 00111 710111 23 01000 811000 24 01001 911001 25 01010 1011010 26 01011 1111011 27 01100 1211100 28 01101 1311101 29 01110 1411110 30 01111 1511111 31 18 56 69 110 24 blinker glider Conway 7 8 4 18 56 2 2 24 8 k k 2 0 1 k 1 S 0 1 k 1 Z S SZ x xi xi S i Z Z x xi SZ 0 SZ x y max i Z n 1 max i 1 xi 6 yi o 2 1 SZ Hausdorff SZ k a a0 ap 1 S p 1 p x SZ I i j x i j xi xj x i j xi xj 1 m Z x m m p 1 a a x x a a x a x a x SZ x a x a a m Z m a0 ap 1 x SZ x m m p 1 a SZ SZ SZ SZ SZ SZ xi 7 xi 1 2 2 SZ S SZ 15 1 2 SZ 3 4 logk k S 9 5 Li Yorke Devaney A S N A N A A x SZ x i i n 1 A A Z A SZ A A N A 2 1 15 2 2 2 1 15 aij 1 i j 0 i j k k 0 1 A aij i j S 2 2 A A A A 1 2 2 A 2 2 15 1 A A 2 A N n N An 0 S 0 1 k 1 k Z2 i j i j Z S SZ 2 x xij xij S i j Z2 x xij SZ 2 0 0 SZ 2 SZ 2 d x y max i j Z2 n 1 max i j 1 xij 6 yij o 2 3 10 aij S i N j N N 0 m n Z2 a N aij i N j N x SZ 2 x i m j n aij i N j N S aij i N j N SZ 2 SZ 2 SZ 2 7 SZ 2 d Hausdorff SZ 2 k SZ 2 kl SZ 2 SZ 2 xij 7 x i k j l 2 4 k l Z2 k 1 l 1 2 4 32 9 00 01 0 1 10 10 11 1 1 11 1 1 00 00 kl k0 0l k l 6 0 0 11 10 01 11 10 10 1 1 10 0 1 1 1 10 0 1 k0 0l 8 kl SZ 2 01 2 2 01 SZ 2 SZ 2 xij 7 xi j 1 2 5 01 x ij xi j 1 i j Z2 2 1 7 x y SZ 2 N d x y 0 N 1 N 1 1 2N 1 2 1 d x y 1 2N 1 max i j 2N xij yij i j Z2 max i j j N i j Z2 max i j 2N 2 1 max i j j N x i j j y i j j d h x h y max i j j Z2 n 1 max i j j 1 x i j j 6 y i j j o 1 N 1 0 N Z 1 N 1 1 N 1 x xij y yij SZ 2 d x y N 1 j 1 x0j6 y0j 1 N 1 2 1 SZ h 01 h h u uij SZ 2 h 01 uij h ui j 1 u0 j 1 i j Z2 h uij u0j u0 j 1 i j Z2 16 01 01 8 SZ 2 01 SZ 2 6 2 7 2 11 17 S 0 1 SZ 2 Neumann S 0 1 2 22 5 4294967296 1 1 N N P31 i 0 i 2 i i S i 0 1 31 0 31 SZ 2 N TN N 4210689285 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 xij S i j Z2 N xij x i 1 j x i 1 j xi j 1 xi j 1 x i 1 j xij x i 1 j N0 4210689285 N0 TN0 TN0 SZ 2 SZ 2 x xij 7 x i 1 j xij x i 1 j TN0 x ij x i 1 j xij x i 1 j i j Z2 TN0 x ij TN0 x i j 2 3 TN0 SZ 2 T N0 SZ 2 T N 3 1 64 3 1 18 3 1 fi TN 3 1 64 f00f631 f1xijf62xij f2x i 1 jf61x i 1 j f3x i 1 jf60 x i 1 j f4xi j 1 f59xi j 1 f5xi j 1 f58xi j 1 f6x i 1 j xijf57x i 1 j xij f7xi j 1 xijf56xi j 1 xij f8xij x i 1 jf55xij x i 1 j f9xij xi j 1 f54xij xi j 1 f10 x i 1 j xi j 1 f53x i 1 j xi j 1 f11x i 1 j x i 1 jf52x i 1 j x i 1 j f12x i 1 j xi j 1 f51x i 1 j xi j 1 f13xi j 1 x i 1 jf50 xi j 1 x i 1 j f14xi j 1 xi j 1 f49xi j 1 xi j 1 f15x i 1 j xi j 1 f48x i 1 j xi j 1 f16x i 1 j xi j 1 xijf47x i 1 j xi j 1 xij f17x i 1 j xi j 1 x i 1 jf46x i 1 j xi j 1 x i 1 j f18x i 1 j xi j 1 xi j 1 f45x i 1 j xi j 1 xi j 1 f19xi j 1 xij x i 1 jf44xi j 1 xij x i 1 j f20 xi j 1 xij xi j 1 f43xi j 1 xij xi j 1 f21xij x i 1 j xi j 1 f42xij x i 1 j xi j 1 f22xi j 1 x i 1 j xi j 1 f41xi j 1 x i 1 j xi j 1 f23x i 1 j x i 1 j xi j 1 f40 x i 1 j x i 1 j xi j 1 f24x i 1 j xij xi j 1 f39x i 1 j xij xi j 1 f25x i 1 j xij x i 1 jf38x i 1 j xij x i 1 j f26x i 1 j xi j 1 xij x i 1 jf37x i 1 j xi j 1 xij x i 1 j f27x i 1 j xi j 1 xij xi j 1 f36x i 1 j xi j 1 xij xi j 1 f28x i 1 j xi j 1 x i 1 j xi j 1 f35x i 1 j xi j 1 x i 1 j xi j 1 f29xi j 1 xij x i 1 j xi j 1 f34xi j 1 xij x i 1 j xi j 1 f30 x i 1 j xij x i 1 j xi j 1 f33x i 1 j xij x i 1 j xi j 1 f31x i 1 j xi j 1 xij x i 1 j xi j 1 f32x i 1 j xi j 1 xij x i 1 j xi j 1 4 T SZ 2 SZ 2 x xij 7 xij 3 1 T x ij xij i j Z2 T UD SZ 2 SZ 2 x xij 7 x i j 3 2 19 T UD x ij x i j i j Z2 T LR SZ 2 SZ 2 x xij 7 xi j 3 3 T LR x ij xi j i j Z2 T D SZ 2 SZ 2 x xij 7 xji 3 4 T D x ij xji i j Z2 T T UD TLR T D 3 1 T T UD TLR T D 3 1 SZ 2 64 T T UD TLR T D 18 3 2 f6 f7 f8 f9 f54 f55 f56 f57 x xij SZ 2 f6 x ij xij x i 1 j i j Z2 f7 x ij xij xi j 1 i j Z2 f8 x ij xij x i 1 j i j Z2 f9 x ij xij xi j 1 i j Z2 f54 x ij xij xi j 1 i j Z2 f55 x ij xij x i 1 j i j Z2 20 f56 x ij xij xi j 1 i j Z2 f57 x ij xij x i 1 j i j Z2 a f8 f6 T UD i j Z2 T UD f6 x ij x i j x i 1 j f8 T UD x ij x i j x i 1 j x T UD f6 f8 T UD f8 f6 b f6 f57 T i j Z2 T f57 x ij x i 1 j xij f6 T x ij x i 1 j xij x i 1 j xij x i 1 j xij T f57 f6 T f57 f6 c f7 f9 T LR i j Z2 T LR f7 x ij xi j xi j 1 f9 T LR x ij xi j xi j 1 x T LR f7 f9 T LR f7 f9 d f57 f54 T D i j Z2 f57 T D x ij xji x j 1 i T D f54 x ij xji x j 1 i x T D f54 f57 T D f54 f57 T f7 f56 f9 f54 f8 f55 SZ 2T SZ 2T LR SZ 2T SZ 2T D SZ 2T SZ 2T UD SZ 2T SZ 2 f56 y f7 y f9 y f54 y f57 y f6 y f8 y f55 y SZ 2T SZ 2T LR SZ 2T SZ 2T D SZ 2T SZ 2T UD SZ 2T SZ 2 21 f6 f7 f8 f9 f54 f55 f56 f57 3 2 64 18 1f0f63f12 3f62f2f3f4f54 5f58f59f60f61f6f7f8f9f54f55f56f576 7f10f12f13f15f48f50f51f53f11f14f49f528 9f16f19f21f24f47f44f42f3910 11f20f25f38f4312 13f17f18f22f23f40f41f45f4614 15f26f27f29f30f33f34f36f37f28f3516 17f31f3218 T T UD TLR T D 70 256 88 4 256 88 Neumann T T UD TLR T D T T UD TLR T D 4294967296 3 1 N 0 30 31 N TN TN T T TN TN T TN T 1 TN T N N 31 30 0 N P31 i 0 31 i 2i 0 30 31 T 31 30 0 3 5 0 30 31 T UD i0 i1 i31 3 6 22 i0 i1 i31 0 16 2 18 4 20 6 22 8 24 10 26 12 28 14 30 1 17 3 19 5 21 7 23 9 25 11 27 13 29 15 31 0 30 31 T LR i0 i1 i31 3 7 i0 i1 i31 0 1 8 9 4 5 12 13 2 3 10 11 6 7 14 15 16 17 24 25 20 21 28 29 18 19 26 27 22 23 30 31 0 30 31 T D i0 i1 i31 3 8 i0 i1 i31 0 8 16 24 4 12 20 28 1 9 17 25 5 13 21 29 2 10 18 26 6 14 22 30 3 11 19 27 7 15 23 31 3 2 1 T T T UD TLR TD T2 Id T 1 T T T T T Id 2 T UD T LR T LR T UD TUD T D T D T LR TLR T D T D T UD 1 2 T UD TLR T D T UD T D T D T LR T LR T D T D T UD 3 3 Id T T UD TLR T D 16 g0 Id g1 T g2 T UD g3 T LR g 4 T D g 5 T T UD g 6 T T LR g 7 T T D g 8 T UD T LR g9 T UD T D g 10 T LR T D g 11 T T UD T LR g 12 T T UD T D g13 T T LR T D g 14 T UD T LR T D g 15 T T UD T LR T D 3 2 T T UD TLR T D SZ 2 16 8 4 2 1 N y 0 30 31 N N N N g0 y y i 0 1 15 gi y N 16 i j 0 1 15 gi y gj y C2 16 3 5 3 8 23 a g1 y y 3 2 g2 y g5 y g3 y g6 y g4 y g7 y g8 y g11 y g9 y g12 y g10 y g13 y g14 y g15 y N 8 i 1 2 3 4 gi y y N 8 b g5 y y g1 y g2 y 3 2 g6 y g8 y g7 y g10 y g9 y g15 y g3 y g11 y g12 y g14 y g4 y g13 y N 8 i 5 6 7 8 9 10 gi y y N 8 c g11 y y g1 y g8 y 3 2 g5 y g3 y g6 y g2 y g7 y g14 y g12 y g10 y g13 y g9 y g15 y g4 y N 8 i 11 12 13 14 gi y y N 8 d g15 y y g14 y g1 y g13 y g2 y g12 y g3 y g11 y g4 y g7 y g8 y g6 y g9 y g5 y g10 y N 8 i j 0 1 15 gi y gj y N 8 i j gi y gj y N 4 N 16 8 4 2 1 N0 4210689285 y 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 g3 y y g6 y g1 y g8 y g2 y g10 y g14 y g5 y g11 y g7 y g12 y g9 y g4 y g13 y g15 y N0 8 g1 y 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 g2 y 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 g3 y 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 g4 y 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 g5 y 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 g7 y 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 g10 y 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 24 g13 y 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 25 S 0 1 r 1 4 1 N 7 P j 0 j 2j j 0 1 j 0 1 7 22 3 256 4 1 256 HN N 56 H56 70 x SZ H56 x i xi 1 xi xi 1 xi xi 1 i Z 4 1 4 1 xi 1xixi 1yi 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 permutive 46 50 53 58 60 2002 L O Chua Wolfram 62 67 71 75 Bernoulli 4 1 70 256 88 26 4 2 51 53 15 30 45 60 90 105 106 150 154 170 SZ 0 4 3 71 75 Bernoulli 2 3 11 37 42 56 SZ Bernoulli 56 Bernoulli ComplexBernoulli rule 65 18 SZ 1 H56 63 characteristic function 256 56 Bernoulli shift 56 Bernoulli shift 4 1 4 2 4 3 4 4 H56 4 1 56 4 2 56 4 3 56 1 1 4 4 56 4 4 H56 SZ x 27 T56 x x x i Z x i 1 i 1 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 SZ x H56 x x H56 x i x i xi 1 i Z 4 1 xi 1 xi xi 1 xi xi 1 xi 1 i Z xi 0 xi 1 xi 1 xi 1 xi 1 xi 1 0 x i 1 i 1 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 i Z SZ x i Z x i 1 i 1 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 56 H56 x i xi 1 i Z H56 x i x i xi 1 i Z H56 x x x 4 5 H56 SZ x H56 x x x i Z x i 1 i 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 x i xi 1 4 4 4 5 4 1 A B A 0 0 0 1 0 1 1 1 0 B 0 0 0 0 1 0 1 0 0 1 0 1 C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 56 4 1 1 A S B C 2 x SZ H56 x C 3 x C 0 0 x x A 1 1 x x B 56 4 3 4 4 28 4 2 A S B H56 T n 0 Hn 56 S Z A S B 4 1 A S B H56 x C 0 0 1 1 x x H56 A S B a 0 0 1 1 x 1 2n 4 0 0 1 0 1 0 z 2n 1 1 4 4 4 5 H56 x k k 1 0 0 k 2 1 0 k 3 2n 1 1 1 k 2n 2 1 1 Hn 56 x 1 2n 4 b 0 0 1 1 x 1 2m 4 1 1 0 1 0 1 z 2m 0 0 H56 x k k 1 0 1 k 2 2m 3 1 1 Hn 56 x 3 n 2m 2 n lim n Hn 56 x A S B 4 1 2 x SZ lim n Hn 56 x A S B H56 A B H56 4 6 1 A 2 A 10000 00010 00001 01100 00010 2 H56 A 29 3 H56 A log 1 2 1 5 0 4812 1 2 1 A 2 A 10000 00010 00001 01100 00010 2 n An 1 0 0 0 0 2 2 2 H56 A 3 A 1 2 1 5 2 2 1 A log 1 2 1 5 4 4 4 1 H56 A log 1 2 1 5 0 4812 4 6 H56 A A 0 H56 0 0 0 0 A A 0 A 0 1 0 0 1 1 1 0 1 1 1 0 A 2 A 0010 0001 1100 0010 n 6 A n A log 1 2 1 5 4 7 1 B 2 B 11000 00100 00011 11000 00100 2 H56 B 3 H56 B log 1 2 1 5 0 4812 30 4 6 4 7 4 3 1 H56 2 H56 0 Li Yorke Devaney 4 4 H56 A B Li Yorke Devaney H56 Li Yorke 2 H18 18 H18 70 x SZ H18 x i xi xi 1 xi 1 i Z 4 2 4 8 1 y SZ 1 1 1 y H18 y 2 y SZ I i j y i j 0 1 1 0 0 1 1 0 H18 y j 4 P k i 4 yk mod 2 1 18 1 2 x SZ y I 0 n y 0 3 y n 3 n 0 1 1 0 n 4 P k 4 yk mod 2 1 18 x 0 3 x n 3 n 1 0 0 1 4 2 y2 x2 x1 x2 x3 y3 x3 x2 x3 x4 yn 3 xn 3 xn 2 xn 3 xn 4 yn 2 xn 2 xn 3 xn 2 xn 1 4 3 n 2 P k 2 yk mod 2 n 4 P k 4 yk mod 2 1 xi xj xj xi xi xj xi xi 0 4 3 x2 x1 x2 xn 2 xn 2 xn 1 0 31 4 9 y SZ 1 1 y H18 y x SZ 1 1 1 x 1 1 y yi 1 yi 1 yi 1 0 x i 1 i 1 1 0 0 0 0 1 y 0 n 1 1 0 0 z n 1 n 1 x 1 1 1 0 0 x n n 2 0 0 1 a x 1 1 1 0 0 x 1 n 2 1 0 0 1 H18 x 0 n 1 y 0 n 1 b x 1 1 0 0 1 x 2 n 1 1 1 0 0 H18 x 0 n 1 y 0 n 1 1 1 1 x 1 n 2 4 8 4 9 1 1 y H18 y 1 0 0 1 x x SZ 4 5 H18 SZ H18 76 0 0 0 1 1 0 4 4 18 90 SZ 2 1 S 00 10 z SZ i Z zi 1 zi 1 0 zi 0 zi 1 0 4 9 4 10 H18 SZ H18 B R B SZ SZ x7 y 4 5 32 yi B x i 00 xi 0 10 xi 1 R SZ y7 z 4 6 zi R y i 1 i yi 2 10 0 R SZ SZ B R 4 3 4 11 SZ B H90 SZ R H2 18 SZ B SZ R 4 6 H2 18 SZ H90 H90 4 2 4 7 1 H18 2 H18 log2 3 H18 log2 2 4 SZ 2 01 SZ h1 SZ 2 SZ xij 7 x0j 4 7 h2 SZ 2 SZ xij 7 x0 j i 4 8 33 4 8 h1 h2 2 4 h1 h2 Ti h1 h2 y SZ h1 x SZ 2 y h1 x H H SZ SZ y7 h1 Ti x 4 9 yj h1 Ti x j j Z Neumann 4 9 H SZ 2Ti SZ 2 h y yh SZ H SZ 77 78 4 8 h1 h2 h1 h2 SZ 2 1 x xij SZ 2 xij x0j i j Z2 4 10 34 2 x xij SZ 2 xij x0 j i i j Z2 4 11 4 12 h1 1 h2 2 18 4 8 T1 SZ 2 SZ 2 xij 7 xij x i 1 j x i 1 j 4 12 T2 SZ 2 SZ 2 xij 7 xij xi j 1 x i 1 j 4 13 H18 4 12 1 T1 2 T2 SZ H18 4 7 1 T1 2 T2 SZ 2 T 1 SZ 2 T 2 log2 30 Church Turing Thesis 79 80 universal computation Conway 1970 43 game of life 3 35 blinker 4 5 glider 4 6 Conway Conway oo 4 5 2 Wolfram Mathew Cook 110 110 110 110 4 7 glider like ether collision glider gun 110 ECA 90 ECA 56 36 4 7 ECA 110 wwooooo ooooo ooooo ooooo ooooo ooooo oo wwooooo ooooo ooooo ooooo ooooo ooooo oo 4 6 20 4 13 69 110 110 H110 x i xi xi 1 xi xi 1 xi 1 xi xi 1 x SZ i Z 4 8 N 37 TN H110 T SZ 2 SZ 2 x7 T x 4 14 T x ij xij xi j 1 xij xi j 1 xi j 1 xij xi j 1 i j Z2 T SZ 2 SZ 2 x7 T x 4 15 T x ij xij xi j 1 xij xi j 1 x i 1 j xij xi j 1 i j Z2 4 14 4 15 T T bT 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 bT 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 NT 1023163644 NT 1010629884 4 9 NT 1023163644 NT 1010629884 4 11 4 12 1 hi SZ H110 i 1 2 NT 1023163644 NT 1010629884 T T UD TLR T D 2 S1 1023163644 1072709616 1515911930 1600123120 2694882725 3234054339 4026789891 4042261765 S2 267452400 268431600 1010629884 1061155056 1526356730 1609588720 2054847098 2088533116 2695209125 2711724449 3233858499 3250700737 38 4026593295 4026920965 4042260495 4042261251 4 10 S1 S2 24 NT 1023163644 Mathematica 6 0 m n Cij i 1 m j 1 n m n C 1 n T i m i 1 n 1 0 4 8 k k 4 8 123456789 1 2 3 4 5 6 7 8 9 123456789 1 2 3 4 5 6 7 8 9 10 123456789 1 2 3 4 5 6 7 8 9 123456789 1 2 3 4 5 6 7 8 9 200 123456789 1 2 3 4 5 6 7 8 9 123456789 1 2 3 4 5 6 7 8 9 4 9 1 2 9 1 4 14 Cij Ci j 1 Ci j 1 1 n i 39 4 9 ECA 110 NT m 2 110 0 1 NT C 4 10 5101520 5 10 5101520 5 10 1 5101520 5 10 5101520 5 10 144 oo 5101520 5 10 5101520 5 10 2 5101520 5 10 5101520 5 10 9 OO 5101520 5 10 5101520 5 10 3 5101520 5 10 5101520 5 10 8 OO 5101520 5 10 5101520 5 10 4 5101520 5 10 5101520 5 10 7 OO 5101520 5 10 5101520 5 10 5 5101520 5 10 5101520 5 10 6 OO 4 10 NT 144 3 40 4 11 i basin tree 4 12 17 51 119 47 121 203 221 65 195 455 68 204 476 71 205 479 113 211 503 175 505 779 179797 188 484 812845 881 884 260 780 272 816 284 820 893 286 818 887 307 311 375 989 382 962 583452 844 467 471 477 716 607 752 913 700 997 754 919 785811 861 885 970 4 11 ECA 110 10 12345678910 1 2 3 4 5 6 7 8 9 10 12345678910 1 2 3 4 5 6 7 8 9 10 2 12345678910 1 2 3 4 5 6 7 8 9 10 12345678910 1 2 3 4 5 6 7 8 9 10 5 12345678910 1 2 3 4 5 6 7 8 9 10 12345678910 1 2 3 4 5 6 7 8 9 10 4 12 1 3 5 7 9 5 4 41 C i j C 4 13 ECA 110 NT 123456789 1 2 3 4 5 123456789 1 2 3 4 5 3 H H H H H H H H H 123456789 1 2 3 4 5 123456789 1 2 3 4 5 21 OO 123456789 1 2 3 4 5 123456789 1 2 3 4 5 7 oo 4 13 ECA 110 2 3 4 7 C NT 21 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 200 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 350 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 760 OO 4 14 NT NT 4 14 4 15 42 NT 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 121 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 198 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 439 OO 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 276 1020304050 10 20 30 40 50 1020304050 10 20 30 40 50 327 OO 4 15 43 8 Neumann 0 1 22 5 4294967296 Neumann T T UD TLR T D 56 18 24 44 A 11 10 110 24 NT 1023163644 45 1 Wiggins S Global bifurcations and chaos analytical methods M Springer Verlag 1988 2 Morse M Trans Amer Math Soc 1921 22 84 3 Birkhoff G D Dynamical systems M Amer Math Soc publications 1927 Reprinted 1966 4 Morse M Hedlund G A Symbolic dynamics J Am J Math 1938 60 815 5 Smale S Diffeomorphisms with many periodic points in Differential and Com binatorial Topology C Princeton university press 1964 63 80 6 Metropolis N Stein M L Stein P R Finite limit sets for transformations on the unit interval J J Comb Theory 1973 15 1 25 43 7 Chen F Y CNN symbolicdynamical systems D Shanghai Shanghai university 2004 In Chinese 8 Robinson R M Undecidability and nonperiodicity for tilings of the plane J Inventiones mathematicae 1971 12 177 209 9 Kastelyn P W The statistics of dimers on a lattice J Physica A 1961 27 1209 1255 10 Berger R The undecidability of the domino problem J Memiors of the Amer Math Soc 1966 66 1 72 11 MilnorJ Thurston W On iterated maps of the interval J Lecture notes in math ematics No 1342 Springer 1988 12 Alekseev V M Yakobson M V Symbolic dynamics and hyperbolic dynamic systems J Physics reports 1981 75 5 290 325 13 Sparrow C The Lorenz equations bifurcations chaos and strange attractors M Springer Verlag 1982 14 Haenggi M Java CNN simulator http www isi ee ethz ch 46 15 M 1997 16 M 1994 17 M 1993 18 Lind D Multidimensional symbolic dynamics J Proc Symp Appl Math 2004 40 61 79 19 RobinsonE A Symbolicdynamicsand tilingsofRd J Proceedingsofsymposia in applied mathematics 2004 60 81 119 20 Hochman M Meyerovitch T A characterization of the entropies of multidimen sional shifts of fi nite type J Preprint 2007 21 JohnsonA S A MaddenK M Thedecompositiontheoremfortwo dimensional shifts of fi nite type J Proceedings of the Amer Math Soc 1999 127 1533 1543 22 Baxter R J Exactly solved models in statistical mechanics M London aca demic press Inc 1989 23 Walters P Symbolic dynamics and its applications M Amer Math Soc 1992 24 Williams S G Symbolic dynamics and its applications M Amer Math Soc 2004 25 Kitchens B Symbolic dynamics one sided two sided and countable state Markov shifts M Berlin Springer Verlag 1998 26 Robinson E A Jr Sahin A A Mixing properties of nearly maximal entropy measures for Zd shifts of fi nite type J Colloq Math 2000 84 85 part 1 43 50 27 Ban J C Lin S S Patterns generation and transition matrices in m