科学网 › 标签 › 自动机论

标签: 自动机论

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

细胞自动机论的简单小结: 热度 1 williammilo 2010-3-13 21:38; 我的博客已经搬家到 xiongbox.com 欢迎访问熊伟的博客！本文永久链接 http://xiongbox.com/细胞自动机论的简单小结/ 1.细胞自动机论主要研究由小的计算机或部件，按邻域连接方式连接成较大的、并行工作的计算机或部件的理论模型。 2.诺伊曼细胞空间的所有细胞都在整数网格的结点上，细胞个数为无限。它满足下列条件：各个细胞都是确定的摩尔型有限自动机；采取五邻域一致连接模式（所有细胞有同样形状的邻域）；不带外部输入，不向外部输出；并且是静态的（邻域不随时间改变）。一般的细胞空间不必要这些条件限制，故此外还有非确定型细胞空间、米雷型细胞空间、连接模式非一致的细胞空间、带外部输入的细胞空间以及动态的细胞空间等。 3.棋盘格空间是细胞空间的一个直接推广。它有分配到各个细胞的统一的外部输入。或者说，棋盘格空间是一个程序控制的细胞空间。棋盘格空间里的每一个细胞能够被想象为有一个局部转移函数的有限集合。因此，棋盘格空间有一个全局转移函数的有限集合。程序中的各个“指令”选择在该时刻的转移中所使用的全局转移函数。 4.细胞自动机不仅可以在形式上作为并行计算机的理论模型来研究，而且还可以作为语言（被机器接受的输入字的集合）识别器。一个语言被某种识别器所识别是指：识别器不仅接受该语言中的字，而且拒绝不属于该语言中的字。在维数高于１时，语言识别有时被看作模式识别。对于迭合自动机，如果每一时间步只输入一个字母，当字全部输完之后，如果输入输出细胞进入一个特别设计的接受状态，就认为它接受了这个字。语言的所有的字都被接受时就称为迭合自动机语言。类似地，棋盘格自动机和一维细胞自动机也可以用作语言接受器。 5. 用细胞自动机的并行计算方式可实现一些并行计算机和识别器的设计。细胞自动机对于集成电路的设计方法具有重要意义。大规模集成电路采用细胞阵列形式具有明显的优点。生物学推动了有关自动机的理论研究。反过来，有关自动机理论的发展为生物发育学提供了一种数学模型和方法。细胞自动机论的研究与形式语言的研究更是息息相关，各种细胞自动机的识别能力，以及它们所能识别的各种语言类与各类形式语言之间的关系都还处于探讨中。另外，各种类型细胞自动机的性质，以及它们彼此之间的关系也都是人们关心的课题。; 个人分类: 电子信息工程与计算机科学|4449 次阅读|0 个评论

概率自动机论的简单小结: williammilo 2010-3-13 21:15; 我的博客已经搬家到 xiongbox.com 欢迎访问熊伟的博客！本文永久链接 http://xiongbox.com/概率自动机论的简单小结/ 1.概率自动机论主要研究所处环境或内部具有（有限或无限的）随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机，首先必需规定在自动机处于某一状态，并向自动机输入某个字母的条件下，自动机下一动作（如状态转移，输出某个字母，改写字母等）的条件概率函数。 2.在概率图灵机的研究中，对可计算随机函数，给出了定义并对可计算函数及其运算也都作了研究，而且还证明了图灵机的许多研究结果在概率图灵机的情况下仍然成立。函数代入、原始递归、求极小等运算对可计算随机函数都是封闭的。限制在普通函数类的范围内，可以证明部分可计算随机函数中的普通函数，恰好是部分递归函数。从这个意义上看，把图灵机推广到概率图灵机的计算能力没有增大。也可以通过别的刻划方法，使概率图灵机所刻划的普通函数类，以部分递归函数类作为其真子类。在相对可计算性方面也有类似的结果。 3.如同在非概率时序机情况，多余的等价状态可以被消除，从而得到一个化简了的时序机。对于概率时序机，它的化简了的形式不是唯一的，这一点和确定的时序机的情况有所不同。对于一个给定的概率时序机，可以找到一个寻求它的所有化简形式的计算方法。随机语言类包含有限识别器所识别的正则语言类作为其真子类，因而概率有限识别器是有限识别器的真推广。随机语言类对运算的封闭性，它的结构以及它与正则语言类的关系都是研究的重要内容。 4.概率自动机也可以用于多阶段判决过程。在这一过程中，从一个状态到另一状态的转移都附有一个条件概率和补偿因子。熵的概念可以用于模式识别和可靠性问题的研究。用概率自动机描述不可靠自动机时，熵可以作为有限自动机的可靠性的测度。可靠性随着熵的减小而增加，可靠自动机的熵是零。概率自动机理论与信息论、可靠性理论、自学习理论和模式识别、控制论、程序设计和马尔可夫链的函数理论都有着密切的联系。图灵机，各型形式语言的概率性推广，具有概率性结构的树自动机，概率自动机与动态规划的关系，以及从范畴论观点对随机自动机的研究，都是一些有意义的研究课题。; 个人分类: 电子信息工程与计算机科学|5256 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 自动机论

相关帖子

相关日志

关闭安全验证