移位拓扑熵的计算及2型可计算性分析—标号有向图、语言和禁止词集的研究.

理论计算机科学电子笔记167（2007）131-155www.elsevier.com/locate/entcs移位拓扑熵的计算克里斯托弗·斯潘德尔1Institutfur？TheoretischeInformatikundMathematikUniversit？atderBundeswehrMu？nchenD-85577 Neubiberg，德国摘要利用标号有向图、语言和禁止词集研究了一类移位动力系统的相应的命名系统进行了分析，根据约简，特别是关于相对于所提出的命名系统的拓扑熵的可计算性。事实证明，所有检查的自然表示分为两个等价类，并且拓扑熵通常对于定义的自然表示不可计算。然而，如果一个特定的标记有向图表示- 即原始的，右分解的标记有向图-的某些类别的移位，即具有指定属性的移位，则拓扑熵变得可计算。关键词：移位动力系统，拓扑熵，2型可计算性，标记有向图。1介绍动力系统理论是数学的一部分，在工程和科学中有许多应用[9]。考虑一类拓扑动力系统，即只研究拓扑方面，而不是例如离散性或测度论概念。拓 扑动 力 学 中的 一个主要问题如下。给定两个动力系统（M，f）和（N，g），其中M，N是紧拓扑空间，f：M→M，g：N→N是连续映射，它们之间是否存在拓扑共轭f=g交换的同胚？换句话说，从拓扑的观点来看，（M，f）和（N，g1电子邮件：christoph. unibw.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.08.011132C. Spandl/理论计算机科学电子笔记167（2007）131Adler，Konheim和McAndrew [1]引入了拓扑熵，它是拓扑共轭的几个不变量之一。从那时起，拓扑熵成为根据共轭性对具体动力系统进行分类的有用工具。后来，Dinaburg和Bowen利用度量空间给出了一个新的定义。事实证明，如果拓扑是由度量生成的，那么这两个定义是一致的。在移位动力系统（简称移位）的情况下，拓扑熵可以用一个简单的公式表示。移位是紧度量空间X和一致连续双射映射σ：X→X的对（X，σ），其中X是某个（有限）字母表上所有双无限序列的闭子集，σ是通常的左移位映射。位移以自然的方式出现在任何拓扑动力系统（M，f）中，其中f是双射[2]。考虑任何有限划分{P i：i= 0，.，n}，则存在一个映射M：M→ {0，...，n}定义为x∈P <$（x），对所有x∈M。 因此，映射M：M→ {0，...，n}Z是通过对所有i ∈ Z，x ∈ M设f（x）= y：f i（x）=yi得到的.这个赋值是转移动力系统的一个环节，因为σf=σf成立。另一方面，符号动力学，拓扑动力系统理论中与移位有关的部分，是数学中与自动机理论、语言理论和编码理论有许多应用的独立部分[12，10，14]。移位（X，σ）的拓扑熵h（X）由h（X）= limlogR（n）给出n→∞n其中R（n）是出现在以下元素中的长度为n的不同单词的数量：X.由于非负矩阵的Perron-Frobenius理论，拓扑熵的计算对于广泛的一类移位是可能的。因此，问题是计算是否有效。在计算（一般）动力系统的熵方面有过几次尝试，见[13]一个简短的调查。在[16]中，还考察了位移的拓扑熵的可计算性。第8节讨论了与本工作的相似性和差异。下面介绍的工作是基于Type-2可计算性理论[17]。首先，几个定义和特征的移位空间进行检查。然后，相应的命名系统进行比较使用的概念，减少。最后，如果这些命名系统是适当的拓扑熵的可计算性方面的问题本文概述如下。 在下一节中，给出了一些基本的符号。第三节给出了移位空间的不同特征。下面的第4节涉及相应的命名系统及其等效性。在第5节中，Perron-Frobenius理论是预C. Spandl/理论计算机科学电子笔记167（2007）131133它建立了计算熵的数学基础最后，在第6节中，重点讨论了主要问题：有效地计算拓扑熵。在下面的第7节中，将研究一类特殊的移位第8章是专门讨论的。2符号设A是一个字母表，即一个非空的有限集合。在下面，只有alpha-bets，|一|考虑≥ 2，字母设置为0，1，...，n与n=|一|-1。则Aω表示A上所有有限字的集合，Aω表示A上所有无限序列的集合，即Aω={f：f：N→ A}。 A上所有双无限序列的集合记为AZ。空字用λ表示。 对于每一个w∈A，|W|表示w的长度。 级联A的u和v表示为uv。设r，u，v，w∈ A_∞且w=ruv.则r称为w的前缀，用符号r±w表示，u称为子字的w，以符号u a w表示。此外，u<$w表示u±w，u/=w。对于任意的词w∈ A∈N且i，j∈ N，w[i，j]：= w i.. w n是w的子字，其中n = min（j，|W|（1）如果i≤j且i<|W|，否则w[i，j]：= λ。若p∈ Aω且i，j∈N，则p[i，j]∈ Aω表示词p[i，j]= pipi+1. 当i≤j时为p j，当i > j时为p[i，j]=λ。部分函数用f：X→Y表示，全函数用f：X→Y表示。一个（部分）函数f：<$Z1×···×Zk→Z0，其中Z0，Z1. Zk∈ {A∈，Aω}称为可计算的，如果它是可由2型图灵机计算的.这里使用的所有关于类型2可计算性的概念都是在[17]的意义根据[17]，有效拓扑空间是一个三元组S=（X，β，ν），其中X是一个拓扑空间，拓扑由可数集β<$2X作为子基定义，ν：<$A<$→β是β的一个记法。此外设X是T0-空间，即对任意x，y∈X，当{B∈β：x∈B}={B∈β：y∈B}，则x=y成立。 有效拓扑空间S=（X，β，ν）的标准表示δ：<$Aω→X定义为：δ（p）=x：惠{B∈β：x∈B}={ν（u）：ι（u）ap}且ι（w）ap<$w∈dom（ν），其中x∈X，p∈ Aω.否则设置δ（p）↑。这里，函数i：A→A定义为i（a1. a n）：= 110 a1 0. 0an 011 for alln∈ N and all wordsa1. a n∈ An。3偏移表征本文介绍的方法改编自[12，3]。设A是阿尔法赌注.考虑AZ是赋积134C. Spandl/理论计算机科学电子笔记167（2007）131FA上的离散拓扑的拓扑则移位映射σ：AZ→AZ，定义为σ（x）i=xi+1是同胚映射。如果X<$AZ具有1. X关闭，2. X是平移不变的，也就是说，σ（X）=X成立，则称X为移位空间，称（X，σ）对为移位动力系统或简称移位。移位空间X还有其他等价的刻画。首先是通过词语的集合来定义。 考虑一个子集F <$A <$。 然后定义一个集合XAZ如下方式：从AZ开始，删除所有具有在F中的子字。则XF是闭的且移位不变的，因此是移位空间。集合F称为移位空间XF的禁用字集合。另一方面，对于任何移位空间X，存在子集F<$A<$使得X=XF。因此，禁止词的集合唯一地确定移位空间。反之则不成立。一个集合S<$A<$称为阶乘，如果对于任意的词u∈S，u的每个子词也在S中。一个集合S<$A<$称为可扩的，如果对于任意的词u∈S，存在非空词v，w∈ A+使得vuw∈S成立。集合L <$A <$A <$A中的所有词是X中元素的子词，称为X的语言。那么L是阶乘的，是可扩的。另一方面，若L <$A<$是阶乘可扩的，则存在唯一确定的移位空间，其语言为L移位空间X的语言记为A（X）。也有通过有限或可数有向图的特征。有向图或有向图Γ是一对（V，E），其中V和E是不相交的、有限的或可数的集合，以及两个映射i：E→V和t：E→V。V称为顶点集，E称为边集。映射i和t给每条边e∈E分配一对顶点（α，β），其中e从顶点i（e）=α开始，到顶点t（e）=β结束。 (In在文献中，一些作者称有向图为“有向多重图”。一个有向图Γ称为不可约的，如果给定两个顶点α，β∈V，在Γ中有一条路连接它们（在文献中也使用“强连通”的表达）。一个有向图Γ称为本原图，如果给定两个顶点α，β∈V，存在N∈N，使得对任意n≥N，在Γ中有一条长为n的路连通α和β。本原有向图也是不可约的。最后，标号有向图是一对（Γ，λ），其中Γ是一个边集为E的有向图，λ：E→ A称为标号，是一个映射，它给Γ的每条边e分配一个字母表中的元素A.设EZ（Γ）∈EZ是Γ中所有双无限路的集合。 则存在一个函数Φ：EZ（Γ）→ AZ，它给每条路径γ∈EZ（Γ）分配对应于路径γ的双无限标号序列。即如果γ=（ei）i∈Z，则Φ（γ）=（ε（ei））i∈Z. 此外，函数Φ是一致连续的，C. Spandl/理论计算机科学电子笔记167（2007）131135移位不变，即σ<$Φ = Φ<$σ成立。集合Φ（EZ（Γ）），将被表示为AZ（Γ），是移位不变的，但不需要是闭的。则闭包AZ（Γ）是移位空间X。因此，任何标号有向图（Γ，）都以唯一的方式确定移位空间X=Φ（EZ（Γ））。为了简单起见，下面只考虑没有搁浅顶点和没有多重标记的标记有向图。 这里，对于有向图Γ，一个顶点α被称为搁浅的，如果存在在r中没有一条双无限路径有一条边e，i（e）=α。 多重标记有向标号图（Γ，ε）的存在性意味着存在两条不同的边e，g∈E，例如，其中i（e）=i（g），t（e）=t（g），并且t（e）=t（g），即e和g具有相同的初始顶点、终止顶点和标签。一个无阶顶点且无重标号的标号有向图（Γ，ω）称为移位空间X= Φ（EZ（Γ））的覆盖任何移位空间都有一个封面。一个可数标号有向图直接暗示了在某个可数字母表上的移位动力系统的定义设B是一个可数集合，称为可数字母表。BZ是一个可度量化空间，它具有B上离散拓扑的乘积拓扑. 移位映射σ：BZ→BZ在BZ上是一致连续的.如果Y<$BZ是闭的且移位不变的，则Y称为（可数的）移位空间，（Y，σ）称为移位。注意，Y不一定是紧的。有限或可数有向图Γ的集合EZ相应的位移称为有向图Γ的边位移最后是一些关于转移的定义。设X是具有有限覆盖的移位空间。所以X称为移位。如果X是一个移位空间，拥有一个有限的禁用词集，那么X被称为有限类型的移位。任何有限类型的移位都是如此，但反之则不成立。 设X是具有可数覆盖的移位空间，其中对应的有向图是不可约的。所以X称为编码系统[5]。 一个移位X称为拓扑传递的，如果对于任何对词u，v∈ A（X），存在一个词w∈ A（X）使得uwv∈ A（X）成立。因此，如果X有一个不可约覆盖，则X在拓扑上可传递的然而，反过来说，不是每个拓扑传递移位的覆盖都需要是不可约的。一个移位空间称为拓扑混合的，如果对于任意一对字u，v∈A∈（X），存在一个N∈N使得对于所有n≥N存在一个长度为n的字w∈ A（X），使得uwv∈ A（X）成立。任何拓扑混合移位是拓扑传递的，反之则不是。稍等如果X有本原覆盖，则X是拓扑混合的。最后，移位空间X的同步字是一个字w∈ A（X），使得对于任何u，v∈ A（X），如果uw∈ A（X）且wv∈ A（X），则uwv∈ A（X）也成立。这里有一些例子来说明上面的定义。字母A={0， 1}是二进制字母表。136C. Spandl/理论计算机科学电子笔记167（2007）131例3.1首先考虑以下有限型X<${0， 1}Z的移位。1. X由禁止词集合F：={ 01}定义，该集合恰好有一个元素。然后X读X={σ i（x）：i∈ Z}<${0 Z，1 Z}其中x∈ {0，1}Z由x：=.定义。十一岁00... .根据定义，没有词w∈ A（X）使得0w 1∈ A（X）成立。因此X不是拓扑传递的。此外，00是X的同步字。2. X由禁用词集合F：={ 00， 11}定义。然后X读取X={（01） Z，（10） Z}。X是拓扑传递的，因为对于任意一对允许字u，v∈ A（X），uv，u0v或u1v都是允许字。但X显然不是拓扑混合的。最后，01是同步字养木3. 黄金均值偏移X由禁用词集合F：={ 00}定义。设u，v∈ A∈（X），则u1nv∈ A∈（X）对所有n≥1成立.因此X是拓扑混合的。字1是X的同步字。例3.2由禁用词集F：={ 102n+1 1：n∈N}定义的偶数移位X<${0， 1}Z是有限类型的但不是有限类型的。图1中给出了相应的盖。如果X是有限类型的，则存在一个表征X的禁用词的有限集合FJ。因此，将存在M∈N使得FJ中的所有字的长度都≤M+1。由于102M+1和02M+1 1若X是允许字，则102M+1 1∈ A（X）成立（见[12]中定理2.1.8）。但这是一个矛盾。010Fig. 1. 偶数班的封面。最后是一个字母表A={ 0， 1， 2}的例子。例3.3上下文自由移位X<${0， 1， 2}Z定义如下。考虑集合LJ<${0，1， 2}，定义为LJ：={ 0n 1n 2：n≥1}。则X的语言L定义为L：={u∈ A<$：u是某个v∈ LJ<$的子字}。那么X是一个编码系统，但不是这样。图2给出了相应的无限覆盖。如果X是这样的，则子集S：={ 0n 1n：n≥1}，{0， 1}从形式语言理论的角度来看，它是一种正则语言。但这是不正确的，这可以证明与泵引理。注意0Z∈X，但0Z不是有向图中任何路的标号序列。C. Spandl/理论计算机科学电子笔记167（2007）131137n<><<>......图二.封面的上下文自由转移。4移位空间设某个有限的字母表A考虑A上的移位空间X，赋以乘积拓扑。设A（X）表示X的语言，An（X）表示A（X）中长度为n的词.此外，不失一般性，让字母A被选择为使得A1（X）=A。X是可度量化拓扑空间，其中拓扑的基由柱集[w] X：={x ∈X：xn+i=wi，0≤i<|W|}对任意的w∈ A∈（X），n∈ Z. 接下来考虑A上所有移位空间的集合，Xσ：={X<$AZ：X是闭的且σ（X）=X}。定义有效拓扑空间（类似于中的定义5.1.1）[17]）Sσ：=（Xσ，βσ，νσ）和Sσ：=（Xσ，βσ，νσ），其中Xσ上的拓扑<<<联系我们由βσ<$2X生成（βσ<$2X分别）作为底基层，路上了 记法νσ：A→βσ和νσ：A→βσ定义为：<<>> >νσ（w，ν−1（n））：={X∈Xσ：[w]AZ<$X/=<$}Zn对所有的w∈ A∈Z和n∈Z.这里，νZ：A→Z是整数的一些双射标准符号。现在考虑相关的标准表示δσ：<$Aω→XσSσ的δσ：<$Aω→Sσ的Xσ和δσ：=δσ<$δσ。事实证明<>>>前两个表示等价于语言和移位空间的最大禁止词集。设EnL：<$Aω→Xσ由EnL（p）=X：惠{w∈ A<$：i（w）ap}=A<$（X）给出.类似地，令EnF：<$Aω→Xσ由EnF（p）=X：惠{w∈ A<$：i（w）a p}=A<$\A<$（X）给出。那么以下情况成立。定理4.1标准表示δσ等价于EnL且δσ为相当于F。证据 首先显示δσEnL. 设p∈dom（δσ）已知，X：=δσ（p）.<<<然后，通过δσ的定义，{A∈βσ：X∈A}={νσ（w，ν−1（n））：ι（w，ν−1（n））a<<另一方面，通过X语言的定义和移位不变性，[w]AZ<$X/=<$$>w∈A<$（X）aswellasw∈A<$（X）<$$>n∈Z[w]AZ<$X<$n n保持。 最后，对于所有的n∈ Z，i（n，v-1（n）n）a p惠w∈ A∈A（X）. 现在很容易看出有可计算的翻译函数f1，f2：<$Aω→ Aω，其中EnL（p1）=δσ<$f1（p1）和δσ（p2）= EnL<$f2（p2），<<所有p1∈dom（EnL），p2∈dom（δσ）.类似地示出了断言δσ<$EnFQ其直接后果是：推论4.2等价性δ σ<$En L<$En F成立。代替使用标准表示，可以使用容许结果表明，对于计算移位空间X的拓扑熵，基于覆盖的命名系统优于EnL。设（Γ，Γ）是一个有限标号有向图，没有链点，也没有多重标号.则（Γ，λ）可以用词的有限集合G <$A<$来表示，其中<$ui，ut，a<$∈Gi <$（ui，ut）∈ A<$× A<$表示边，a∈ A表示相应的标号。 所以，一个名为（Γ，）的词u∈A∈G，其中i（w）aui∈ G.由于（Γ，）没有链顶点，也没有多重标号，因此（Γ，）也是唯一确定的移位空间的覆盖X.因此，u也被称为X的名字。具有名称的移位空间正好是sofic移位Xσ，s。现在定义X σ，s的符号νG：<$A<$→Xσ，s，称为图符号νG（u）=X i<${w：i（w）a u}=G，其中G是X的覆盖。设X是A上的任意移位空间。则存在X的可数覆盖（Γ，）。因此，（Γ，）可以用可数集合G <$A<$来表示。所有移位空间的表示EnG：<$Aω→Xσ结果是EnG等价于EnL。命题4.3设En G：<$Aω→X σ为图表示，En L：<$Aω→X σ为X σ的语言枚举表示，则En G<$En L成立.证据首先显示EnG≤ EnL。设M是一台Type-2机器，做以下事情。考虑一个英文名p作为M的输入.则M在步骤n≥1中工作。每一步都从构造相应的通过读取长度为n的p的前缀来标记有向图。然后在每个顶点遍历整个子图，记录长度≤n之后，下一步开始。由于覆盖没有搁浅顶点，移位空间语言中的所有单词都被写入输出磁带。C. Spandl/理论计算机科学电子笔记167（2007）131139第二个证明EnL≤ EnG。还有一个Type-2机器N在作为输入的EnL-namep上做相反的工作。N也在步骤n≥1中起作用。每一步都从确定p中列出的X语言的第n个词u∈ A（X）开始。在每个步骤的第二部分中，构造子图。在每一步，有向图Γ由有限个彼此不相连每一个链都由在前面的步骤中已经读取的一些单词标记如果u是某个词的子词，它是一个链的标签，那么转到步骤n+ 1。否则，对于所有标签为单词v的链，使得u=w1vw2成立，其中w1，w2∈ A+，在两个方向上扩展链，使得新链被u标记。如果根本不存在这样的链，则构造一个新的由u标记的链。然后将构造的扩展或构造的新链分别写入输出磁带，并继续下一步。通过构造，语言中的每个词都是有向图中某条有限路径的标签，任何链都可以在两个方向上延伸到无限。 因此，在Γ中的所有双无限路标号的集合是在X. 因此，N计算X的EnG-name。Q最后转向有限型移位集Xσ，f。然后有一个符号νF：Aσ→Xσ，f的Xσ，f，称为禁止词符号。它的定义是：νF（u）=X i{w：i（w）a u}=F，其中F是X的禁用字的有限集合。以下建议是有用的。命题4.4存在一个可计算函数χL：A×A→{0，1}使得对于a lu，w∈A，χL（u，w）=1iw∈A（νF（u））.为了证明，需要邻接矩阵的概念。因此，在第5.1小节中给出了证明，该小节将解释这一概念命题4.5设νG：A <$A <$→Xσ，s为图记法，νF：A<$→X σ，f是禁止词符号，则ν F≤ νG成立.证据 必须证明存在一个可计算函数f：A→ A使得对于所有的u ∈ A，表示某个移位空间X ∈ X σ的禁用字F的有限集合，f，f（u）∈ dom（νG）成立，并且f（u）表示X的一个覆盖的有限标号有向图。盖可以按以下方式构造。如果F是空的，则X=AZ，相应的覆盖由一个顶点α和|一|从α开始到α结束的边用完整的字母表标记。另外，F中存在某个最大长度M≥1的禁用字.如果M=1，则X=（A\F）Z，并且对应的覆盖是上面覆盖的子覆盖。特别地，如果F=A，则X=λ且f（u）=λ。设M≥2。 则顶点集由AM−1（X）给出。 根据命题4.4，AM−1（X）和AM（X）可以一致有效地列出，140C. Spandl/理论计算机科学电子笔记167（2007）131G给定一个νF的名字X。现在对u1，u2∈ AM−1（X），（u1，u2）是标号有向图i的边，其中对某些a，b∈ A和u∈ AM−2，以及aub∈ AM（X），u1=au和u2=ub如果是，则边（u1，u2）标记为b。Q命题4.6存在一个可计算函数f：<$A<$A <$→ A<$，其中dom（f）=ν−1（range（νF））和νG（u）= νF<$f（u）对所有u ∈ dom（f）。证据首先注意，如果X是有限类型的移位，则存在M≥1，使得存在一组禁用字，所有禁用字的长度都为M。考虑以下算法，在阶段n≥1中工作。由于X的覆盖G中没有链点，所以An（X）可以在每个顶点上遍历标号有向图n步而一致有效地列出.现在考虑有限类型Y的移位，其中禁用词的集合为An\An（X）。根据命题4.5构造一个相应的标号有向图GJ.然后根据[12]中的定理3.4.13，X和Y通过比较它们的封面是相同的。如果它们不相同，则继续进行阶段n+ 1，否则将对应于An\ An（X）的νF-名称写入输出并停止。通过算法的构造，很明显，算法停止在阶段Mi，如果X是有限型的，并且X/=AZ，并且如果X=AZ，则停止在阶段1。因此，上面概述的算法计算f。Q注：根据文献[12]中定理3.4.17和3.4.14 ，存在可计算函数χf：<$A→{ 0， 1}使得u∈dom（χf），如果u是拓扑传递移位X的覆盖名，且χf（u）= 1 i <$X是有限型移位.5邻接矩阵与熵设（r，r）是一个标号有向图（可数或有限），V是r的顶点集。（Γ，β）的邻接矩阵A=（Aαβ）（α，β）∈V2具有非负元素的定义如下。设α，β∈V，则Aαβ∈N是从顶点α开始到顶点β结束的边数。有限字母表A上的移位动力系统（X，σ）的拓扑熵h（X）定义为：h（X）：= limn→∞日志|An（X）|n（一）如果X1 = 0且h（0）：= 0。 拓扑熵是在给定长度下出现的单词数量的“增长率”。注意，熵由0 ≤ h（X）≤ log限定|一|. 注意极限总是存在的（[12]中的命题4.1.8）。C. Spandl/理论计算机科学电子笔记167（2007）131141不5.1有限的情况在本小节中，考虑有限邻接矩阵。因此，相关的变化是如此的准确。下面的命题很容易理解。命题5.1存在可计算函数dim G：<$A<$N → N和AG：<$A<$×N2→ N，其中dim G（u）=n，AG（u，i，j）= Aij，对任意u∈ dom（νG），i，j∈ {1，.，n}，其中A是以u命名的标号有向图的n × n邻接矩阵。现在介绍一些关于有限邻接矩阵和Perron-Frobenius理论的基本事实参考文献[7，15]。有限邻接矩阵A称为可约的，如果存在置换矩阵P，使得P APT具有以下形式：⎛ ⎞b0的PAP= 1000CQC这里，B和C是方阵。换句话说，上述形式是通过重新排列原始矩阵的索引而获得的。如果A是不可约的，则称为不可约的。不可约矩阵确实有一个基本性质：如果A是一个n × n不可约矩阵，n≥ 1，则A是一一矩阵（0），或者对于任何一对指数i，j∈ {1，.，n}存在某个l > 0使得（Al）ij> 0成立。注意，一个标号有向图是不可约的，那么它对应的邻接矩阵也是不可约的.一个不可约矩阵称为本原矩阵，如果对任意一对指数i，j∈ {1，.，n}存在某个N∈ N使得（Al）ij> 0对所有l≥N成立.注意，有向标号有向图是本原的，则其对应的邻接矩阵是本原的。任何有限邻接矩阵A都有一个标准形式：存在一个置换矩阵P，使得PAPT具有以下形式：⎛ ⎞10...00 ...0⎟⎜ ⎟100A2.00 ...0⎟⎜ ⎟⎜ ⎟我...... ......这是什么？......这是什么？...... .. .⎟⎜ ⎟P APT=0.001100... 一个g...0⎟⎜ ⎟⎜ ⎟你好∗一个g+10⎟⎜ ⎟⎜ ⎟我...... ......这是什么？......这是什么？...... .. .⎟⎝ ⎠我...我 ... As142C. Spandl/理论计算机科学电子笔记167（2007）131其中A1，.，A s是不可约方阵，且在每个块行> g中，至少有一个矩阵的块列严格小于块行，该矩阵不是零矩阵。标准形式是唯一的，直到块的排列和每个对角块内的索引。有n！对于不可约的n×n方阵，给出了不同的置换矩阵P。因此，按照[7]中给出的标准形的构造步骤，显然存在一种算法，该算法以矩阵A作为输入来计算标准形。由于命题5.1，下面的定理成立。定理5.2设u∈ dom（νG）是某个有限移位空间的（图）名.设N是以u命名的图的邻接矩阵的标准形（指标集为1，…，n）。以下函数是可计算的。1. irG：α Aβ→N，2. dimG：Δ AΔ×N→ N，3. NG：A → N× N 2→N。这里，irG（u）=s是N的不可约分量的数目，如果i = 0，dim G（u，i）等于n，如果i∈ {1，.，s}。最后，N G（u，i，j）= N ij，对于所有i，j∈{1，.，n}。在来到中心Perron-Frobenius定理的一个词的指数类型的邻接矩阵A=（一个ij）。A的指数i称为瞬时的，如果它对应的（置换的）指数j在标准形式中使得jj形成一一不可约块并且jj=0。一个有限序列（si）1≤i≤m称为一个长度为m≥1的链，如果对所有i=0， .. . . ， m−1。的索引iA称为吸收的，如果从i开始的所有链的长度都有一个上界。那么以下情况成立。引理5.3索引i吸收i，它是瞬时的，所有以i开始的链只有瞬时索引。证据 设i是一个吸收指数，（sk）1≤k≤m是从i开始的长为m的链.则对于所有k∈ {1，.，m}。假设不是这样。 然后有一个l∈ {1，...，m}，使得S1不是瞬态的。因此，SL属于一个不可约块的规范形式，至少有一个严格的积极的项目。因此，存在从sl开始的任何长度的链。 但那样的话，我就不会吸收了。另一方面，让i是瞬态的，所有从i开始的链都只有瞬态索引。 设（sk）1≤k≤m是从i开始的长度为m的链。 然后i=s1> s2>···> sm成立。只有少数的不同。从i开始的链。因此，i是吸收的。QC. Spandl/理论计算机科学电子笔记167（2007）131143结合到目前为止的结果，可以得出以下结论。命题5.4存在一种算法来决定邻接矩阵A中的索引是否均匀吸收。证据 由定理5.2和上面的引理直接导出。Q现在可以给出命题4.4的证明命题4.4的证明 设u ∈ A，F是X：=vF的禁忌词（u）对应于u。如果F为空，则X=AZ且对任意的w∈ A∈ L，χL（u，w）=1.如果F不为空，则存在M≥1使得M是F中所有元素的最大长度。 如果M= 1，则X=（A \ F）Z和χ（u，w）= 1 i <$ff中没有符号a是w的子字。最后考虑M≥2的情况。 设置N：=|一|M. 令ν：{1，.，N} → AM是AM的字典序。考虑由aij：= 1定义的N×N邻接矩阵A=（aij），如果ν（i）[1，M−1]=ν（j）[0，M−2]，并且没有词w∈ F是ν（i）或ν（j）的子词。否则设置ij：= 0。 很明显，存在一个算法在u中一致地构造A。现在考虑某个词w∈ AM。则w∈AM（X）i <$w不是A和AT的吸收指数.只有在这种情况下，才存在w向右和向左的无限扩张。接下来设w∈ A∈。 如果|W|0使得（Al）ij>0成立. 一个不可约矩阵A称为本原矩阵，如果对任意一对指数i，j∈N，存在某个N∈N使得（Al）ij>0对所有l≥N成立.因此一个可数的标号有向图是不可约的（本原的），如果相应的邻接矩阵是不可约的（本原的）。”[15]这是一个比喻。1不可约非负矩阵A，lim supern→∞（An）n存在，是积极的，1不依赖于索引i。 设置λ：= lim supn→∞（A n）n.如果A是有限的，则λ与Perron值相同。 因此，λ被称为Perron值，即使在A是可数的。设（Γ，λ）是可数的不可约标号有向图，A是不可约邻接矩阵，λ是相应的Perron值.则hτ（BZ（Γ））= logλ成立（[10]，命题7.2.6和[12]，第13.9节）。6计算拓扑熵移位（X，σ）的拓扑熵的计算是通过具有增加行数的有限邻接矩阵的序列来完成的。因此，下面的基本定理是计算的基础定理6.1函数hs：X σ，s→ R赋予每个移位X其拓扑熵是（νG，ρ）-可计算的。证据 首先考虑A是行n ≥ 1的不可约有限邻接矩阵的情况。 如果n= 1，即A=（a），则Perron值为a。设n≥2。根据[7]中Perron-Frobenius定理的证明，可以导出计算Perron值的算法。设Sn <$Rn是由Sn={x∈Rn：||X||= 1}。 定义一个函数r：Sn→R，r（x）：=min（A（E+A）n−1abs（x））in−11≤i≤n （（E+A）abs（x））i其中函数abs： Rn→ Rn取每个分量的绝对值，即abs（x1，.，x n）=（|X1|，...、|X n|）. r是连续的，Sn是紧的，所以存在maxr（ Sn）.λ=maxr（Sn）是A的Perron值.函数r是（[ρ] n，ρ）-可计算的。在[17]定义5.2.1的意义下，n-球面Sn也是可计算紧集。 因此，r（Sn）也是可计算紧集。最后，由于R的可计算紧子集的最大值是可计算的（[17]中的引理5.2.6），Perron值λ也是ρ-可计算的。很明显，存在一种算法，146C. Spandl/理论计算机科学电子笔记167（2007）131n在给定邻接矩阵u∈dom（νG）的条件下，统一计算Perron值设A是有限移位空间X的右分解覆盖的任意有限邻接矩阵。前面已经提到过，有一种算法可以计算A的标准形。因此，可以计算每个不可约分量的Perron值λi。由于极大值函数和对数是可计算的，因此h（X）= logmaxλi也是可计算的（在A中一致）。定理5.2最终保证hs是（νG，ρ）-可计算的。Q命题4.5直接包含了推论：推论6.2函数h f：X σ ， f→ R赋给有限型X的每一移位其拓扑熵是（νF，ρ）-可计算的。现在转到任意移位空间X。X将由EnF的名称p∈ Aω表示。 则任何长度为n∈N的p的前缀un∈ An表示有限型移位eYn是X的扩张：X<$Yn对所有n∈N。此外，X=nYn成立。定理6.3函数h：X σ→ R赋给每个移位X的拓扑熵是（En F，ρ>）-可计算的.证据设p∈dom（EnF）已知，X：= EnF（p）. 对于所有n∈N，用p的前缀定义一个长度为n的词u n，unиp。 设Yn：=νF（un）。 Yn是有限型移位，X<$Yn。根据拓扑的定义，我们可以立即看出Yn的拓扑熵序列（h（Yn））n是一个有界的递减实数序列。 因此，存在limn→∞h（Yn 进一步地，对于所有n∈N和X=nYn，Yn+1<$Yn保持。对于任何n∈ N，|An（Y m+1）| ≤ |An（Y m）|对所有m∈ N成立，并且lim m→∞|An（Y m）|为|An（X）|. 因此，对于所有的n>0，有N，M∈N，对于n≥N，m≥M|h（X）−l og|An（Ym）||<手握着。Limn→∞ h（Yn）=h（X）紧接着。由（h（Yn））n是递减的这一事实，推论6.2得出该断言。Q定理6.4函数h：X σ→ R赋给每个移位X的拓扑熵不是（En L<$En F，ρ）-可计算的。证据根据定理6.3，它表明h不是（EnL<$ EnF，ρ<）-可计算的。假设不是这样。然后有一个Type-2机器M进行计算。现在设p∈ Aω是某个编码的EnL<$EnF-名，系统X具有严格正的拓扑熵h（X）>0。然后存在某个T∈N，使得在输入p上计算M的T步之后，M具有表示有理数r的字作为输出，其中0

下载后可阅读完整内容，剩余1页未读，立即下载