Number-conserving cellular automata I: decidability
Descrição do Produto
∗ †
≥2
O(s log s)
∗ †
s
S = {0, 1, ! " . . . s} C = c | c : Zd → S
∀!v "∈ Zd , 0(!v ) = 0 ! !v ∈ Zd | c(!v ) %= 0 N u !v1 , . . . , !vu f : Su → S
d, S, N
c : Zd → S d 0
c
c CF (d, S, N, f ) f
A : SZ → SZ d
∀c ∈ S Z ∀!v ∈ Zd , A(c)(!v ) = f (c(!v + !v1 ), . . . , c(!v + !vu )) . d
S C
C
d
0
i th
∀i ∈ 1, . . . , d, A ◦ σ!ei = σ!ei ◦ A
!ei
1
!ei
∀c ∈ C ∀!v ∈ Zd , σ!ei (c)(!v ) = c(!v + !ei ) . 'C, F (
A
c ∀!v ∈ c(!v + !πc ) = c(!v ) c CP 0 ≤ !v < !πc !v ∈ Zd
!πc
Zd ,
d
i ∈ {1, . . . d} !vi
!πc
∀i ∈ {1, . . . , d} , 0 ≤ !vi < (!πc )i i th !v
{−r, . . . , 0, . . . , r} f : S 2r+1 → S
r
∀c ∈ C ∀i ∈ Z, F (c)(i) = f (c(i − r), . . . , c(i), . . . , c(i + r)) . ∀c ∈ C ∀i ∈ Z, σ(c)(i) =
σ c(i + 1)
A
d
∀c ∈ CP , A
A #
c(!v ) =
0≤! v
2ls β−α
α>β 4ls α−β
3→1
x>
A A
M =m M 1 n
µn (A(y)) µn (y)
≥ l−&
l ∈ R ∪ {+∞}
µn (A(c)) ≥ (l − &)µn (c) A δ0 &>0
A(y) !
+
(0, 0) (1, 0) (0, −1) (1, −1) f
+
,A = (2, N, Q, f ) f : Q4 → Q A
a c
b d
,
- + + f - + + f - + + f - + + f
=a
0 0 0 c 0 0 0 b 0 0 c d 0 b 0 d
N =
,
,
,
,
−f −f −f −f
+
+
0 0
0 a
0 0
0 d
+
0 a
0 b
0 a 0 c
+
,.
,.
,.
,.
)c
.
A A
c
A
)A a+b+c+d
... ... ... ... 0 0 ... 0 a ... 0 c ... 0 0 ... ... ...
= f
+
+f +f
0 0 +
+
0 a 0 a a c
... ... ... 0 0 ... b 0 ... = a + b + c + d. d 0 ... 0 0 ... ... ... ...
,
+ , + , + 0 0 0 c d +f +f +f b 0 0 0 0 , + , + , + 0 c d 0 a +f +f +f b 0 0 0 c , b d
0 0
,
b 0 d 0
a b+c+d
= f
+
+f
f
+
a b c d
,
0 b +
+ , + , + , 0 0 0 c 0 0 +f +f +f 0 b 0 0 0 c , + , + , + , d 0 c d b 0 0 b +f +f +f 0 0 0 0 d 0 c d
=a
0 0
,
+f −f
+
+
0 0
0 b
0 0
0 a
,
,
+f −f
+
+
0 0 0 c 0 a
0 b
,
,
+f −f
+
+
0 b c d 0 a 0 c
,
,
,
b=0 , + , + , + , 0 0 0 c 0 0 d 0 +f +f +f 0 c 0 0 d 0 0 0 + , + , 0 0 c d +f +f c d 0 0
c+d =
+
f
0 c
f
b d
+
,
=b
+f −f
f
+
a c
b d
,
+
+
0 d
0 0
0 b
0 0
,
,
+f −f
+
+
0 c
0 d
b 0 d 0
,
,
−f
+
0 0
0 b
,
+
, + , + , + , b 0 0 0 0 0 0 0 = a+b−f +f −f +f d 0 c d a b 0 c + , + , + , + , 0 0 0 0 0 0 0 a −f +f −f −f 0 a d 0 b 0 0 c
A
)A
f
+
b 0 d 0
,
=
+
... ... ... ... 0 0 ... 0 b ... 0 d ... 0 0 ... ... ...
... 0 0 0 0 ...
... ... ... ... ... ...
b 0 0
b+f + 0 b −f 0 d
0 d ,
,
+f
[f (. . .) − f (. . .)]
+
0 0 d 0
= b + d. ,
−f
+
0 0 0 b
,
−f
+
0 b
0 0
,
!
A = (2, N, Q, f ) (0, 0) (0, 1) . . . (0, n − 1) (1, 0) (1, 1) . . . (1, n − 1) N = (m − 1, 0) (m − 1, 1) . . . (m − 1, n − 1)
f : Qm×n → Q A
x1,1 x1,2 . . . x1,n x2,1 x2,2 . . . x2,n f xm,1 xm,2 . . . xm,n
0
m−1 0 n−2 ## + f ' i=0 j=0
0
m−2 0 # n−1 # + f ' i=0 j=0
... 0 ... 0 () *
j+1
0
... 0 ... 0 () * j
0
= x1,1 0
xm−i,2
... ...
xm−i,1 0 ... 0
x1,n−j x2,n−j
. . . xm−i,n−j
... ...
x2,n−j x3,n−j
. . . xm−i,n−j
i m−1 n−1 0 ... 0 # # () * − f ' x1,1 j i=0 j=0(i+j>0) x 2,1 0 xm−i,1
0
i+1
x2,1 x3,1
i
x1,2 x2,2
0 ... ...
x1,n−j x2,n−j
. . . xm−i,n−j
0
m−2 0 n−2 ## − f ' i=0 j=0
... 0 ... 0 ... 0
... 0 ... 0 () *
j+1
0
0
i+1
... ...
x2,2 x3,2 xm−i,2
x2,n−j x3,n−j
. . . xm−i,n−j
0 x1,1 x2,1
0 x1,2 x2,2
... ...
0 x1,n x2,n
0 0 0
... ... ...
0 . . . 0 xm,1 ... 0 0
xm,2 0
. . . xm,n 0
0 0 0
... ...
x1,1 + x1,2 + . . . + xm,n A x1,1 x1,2
A
f (. . .) x1,n
x1,n x2,n = x1,1 + x1,2 + . . . + x1,n xm,2 . . . xm,n x1,2 x1,3 . . . x1,n 0 x2,2 x2,3 . . . x2,n 0 −f + ... xm,2 x1,2 . . . xm,n 0
x1,1 x2,1 f xm,1
x1,2 x2,2
... 0 ... 0 ... 0
... ...
0 x1,2 x2,2
0 x1,3 x2,3
... ...
0 x1,n x2,n
0 0 0
... ... ...
0 . . . 0 xm,2 ... 0 0
xm,3 0
. . . xm,n 0
0 0 0
... ...
x1,2
x1,2 x2,2 f xm,2
x1,3 x2,3
... ...
x1,n x2,n
xm,3
. . . xm,n
x1,3
0 0 . 0
x1,n
f f
x1,1 f
x2,2 x1,2 $
x2,1 m $n i=1 j=1 xi,j
!
n g
0 ... 0
i−1+a m−a 0 ... 0 # n−b # () * g(a, b) = f ' j−1+b xa,b i=0 j=0 x a+1,b 0 xm−i,b
a, b ∈ {1, 2}
i+j >0
a+b=2
0 ... ...
xa,n−j xa+1,n−j
. . . xm−i,n−j
A
x1,1 x1,2 . . . x1,n x2,1 x2,2 . . . x2,n f xm,1 xm,2 . . . xm,n
= x1,1 + g(1, 2) + g(2, 1) − g(1, 1) − g(2, 2).
g j
0
k 1+ c
0 m
a n
b l
0 0
i
0
c
g (a, b, c) =
1+ b
f
0
0 0
i = 0 j = 0 k= 0
x a,b,c
x a,n j,c
x a,b,k l x a,n j,k l x m i,b,c x m i,n j,c
i+ j+ k >0 if a+ b+ c = 3
x m i,b,k l
g(1, 2, 2) g(2, 1, 2) g(a, b, c)
g(a1 , a2 , ..., an ) A = (n, S, N, f ) ∀j ∈ 1, . . . n dj
f (x1 , ...xm ) = x1 +
1+ a
g(2, 2, 1) (a − 1, b − 1, c − 1)
m = |N | = d1 ×d2 ×. . .×dn j A m ∀(x1 , ...xm ) ∈ S
d# 1 −a1 d# 2 −a2 i1 =0 i2 =0
∀i, 1 ≤ i ≤ n, ai ∈ {1, 2}
x m i,n j,k l
...
dn −an #
(−1)k g(a1 , a2 , ..., an ),
in =0
k = 1 (a1 − 1, a2 − 1, ..., an − 1) (n − 1) k = 2
s
O(s log s)
O(s log s)
O s
O(log s)
n
!
Lihat lebih banyak...
Comentários
