连续时空转化为离散系统：动力学、元胞自动机、偏微分方程和拓扑

×→理论计算机科学电子笔记120（2005）173-186www.elsevier.com/locate/entcs连续时空上的转移系统武内泉1FacultyofSiences，Tohouiversity，Miyama，Hunabasi，274-8510，JAPAN摘要本文给出了连续时空上的一个过渡系统，它是由连续时空的函数系统转化为离散状态的函数系统。该系统介于元胞自动机和偏微分方程之间。本文给出了解唯一的合理充分条件。关键词：动力学，时间发展，元胞自动机，偏微分方程，一般拓扑1介绍1.1动机时间发展一般被描述为函数φ：X T A，其中集合X表示空间或自由度，T是时间的集合，A是属性的集合。在函数φ：X×T→A的约束下描述了时间发展规律。根据每个应用的目的，集合X是表示系统的小自由度的几个元素的离散集合、表示空间的网格的大量元素的集合、或连续空间R。类似地，集合T有时是Z，有时是R。属性A的集合是1电子邮件地址：takeuti@kuis.kyoto-u.ac.jp1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.043174I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173--×→×→−2有时一组离散的状态Q=q1，q2，. q n，有时连续R表示波的位移。对于离散时间T=Z，符号动力学是{·} ×Z→Q。 元胞自动机[1]是Z×Z→Q，映射动力学是{·} ×Z→R，而高维映射动力学是对于X×Z→R，对于某个X<$Z。R×Z→R的一个例子是函数空间上的映射动力学[5，6]。对于连续时间T=R，一个普通的微分方程描述了一个{·}×R→R的系统，一个高维的普通微分方程描述了一个X×R→R的系统，对于某个X∈Z，一个偏微分方程描述了一个R×R→R的系统.已知非线性偏微分方程模拟一类细胞自动机[2，3，4]。本文研究了连续时空上的转移系统，即RnRQ系统。该系统介于元胞自动机和偏微分方程之间。1.2决定论与芝诺我们感兴趣的是RnRQ的确定性系统。那是-因为，在通常情况下，非确定性系统包括确定性系统作为特殊情况，并且确定性系统被认为比非确定性系统简单。非确定性系统的定义是没有意义的，除非这个定义既能描述确定性又能描述适当的非确定性。具有较高自由度的动力学最简单的例子是前进波。 对于元胞自动机，我们定义了φ：Z × {0，1，2，.. } → {0， 1}为：––φ（0，0）= 1，且φ（x，0）= 0，其中x= 0。那么解决方案是：如果−t≤x≤t，则φ（x，t）= 1，否则φ（x，t）= 0。这个φ表示向左和向右行进的波对于偏微分方程，将波函数方程φ：R×R→R，∂2φ ∂2φ=.第二章则解为φ（x，t）=φ+（x−t）+φ−（x+t），这是以下等式的总和：I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173175≤|− |≤−两个波;一个向左前进，另一个向右前进。将上面的元胞自动机简单地转换为R×R→ {0， 1}的系统将如下所示φ：[0，∞）×R→ { 0， 1}的朴素转换规则写为：• φ（x，t）= 1，如果对任意φ>0，存在（xJ，tJ），使得t−φ tJ 0，使得对于任何点（x j，tj），使得ttJ0. n（xJ，tJ）. t−δ< tJ 0。n（xJ，tJ）. t ≤tJ 0。这种困难似乎是芝诺悖论的反面为什么波的存在没有原因？这是因为t= 1的波在时间t= 1/ 2有原因，t=1/ 2的波在时间t= 1/4有原因，t= 1/ 2n的波在时间t= 1/ 2n+1有原因，等等。为了避免这种困难，我们定义了基本函数和速度条件的概念。基本函数的直观含义在基本函数所描述的发展过程中，人们总是可以将每个现象的原因追溯到初始条件。它的正式定义见定义2.10和4.2。速度条件是转换规则的条件。速度条件的直观含义是，以速度v前进的波不会使效应快于其速度v。它的正式定义见定义4.5。通过这些工具，我们证明了在某种约束下解的唯一性.这就是定理4.16，这是本文的主要定理。与例1.1一样，这组转换规则实际上满足速度条件。函数φJ不是基本函数，函数φ1是唯一的基本函数，它是转移规则的解。2时空上的拓扑算子定义2.1（时空）设X是完备度量空间。则集合U=X×R称为时空，其中左部分X被视为空间，右部分R被视为时间。例2.2设X是Rn的闭子集。X×R是一个时空。定义2.3（累加算子）设U是一个时空。我们定义了E U上的算子A+和A−，其中v≥0。V V• A+（E）I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173177vvvv>vvW 0。n（xJ，tJ）. t− <$ 0。<$（xJ，tJ）.t tJvw v2.51. U=A+（U）2。=A+（3. E<$E J<$A+（E）<$A+（EJ） 4. A+（A+（E））5. A+（E<$E J）=A+（E）<$A+（E J） 6。v≤w<$A+（E）<$A+（E）对于A−v，类似的性质也成立。定义2.6（闭包、内部、边界）闭包算子F+和Fv−，内部算子G+和G−，以及边界算子+并且根据A+和A−v来确定A − v。为欧洲和其他国家数v≥0，它们被定义为：Fv−（E）=E<$A+（E），Fv−（E）=E<$A−v（E），G+（E）=U-F+（U-E）， G-（E）=U-F-（U-E），+（E）= F+（E）− G+（E），注2.7与Prop.2.5为这些操作员保留F+、F −、G+、G−、+和−。v v v v v v定义2.8（闭集，开集）对于每个实数v≥0，闭集和开集的族定义如下：F+={EU|E= F+（E）}，F− ={E <$U |E = F −（E）}，G+={EU|E = G+（E）}，G−={E<$U|E = G−（E）}。注2.9若v≤w，则下列成立：⊂ F+、F−F−，G+<$G+，G− <$G−。w v w v定义2.10（基本集合）对于每个实数v≥0，我们定义一个集合族Dv为：Dv={EU|E∈F0−，Fv−（<$0−（E））<$E}.一个集合E∈ Dv称为在速度极限v的基本集合。注2.11如果v≤w，则Dw <$Dv。178I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173注2.12这个Dv在有限并集下是封闭的。I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173179∈vvvvvv3模态逻辑定义3.1（状态）有限集合Q ={q1，q2，.，q n}称为状态集，ndn元素ntqiQiscalledastatee. 国家对数学公式进行了重新定义。定义3.2（公式）公式定义为以下语法。P：：= q|欧元/英镑|PP|QvP（q∈Q，v≥ 0）我们把所有公式的集合记为P。我们写Pv为所有公式p的集合，这些公式p没有任何模态算子Qw的出现，使得vw。注意QPvP。记法3.3p<$pJ=<$（<$ p<$$>pJ），Qvp=<$Qv<$p。符号3.4<$、Q和Q的联系的幂是最强的。第二个是，它是最弱的，它是最弱的定义3.5（全模态公式）一个公式p∈P是全模态的，如果任何q∈Q在p中的任何出现都在Q的我们对于所有全模态化公式的集合，写PM，并写PM为PM= P MP v.定义3.6（公式的解释）对于U的部分函数φ[10][11][12][13][14][15][16][17][18][19][19][1[[q]] φ= φ−1（q），[<$p]]φ= U − [[p]] φ，[p <$pJ]] φ=[[p]] φ <$[[pJ]] φ，[[Qvp]]φ=A+（[[p]]φ）.记法3.7对于函数φ：U→Q，我们记为φ|E表示通过将域限制到E中而得到的函数。命题3.8 对任意v≥0 ，任意子集E∈ G+，任意函数φ，φJ：U→Q 使得φ|E=φJ|E和任意公式p∈Pv，则[[p]] φ<$E =[[p] φJ<$E.命题3.9对任意v≥0，任意子集E∈ G+，任意函数φ，φJ：U→Q使得φ|E= φJ|E和任何公式p∈PM，则[[p]] φ∈++Fv（E）=[p]] φJ<$Fv（E）.定义3.10（正发生，负发生）在公式p∈P中，状态q∈Q的正发生和负发生的概念按通常的方式定义。注3.11对于每一个公式p，都有一个公式PJ，它在逻辑上等价于p，并且只有状态q的两个公式p和pJ的逻辑等价性定义为：[p]]φ=[[pJ]]φ，对于任何总数180I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173∈联系我们|}∈QJQ函数φ：U→Q。 实际上，这样的pJ是由p通过替换每个每个状态q的负发生，公式为<$qJ。定义3.12（公式中的传播速度）公式p PM中状态q的传播速度是最大的数v，使得公式p在Qv的范围内有q的正出现，或者有除q之外的某个QJ的负出现。如果不存在这样的v，则传播速度定义为−∞。我们将q在p中的传播速度记为Pr（q，p）。例3.13成立Pr（q，Qvq）=v和Pr（q，Qv<$q）=−∞。公式<$Qvq在Qv的范围内有q的负出现。事实上，q在Qv中正发生，但在<$Qvq中负发生。 因此，对于状态qJ/= q，Pr（q，<$Qvq）=−∞且Pr（qJ，<$Qvq）=v。注3.14q的传播速度的定义提到了除q以外的状态的负发生。这是因为q以外的状态的负出现可以通过如注释3.11中的替换而变成q的正出现。引理3.15设φ，φJ：U→Q且p∈PM。设（x，t）∈ [[p]] φ，（x，t）/∈ [[p]] φJ.然后，对于任何n>0，存在一个点（xJ，tJ）使得：0t-tJ<，t0 ={（x，t）∈ U|t>t0}，U（t1，t2）={（x，t）∈ U|{<<\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}定义4.2（基本函数）对于v≥0，函数φ：U→Q或φ：U≥t0→Q是速度极限vi <$φ−（q）∈ Dv的基本函数，1每个q∈Q。我们将速度极限v下的所有基本函数φ：U→Q的集合记为Φv。 对于所有基本函数的集合，我们记为Φv，≥t0φ：U≥t0→Q在速度限制v时。注4.3基本函数的概念是半开区间概念的推广。实际上，对于基本函数φΦv和状态q Q，集合t T φ（x，t）=q是半开区间[t，tJ）的可数并。JJI. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173181v→注4.4若φ ∈Φ v，则φ|U≥t0∈Φ v，≥t0.反之亦然。对于每个函数φJ∈Φ v，≥t0，存在一个全函数φ∈Φ v使得φJ= φ|U≥t0。这个φ被构造为：如果t≥t0，则φ（x，t）=φJ（x，t），如果t0，则φ（x，t）=φJ（x，t0）。<定义4.5（转移规则）一个三元组<$q，v，p<$∈Q×[0，∞）×PM称为转移规则。规则<$q，v，p<$p意味着，如果p成立，那么状态以扩展速度v变为q。定义4.6（在一点上满足规则）U到Q的部分函数φ满足一个过渡规则<$q，v，p<$在一个点（x，t）∈ U i <$它们满足关系φ| =（x，t）<$q，v，p定义为：φ|=（x，t）<$q，v，p<$$><$$>（x，t）∈G−v（φ−1（q））<$[[<$p]]φ。定义4.7（区域中规则的满足）U到Q的部分函数φ满足转换规则<$q，v，p，在区域E<$U i，它们满足关系φ| = Eq，v，p定义为：φ|= E<$q，v，p<$$><$q（x，t）∈E. φ |=（x，t）<$q，v，p<$<$E<$[[p]]φ（x，t）<$G−v（φ−1（q））.定义4.8（变迁系统）变迁系统是变迁规则的有限集合S。速度限制为v的转移系统是一个有限子集S<$Q×[0，v]×PM。定义4.9（完备性）一个转移系统S={，q2，v2，p2 <$q k，v k，p k<$$>}在速度限制v i <$时是完备的，对于每个函数φ ∈Φv，则U=1≤i≤k[[p i]] φ，相当于：φ |= Up1p2... 赫里普湾猜想4.10对于迁移系统S ={q1，v1，p1，q2，v2，p2，.，<$qk，vk，pk<$}，如果S在某个速度极限v下是完备的，则对于每个函数φ：UQ，它保持U =[[p i]] φ。1≤i≤k定义4.11（系统中的传播速度传播速度系统S中状态q的最大值是p的Pr（q，p）<$qJ，v，p <$∈S。 请注意，状态qJ在qJ，v，p中可能与q不同。我们将q在S中的传播速度记为Pr（q，S）。定义4.12（速度条件）一个系统S满足速度条件i，则存在q0∈Q，使得对于每个q，v，p∈S，它满足Pr（q，S）≤v，或q=q0，Pr（q0，p）= 0，并且对任意其它的∈S，182I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173≤⟨ ⟩ ∈|若qJq0且Pr（qJ，p）≥0，则Pr（q，pJ）0.<这个q称为异常状态.注4.13如果对于每个q，v，p S，系统保持Pr（q，S）v，则系统S满足速度条件。定义4.14（在具有正厚度的初始条件下的解）对于一个过渡系统S和一个函数φ0：U（−k，0）→Q，一个函数φ：U≥−k→Q是S在初始条件φ0iφ|U（−φ，0）= φ0，且φ| = U≥0R，对于每个R∈ S。定义4.15（在Hagiya初始条件φ（x，0）= φ0（x），以及|= U>0R，对于每个R∈ S。定理4.16（主要定理）设S是一个有速度限制v.假设S在速度极限v下完备，且S满足速度条件。设φ0是一个函数X→Q。则S在初始条件φ0在Φ v，≥0处的解是唯一的，如果它存在的话。 换句话说，如果函数φ，φJ∈Φ v，≥0都是S在初始条件φ 0的解，则φ = φJ。我们将在后面证明这个定理。首先，我们把这个定理的推论。推论4.17设S是速度限制为v的过渡系统，设S在速度限制为v时完备，S满足速度条件。设φ0是U（−φ，0）→Q中的函数。那么，S在初始条件φ0在Φ v，≥−φ中的解是唯一的，如果它存在。证明的大纲。函数φ|X×{0}是t = 0时的解，由于命题φ 0，它是由初始条件φ0唯一确定的三点九函数φ|U≥0是S在Hagiya初始条件φ X ×{ 0 }下的解。因此，由于主要定理（Thm.），整个函数φ4.16）。Q在此之后，我们定义了几个概念，以证明主要定理（Thm。4.16）。定义4.18（差集）设S是一个在速度限制v下的过渡系统，它在速度限制v下是完备的，并且满足速度条件。对于两个函数φ，φJ∈Φ v，≥0，使得φ| = U>0S和φJ|= U>0S。然后，差集是集合{（x，t）∈U≥0|φ（x，t）φJ（x，t）}。I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173183∈ℵ|∈∈∈⊂联系我们定义4.19（因果关系）对于两个点（x，t），（xJ，tJ）i，点（x，t）是（xJ，tJ）i的原因，以下成立：1. t0。对于零：因为φ和φJ是不同的，所以差集φj不是空的。故有一点（x，t）∈ [x，t]。我们把f（0）=（x，t）代入这个（x，t）。对于后继者：我们定义f（α+1）为后继者α+1。作为归纳假设，我们已经定义了f（α）。 根据引理4.20，存在（x，t）<$U>0，这是f（α）的原因。对于这个（x，t），我们设f（α+1）=（x，t）。我们必须去检查一下|{β|β≤α+1}是一条因果链。在诱导假设中，我们已经知道f{β|β≤α}是因果链。 因此它证明了对任意的β≤α，存在一个从f（β）到f（α+1）的有限因果链.184I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173这是因为我们已经有了一个有限的因果关系I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173185≤--|从f（β）到f（α）的链对于极限：我们将定义f（α）对于一个极限序数α。有一个递增序列α1，α2，α3，. 它收敛于α。作为归纳假设，我们已经对β α和f定义了f（β）<，|{β|β< α}是因果链。因 此 ，我们可以选择序列{f（α1），f（α2），f（α3），. }作为因果链。根据引理4.24，存在（x，t）∈N使得链f（α1），f（α2），f（α3），.， （x，t）是因果链。 我们把f（α）=（x，t）设为（x，t）。我们必须检查f {β|β≤α}是因果链。 结果表明，对于每个β α，存在一个从f（β）到f（α）的有限因果链.这是因为我们已经有了一个从f（β）到f（α n）的有限因果链，其中α n> β。这样我们就构造了一个因果链f：Ord（U1）→U>0。对于α∈1，将（xα，tα）设为（xα，tα）=f（α）。则00，t≥（x−1）2+y2φ：U≥0→Q，φ（x，y，t）=黑色，x= 0，t≥其他的都是白色的中国2+ 1规则R6是一个伪规则;这个规则实际上并不适用于任何点，也就是说，[<$（p1<$p2<$p3<$p4<$p5）]]φ=φ。系统S具有规则R6，因为它使系统完备。例5.3空间是一条线X = R，状态集是Q =Z/5Z=<$0，<$1，<$2，<$3，<$4，这是一个p=5的循环群。 ItholdsinQthat1=<$4=<$9=. ，2=<$3=<$8=.和SOForth。转换系统S是定义如下。For<$i∈Q，R1，<$i=<$i，1，P1，<$i，P1，<$i=Q1<$i Q1（<$ii−1），R2，<$i=<$i，1，P2，<$i，P2，<$i=Q1<$iQ1（<$ii−2），R3，<$i=<$i，1，P3，<$i，P3，<$i=Q1i−1Q1i−2，R4，<$i=<$i，1，P4，<$i，P4，<$i=Q1<$i，R5=<$$>0，1，<$（P1，<$0<$. P4，P4）S={R1，<$0，...，R4，R5}该S是限速1时的过渡系统，在限速1时完成，满足速度条件。初始条件定义如下。函数φ∈Φ1，≥−φ，φ：U（−φ，0）→Q定义为：I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173187{|联系我们m，n∈Z，n≤t+xn+ 1，m≤t−xn +1<$φ（x，t）=n+2m.面积（x，t）n t+x< n+1，m t x< m+1是一个最低点为（m+n/2，n-m/2）的斜正方形。这样的广场的集合填满了整个平原。这是一个很好的定义。 初始条件φ0定义为：φ0=φ|U（−c，0）.因此，函数φ是S在初始条件φ0下的解。注5.4在这个例子中，φ在一维直线上形成周期性的间隔.一般来说，在n维空间Rn上，我们可以构造一个过渡系统和一个初始条件，使得该解成为周期胞。本例中的状态集仅表示细胞的阶段。 如果我们把状态集作为颜色集和一组相位，如Q={白，黑} ×Z/ 5Z，则系统可以实现细胞自动机。这可以推广到更高维度的空间。确认这项工作是通过与田锅雅美、田边俊则和其他参与者的非正式会谈进行讨论而完成的。作者对他们非常Hagiya给了我们他的例子（前。5.2）首先，然后问我们这个例子是解决方案的系统是什么田边 指 出 ， 人 们 必 须 确 保 前 进 波 速 度 的 下 限 本 文 以 正 厚 度（Def.degree）为初始条件，建立了一个系统#24444;，并向与会者展示然后，Hagiya建议作者将初始条件设为无厚度（Def.4.15）。作者感谢匿名裁判的评论。引用[1] 加德纳，马丁，细胞自动机，自我繁殖，伊甸园和游戏“生活”。，Scienti fic American，February，1971，112[2] 林文胜，等离子体中脉冲的碰撞与自复制，国立台湾大学机械工程研究所硕士论文，1997[3] Hayase Yumino Ohta Takao，反应扩散系统中的Sierpinski垫片，物理评论Lett。81（1998），1726[4] Hayase Yumino，Sierpinski gasket in excitable media，Forma15（2000），267[5] 张文，等.复杂系统动力学中的动力学网络.北京：清华大学出版社，2001（ 4 ） .188I. Takeuti/Electronic Notes in Theoretical Computer Science 120（2005）173[6] 张文忠，函数动力学，国立台湾大学数学系硕士论文，2001