卵石自动机的层次结构和理论教学

可在www.sciencedirect.com在线获取理论计算机科学电子笔记339（2018）99-110www.elsevier.com/locate/entcs写作的力量，一个卵石层次和自动机理论教学的叙述CarolinaMej 'ıa1，2ProyectoCurricularMatem'aticasUniversidadDistritalFranciscoJos'edeCaldasBogot'a，哥伦比亚J. Andres Montoya，Christian NolascoDep artamentodeMatem'aticas国立大学Bogot'a，哥伦比亚摘要在这项工作中，我们研究卵石自动机。这些自动机构成了离散计算模型的无限层次。层次结构开始于有限状态自动机（0-pebble自动机）的水平，并接近于单带图灵机的模型。 因此，可以说，它是一个完整的层次结构，涵盖，以一种连续的方式，所有在计算理论中很重要的自动机模型。我们调查使用这种层次结构作为自动机理论教学的叙事。我们还调查了一些基本问题的卵石自动机的权力关键词：卵石自动机，有限状态自动机。我们研究一类非经典自动机，我们称之为卵石自动机。卵石自动机是双向有限状态自动机（2DFA），具有最弱的写入能力：在计算过程中使用有限数量的卵石的能力，这些卵石用于标记输入磁带的单元卵石自动机是双向有限状态自动机的非书写扩展，可以分层组织：一个卵石自动机提供了k个卵石，称为k-卵石自动机（k-2DFA）。请注意，pebble层次结构是一个非书写机器的书写能力层次结构零级的自动机是1第一作者要感谢COLCIENCIAS授予的补助金，这使她能够发展她的博士研究。第二作者要感谢哥伦比亚国立大学，这项研究得到了Hermes研究系统的部分支持，项目编号32083。2电子邮件地址：cmejiam@udistrital.edu.co3电子邮件：amontoyaa@unal.edu.co，cnolascos@unal.edu.cohttps://doi.org/10.1016/j.entcs.2018.06.0071571-0661/© 2018作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。100C. Mejía等人/理论计算机科学电子笔记339（2018）99标准2DFA，其具有零卵石，并且根本不写入。第k层的自动机是k-pebble自动机，它可以接近用k个pebble写的能力。层次结构的极限（sup）是什么我们使用术语∞-卵石自动机来表示具有无限数量卵石的卵石自动机。唯一的限制是可以放置在单个像元上的pebble数量是有上限的我们称之为细胞容量。很容易检验∞-pebble自动机是否等价于一带图灵机。因此，卵石层次结构允许我们引入图灵机作为进化过程的左端，该进化过程始于有限状态自动机，并由卵石（书写能力，墨水滴）的添加驱动。 它表明，研究的层次结构可以作为轴的叙事自动机理论和其他离散模型的计算教学。 我们深入讨论这个话题：这是我们为自动机的非经典模型提出的第一个应用人们自然会问：等级制度是否严格？如果是这样的话，我们从2DFA到图灵机的进化过程可以分解为无限系列的离散和自然步骤。然后，可以得出结论，我们正在处理一个强大的结构，可以用于图灵机和其他离散计算模型另一方面，如果层次是有限的，我们会有类似相变发生在某个k。最后一种可能性似乎不大。应该说，在这一点上，层次结构是严格的，并且在这项工作之前就已经知道了。我们提出了一个新的证明这一事实，我们使用这个证明来解决一些进一步的问题卵石自动机和它们与其他模型的自动机。工作安排和贡献。 这项工作分为三个部分。在第1节中，我们介绍了卵石自动机的模型，以及一些基本问题，沿纸调查。在这一节中，我们证明了卵石自动机的普遍性的一个弱形式，我们收集了一些简单的事实，使我们能够证明卵石层次结构是严格的。在第二节中，我们研究了这种语言类的层次结构与其他一些有趣的形式语言类之间的关系。我们表明，存在确定性上下文无关的语言，不包括在层次结构中，我们介绍了卵石类的非确定性版本。我们可以给出满意的答案的一些基本问题之间的关系确定性和非确定性的类。在第3节中，我们包括一些结论性的评论，其中大部分1Pebble自动机：书写能力k-pebble自动机是具有k个不可区分pebble的2DFA这些自动机可以使用鹅卵石作为标记：鹅卵石可以放置，感知和举起。C. Mejía等人/理论计算机科学电子笔记339（2018）99101P P定义1.1设k≥1，k-卵石自动机是一个元组M=（Q，q0，A，H，n，δ）使得：(i) Q是内部状态的有限集合(ii) q0∈Q是初始状态。(iii) HQ是停止状态的集合。(iv) 一个可接受状态是接受状态的集合。(v) 是有限输入字母表。(vi) δ是过渡函数，它是集合Q×Ω×的部分函数{0，.， k}× {0，.， k}到集合Q × {0，.， k}× {0，.， k}× {←，o，→}。 让（q，a，r，s）∈ Q× n×{0，.， k}×{0，.， k}，元组（q，a，r，s）编码M的配置，该配置由下式给出：内部状态是状态q，被扫描的单元格被填上字母a，一堆r个鹅卵石放在这个单元格上，自动机M的袋子里装着s个然后，它遵循，如果（q，a，r，s）∈dom（δ），不等式r+s≤k必须保持。此外，如果δ（q，a，r，s）=（p，n，m，d），则M将其内部状态从q改变到p，它在扫描单元上留下n个pebbles，保持m个pebbles。它的袋子（等式r+s=n+m≤k必须成立），并在d所示的方向上移动（符号o迫使工作头停留在同一个单元）。请注意，卵石自动机是准书写机器。 因此，它可以使如果我们允许工作头访问输入带的空单元，则会产生很大的差异。 不能访问空单元的卵石自动机被称为标准的，而允许使用所有这些单元的卵石自动机被称为无限制的。我们想研究卵石自动机作为语言接受者的能力因此，我们定义了以下几类形式语言定义1.2设L是语言，我们有L∈ Pk，当且仅当，语言L可以用标准的k-pebble自动机来识别。我们用符号来表示集合i。 标准卵石可以很容易地i∈N由确定性线性有界自动机（DLBA）模拟：卵石自动机的单元内容，这是由一堆卵石和一个输入字母构成的对，可以适当地编码成线性自动机的工作字母表 它也可以检查，如果P NP，后面的遏制是严格的：集合P包含在ptime中，而SAT问题可以用确定性线性有界自动机求解。因此，如果DCSL表示由所有确定性上下文敏感语言构成的集合，则包含P ≠ DCSL成立，并且如果P/=NP，则后面的包含是严格的。设M是一个无限制的卵石自动机。我们注意到自动机M可以用它的鹅卵石来模拟计数器因此，4-pebble无限制自动机可以模拟四个计数器，因此它们可以模拟两个下推堆栈[5]。回想一下，具有两个下推堆栈的自动机类构成了计算的通用模型我们感兴趣的模型102C. Mejía等人/理论计算机科学电子笔记339（2018）99p1 01 01：i，j≥0自动机比图灵机弱得多。因此，我们把我们的注意力集中在类标准卵石自动机。从现在开始，我们使用术语卵石自动机来指代标准卵石自动机的更多限制性概念。如果我们放弃有限性约束，自动机提供了无限数量的鹅卵石？我们称之为∞-pebble automata到双向自动机，提供了无限数量的鹅卵石。我们对这些自动机的唯一限制是，给定一个∞-卵石自动机M，存在k（M的卵石容量）使得没有可以在同一单元上堆叠多于K个卵石。很容易检验这种新的自动机模型的标准版本是否等价于确定性线性有界自动机模型。也很容易检验无限制版本是否等价于单磁带图灵机模型。因此，从2DFA开始，一颗一颗地，我们到达了一个通用的计算模型。我们认为它具有巨大的教学潜力，这种教学潜力大部分依赖于以下事实：从一个自然且易于描述的计算模型开始，我们可以部署一个自动机的层次结构，它接近（并收敛于）一个通用的计算模型。此外，两个连续的层次之间的过渡是以一种自然的方式，通过增加一个书写能力（鹅卵石）。重要的是要强调，该结构的教学潜力不能被简化为上述事实。计算机科学的一些基本现象（思想）开始在最低层次出现。理论计算机科学的大多数基本问题也是在人们认真思考卵石层次结构的最低层时出现的让我们检查一些与第一层次相关的简单事实。我们知道P0是正则语言的集合.Blum-Hewitt定理意味着P1=P0[1]。广场的语言，{ww：w∈{0， 1}}，可以很容易地用两个pebble来识别，因此两个pebble就足以识别一些与上下文无关的语言。集合{1 ：p是素数}，可以用三块鹅卵石来识别用四块鹅卵石就能认出，i j ij，这意味着四个卵石可以计算出一般的指数函数是的。更复杂的集合可以通过添加一些鹅卵石来识别。关于卵石自动机的一个重要事实是，这些自动机是可编程机器的一个简单模型（不像2DFA）。请注意，、C. Mejía等人/理论计算机科学电子笔记339（2018）99103搜索转换表的能力接近于搜索与给定模式匹配的子串的能力Pebble自动机非常适合模式匹配任务。当模拟一个转换表时，一点写的能力可能是必要的，但是碰巧卵石自动机可以使用它们的一些卵石来写短字符串。因此，卵石自动机似乎可以利用它们的标记能力来搜索和模拟转换表。我们有以下定理。定理1.3给定n，k ≥ 1，存在N ∈ O（k + log（n）），存在一个N-卵石自动机Mn，k使得任何至多n个状态的k-卵石自动机都能被Mn，k模拟。证据设k，n≥1，对任意N∈O（k+ log（n）），采用统一图灵机的标准构造不难构造出一个N-卵石自动机Mn，k，它能被编程来模拟任意至多n个状态的k设M是一个具有n个状态的k-pebble自动机，w是M的一个输入.我们可以假设M的状态集合是集合{1，...，n}。自动机Mn，k使用k个pebbles来模拟M的k个pebbles，它使用O（1）个pebbles来搜索作为输入的一部分编码的M的转换表，并且它使用O（log（n））个pebbles来跟踪M的状态。后一项任务是通过以下方式完成的：自动机Mn，k使用O（log（n））pebbles来写下M的实际状态的二进制代码，所使用的工作空间是其输入带的第一个O（log（n 编码相当简单：占用的单元格等于1，空单元格等于0。Q注意，如果N是一个n状态的2DFA，那么N最多可以执行n个程序：每个程序对应选择一个状态作为初始状态。另一方面，自动机Mn，k可以运行无限数量的程序：注意，在上述定理的陈述中，没有与可以由Mn，k模拟的自动机的字母大小有关的限制。后面这个事实清楚地意味着Mn，k可以模拟无限多个卵石自动机。因此，我们可以得出结论，普遍性（自我参照）现象开始出现在我们等级制度的最低层次。然而，普适性并不是在层次结构的某些层次上实现的，它是在极限上实现的（就像在集合理论强迫中一样[4]）。我们想让读者相信卵石自动机的巨大教学潜力。因此，指出一些复杂的问题解决（编程）策略可以在pebble层次结构的最低层实现变得很重要。我们将在下一小节详细说明这一点。1.1与回文回文语言，也就是=. w∈{0， 1}<$：w=wR<$，104C. Mejía等人/理论计算机科学电子笔记339（2018）99Mn3在形式语言理论中起着非常重要的作用[8]。请注意，识别回文的能力接近于搜索转换表所需的能力。我们知道，它是一种非正则语言，不能用一块鹅卵石来识别。使用两个鹅卵石和一个简单的锯齿形策略可以很容易地检查出是否可以识别出pebble。设i≥1，设i为语言{w1···w i：|w1|、...、|w i| ≥ 2 &w1，.， w i∈ n}。有多少鹅卵石需要阿玛尼的认可？第一个合理的猜测是，P2i需要i+ 1个卵石。然而，可以检查到，可以用两个鹅卵石识别出P202定理1.4<$2 ∈ P2.证据 我们将描述一个2-pebble自动机，2002年。设w为M的输入字符串。我们假设如下：自动机M对所有i ≤ j有cked，使得w[1，.， i]∈/P al或w[i+1，.， |W|]∈/P al. 我们假设卵石位于单元格1和j +1处。自动机开始交替地移动鹅卵石，左边的鹅卵石被移动100度，右边的鹅卵石被移动100度，通过自动机比较被占用单元格的内容。如果发现不匹配，则它将向相反方向移动pebble，直到左侧pebble到达输入磁带的左端。请注意，右边的鹅卵石已经放在单元格j+1上，并且i t已经在w[1，.. j+1]∈/P al. 然后，将该分组移动到单元j+2。注意，归纳条件被保留了。假设没有发现不匹配，并且两个鹅卵石被放置在相同单元 这意味着w[1，... j+1] ∈ [j +1]。 然后，自动机在相反的方向上交替移动鹅卵石，直到左边的鹅卵石到达输入带的左端。 正确的pebble位于单元格j+1上，现在是检查的时候了如果w [j+2，...，|”属于。|] belongs to Pal. 右pebble移动到单元格j+2，而左pebble移动到单元格j +2。|W|. 然后，采用锯齿形策略来检查 如果w[j+2，...，|] ∈。|] ∈ Pal. 如果最后一次检查是肯定的，自动机停止并接受输入，否则它设法将其中一个鹅卵石放在单元j+3上，另一个放在单元1上。再一次，归纳条件被保留了下来，因此很明显，这样的自动机正确地识别了语言E12。Q需要多少鹅卵石才能识别这种语言？我们可以使用一个运行时间参数来证明两个鹅卵石是不够的。首先，我们观察到卵石自动机是一种特殊类型的限制单带图灵机。碰巧任何一台能识别1003的单磁带图灵机需要时间Ω。n4个。”于是，他就与阿赖耶识结缘。我知道，我们的跑步令i≤j，注意识别语言一个终止的2-pebble自动机的时间是O.C. Mejía等人/理论计算机科学电子笔记339（2018）99105.Σ[|.ΣP ali最多与识别P alj 所 需的 字 节数 一 样大。 因此，我们有，对于所有i≥ 3，语言i不能用两个鹅卵石识别。我们可以证明，三个鹅卵石就足以识别语言 103和104。为此，我们采取了分而治之的策略。定理1.5用三块鹅卵石就能识别语言E13和E14。证据 我们为2004年做了证明。设w为输入字符串。假设一个单独的pebble放在输入磁带上，并且假设它放在单元格i上，称这个pebble为引用pebble。自动机使用剩余的两个pebble来检查w[1，.，i]属于n =2，并且因此，如果检查是肯定的，则它使用相同的两个卵石来检查w [i+1，.，|[2]属于第二类。|] belongs to Pal2. 如果两个检查都是肯定的，自动机停止并接受输入，否则它将引用pebble移动到单元格i+1。 计算从放置在单元格4的参考卵石开始。如果参考卵石到达单元，则计算被拒 绝 |W|-3。Q上面的策略可以很容易地扩展，以证明可以使用log（i）+ 1 pebbles来识别语言i。我们不得不再问一次：有多少鹅卵石需要阿努比斯的认可？4我们感兴趣的是证明当i达到无穷大时，pebble i所需的鹅卵石数量达到无穷大 我们可以尝试一个运行时间的论点，看起来似乎是合理的，注意，一个终止的k-卵石自动机的运行时间是O n k+1。然而，我们需要一个额外的事实来结束这个论点，而碰巧第二个成分不为真：语言Bai是一个上下文无关的语言，给定一个上下文无关的语言L，我们有一个单磁带图灵机，它在时间On6识别L。因此，我们有（从运行时间的角度来看）五个鹅卵石可能足以识别所有这些无限多的权力。不难证明，尽管细节可能很麻烦，上面的分治策略是最优策略，并且对于所有i≥ 2，语言i需要[log（i）]|+1鹅卵石。后一个事实意味着pebble层次结构是严格的。需要强调的是，这一事实在很久以前就被夏和义所证明[6]。他们在证明中使用了一种非统一的语言序列，我们称之为HY序列。在接下来的部分中，我们将证明一些关于pebble层次与其他形式语言类之间关系的事实。为此，我们使用pebble层次结构是无限的。然而，重要的是要强调，这些结果不能从Hsia和Yhe [6]的证明中获得，因为它们的序列具有非均匀性（见下文）。下面几节中提到的所有结果都可以很容易地从以下事实中得到：不存在N，使得所有的幂都可以用N鹅卵石。[4]请注意，这个问题是一个典型的下界问题。因此，可以说，复杂性理论的一些基本问题可以用卵石层次（卵石作为计算资源）以一种自然的方式引入。106C. Mejía等人/理论计算机科学电子笔记339（2018）99PPP∈∈不属于i∈N 派岛HY序列是不均匀的，但序列2Pebble层次及其与其他自动机Hsia和Yhe[6]以及Ritchie和Springsteel[10]介绍了pebble自动机作为可用于识别上下文无关语言（简称CFL）的计算设备，并且其体系结构比下推自动机（PDA）的体系结构更基本这两篇文献似乎是与我们对卵石自动机的研究相关的唯一相关文献大多数关于卵石自动机的文献都与二维自动机和图像识别有关，其中包括Blum和Hewitt的经典文献[1]，其中证明了1-卵石自动机和0-卵石自动机一样强大。一些参考文献涉及树行走自动机和树语言识别的模型（例如参见[2]）。其他一些作品研究了与有限状态自动机等价的卵石自动机的更多限制模型（参见[3]和本文的参考文献）。2.1与上下文无关语言在[10]和[6]中证明了许多重要的节能灯类，如有界节能灯、结构节能灯和标准节能灯都可以用卵石自动机来识别。设CFL是由所有上下文无关语言构成的集合，上述作者留下了以下问题：CFL是否包含在集合i中？i∈N我们可以为这个老问题提供一些线索首先，我们观察到，i。是IN包含在logspace中。这个后来的事实表明存在上下文无关语言卵石自动机无法识别的东西人们普遍认为，存在不属于L语言的（确定性）上下文无关语言。这样的信念促使了logDCFL类的引入（见[12]），否则这个类将平凡地等于L。因此，似乎很容易证明CFL不包括在i中。 如果一个人想IN为了详细证明这一事实，他可以试着寻找一个语言序列，比如说{Li}i≥2，满足以下两个性质：(i) 对所有i ≥ 1，存在j使得L j∈ Pi\Pi−1。(ii) 序列是统一的。这意味着存在一个字母表，对于所有i≥2i，有可能使Li ≠0，且givena∈/语言我们有，是一种上下文无关的语言。L∞=，akw：w∈Lk，如果{Li}i≥2是这样一个序列，我们有L∞是上下文无关语言，，P ali，i≥1 是统一的。因此，我们可以证明以下内容：C. Mejía等人/理论计算机科学电子笔记339（2018）99107定理2.1存在一种上下文无关语言，它不包含在P中。证据 令ai= 0， 1。还有待证明的是，P al∞=，akw：w∈P alk，，是一种上下文无关的语言。请注意，可以使用与识别语言pullback类似的非确定性下推自动机轻松识别pullback∞，主要区别如下：设ak w为输入字符串。每次自动机识别出w的回文因子时，它都会进行一次额外的ε-转换以弹出一个符号a。如果输入是ak w，自动机将k个符号a写入下推堆栈在计算的开始。 自动机接受空栈。Q看起来，作为一种上下文无关的语言，pebble自动机不能识别语言pebble。如果这个后来的猜想是真的，我们可以提出上述定理的另一种证明以及推论的另一种证明2.5和2.6。2.2不确定卵石自动机不确定卵石自动机是指具有非确定性行为的卵石自动机。我们省略了介绍这种新的自动机模型的形式定义。第一个要问的问题：非决定论是否赋予卵石自动机计算能力？2.2NPi是可以用i个pebbles非确定性识别的语言类。注意，对于所有i≥0PiPi+1N Pi +1N Pi +2因此，第一个问题涉及确定性和非确定性类之间的包含关系的性质i= 1， 0的情况是特殊情况。 我们有这个P0=P1=NP1=NP0下一个定理允许我们对所有i≥3回答上述问题定理2.3对所有i ≥ 1，语言i可以用三个pebble非确定地识别.证据设i≥3，我们定义一个3-pebble自动机Mi，它能识别语言pebblei.自动机Mi使用非确定性来猜测i个回文因子的结束位置。它对输入w的工作方式如下：108C. Mejía等人/理论计算机科学电子笔记339（2018）99假设Mi位于单元格j上，三个卵石被放置在单元格j上，M i的内部状态编码一个数k≤i，并且Mi已经检查了w [1，.，j] ∈ k。假设k< i。如果j=|W|，自动机Mi停止并拒绝。否则，它将一个pebble放在单元格j+1上，并携带其余两个pebble向右前进，直到它非确定性地选择位置l>j+1。然 后 ，它将一个pebble放置在单元格l上，并使用另外两个pebble来检查w [j +1，.， l] ∈[1]。 如果检查是肯定的，它将三个卵石放在单元l上，并在其内部状态中编码数字k+1。Q注2.4也可以用类似的算法证明，NP3是NP3.从上面的定理中，我们可以得到以下推论：推论2.5对所有i≥ 3，Pi; NPi。此外，这两个层次并不是交错的，不确定性不能被卵石数量的增加所取代推论2.6对所有i ≥ 1，我们有NP3<$Pi。还有许多其他的基本问题需要考虑。对这些问题的研究可能具有巨大的教学潜力。考虑以下问题：• 安全壳P2;NP2是否严格？• 不确定性pebble层次结构是严格的吗？• 非决定论能模拟多少鹅卵石或者，最好问：是否存在k >0，使得对所有i，包容Pi+k;NPi成立？3结束语：卵石自动机和乔姆斯基层次结构我们认为卵石层次结构是一个具有巨大教学潜力的强有力的结构。乔姆斯基的层次结构已被用作自动机理论教学的标准叙述。然而，近年来对这种等级制度的作用提出了一些批评（非正式讨论见[7]和[11]）。有人认为，乔姆斯基层次结构不是一个真正的层次结构，而是一个小的语言类集合，具有由包含关系给出的线性顺序。此外，有人认为，这个简短的层次结构中的一些层次是不自然的，从机器的角度（下推自动机）以及从语法的角度（规则和一般语法）来看，这是真的。必须说，为了支持乔姆斯基的层次结构，它包含了大多数应用程序中出现的语言类（常规，上下文无关，上下文敏感和图灵可计算）。C. Mejía等人/理论计算机科学电子笔记339（2018）99109卵石层次是一个无限（有点连续）的层次，编码一个进化过程，从最基本的自动机模型开始，并收敛到单带图灵机的通用模型。这一过程是由书写能力的增加以自然的方式驱动的。它包含（在限制范围内）常规，上下文敏感和图灵可计算语言的类但是，正如我们之前所看到的，它在某种程度上与上下文无关语言类正交。这后一个事实应该被视为等级制度的一个主要的基本法则，如果一个人想把它作为一种理论教学的叙述，那么这个基本法则就变得更加重要。有两种可能的补救办法来解决这个问题：(i) 一些作者（见[7]和[11]）建议将所有关于上下文无关文法和下推自动机的材料纳入程序设计语言理论课程的教学大纲中，并将理论课程限制在有限状态自动机和图灵机的研究中。有人认为，有限状态自动机必须作为起点保留，因为这种材料给出了关于非决定论和计算机科学其他基本思想的所有正确直觉。从这个建议的解决方案的角度来看，卵石层次结构是一个完整的叙述，被称为填补起点（有限状态自动机）和到达点（图灵机）之间的差距。(ii) 我们认为，CFGs和PDA的材料是如此有价值，它必须（至少）以某种方式处理。碰巧下推自动机可以被表示为从有限状态自动机开始的进化树的附加分支，并且通过添加以不同的方式驱动。写作的力量。回想一下，可以使用pebble来模拟计数器和下推堆栈。让我们详细说明一下这个事实。让我们假设我们有两组鹅卵石，第一组是有限的，由黑色鹅卵石组成，而第二组是有限的，由白色鹅卵石组成。 让我们也假设输入带包含一个特殊的黑色单元，比如单元0，使得可以在其上放置任何有限数量的黑色鹅卵石。白色鹅卵石是可以放在细胞上的鹅卵石与单元格0不同。可以使用单元格0和无限规定用黑色鹅卵石来模拟柜台 因此，首先，我们可以恢复双向计数器自动机的模型。 如果我们允许有两个具有无限卵石容量的黑细胞，我们得到了双计数器自动机模型。回想一下，可以使用两个计数器来模拟下推堆栈[5]。 因此，我们也可以恢复双向下推自动机的模型。我们认为在这一点上可以引入单向下推自动机，以及上下文无关文法的一些材料。 此外，（从教学的角度来看）提出一些与具有大量黑色单元的卵石自动机的计算能力相关的问题可能是有趣的。 我们注意到，四个黑细胞可以用来模拟两个下推堆栈，因此我们有这个新的自动机模型是一个通用的[5]。这意味着更大（和有界）数量的黑色单元不会赋予计算能力。如果所有的细胞都是黑细胞会发生什么？110C. Mejía等人/理论计算机科学电子笔记339（2018）99这个新的黑色自动机模型至少与∞-卵石自动机模型一样强大，最多与二维图灵机模型一样强大[9]。后两个事实表明，黑色自动机模型等价于图灵机模型，我们又一次得到了一个通用的计算模型。确认第一作者要感谢COLCIENCIAS授予的赠款，这使她能够发展她的博士研究。第二作者要感谢哥伦比亚国立大学，这项研究得到了Hermes研究系统的部分支持，项目编号32083。引用[1] M. 布卢姆角休伊特二维磁带上的自动机SWAT（FOCS）1967：155-160.[2] M. Bo janczyk，M. Sa muelides，T. S chwe nti ck，L. Segoufinn. Pebble自动机的功率表示ICALP（1）2006：157-168.[3] D Casas，J. A.蒙托亚正则运算的实态处理和Sakoda-Sipser问题。电动注意Theor。Comput. Sci. 321：23-39，2016.[4] L.哈尔贝森组合集合论与强迫的温和介绍。Springer Verlag，London，2014.[5] 霍普克罗夫特河Motwani，J. Ullman. 自动机理论、语言和计算导论。Addison-Wesley，马萨诸塞州雷丁，2002年。[6] 夏河是的。标记自动机。信息科学8（1）：71-88，1975年。[7] https://rjlipton.wordpress.com/2016/08/09/do-results-have-a-teach-by-date/[8] J. A.蒙托亚与回文识别相关的开放问题：是否存在相关的开放问题到回文识别Journal of Automata，Languages and Combinatorics 20（1）：5-25，2016.[9] C. 帕帕迪米特里乌计算复杂性。Addison-Wesley，马萨诸塞州雷丁一九九四年[10] R. Ritchie，F.弹簧钢用标记自动机进行语言识别。Information and Control 20（4）：313-330，1972.[11] http://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory[12] I.萨德伯勒关于确定性上下文无关语言的磁带复杂性。J. ACM 25（3）：405-414，1978年。