最小串行策略下脉冲神经膜系统的语言产生能力

为了验证脉冲神经膜系统(SNPS)在运算受限情况下的计算性能,该文在标准SNPS中引入最小串行策略,并研究其语言产生能力。在使用最小串行策略的SNPS的每一步计算中,只有满足相应规则且所含脉冲数最少的神经元才可以激发。首先分析了使用最小串行策略的SNPS与有限语言和正则语言的关系,定义了任意多元字母表到二元字母表的映射,构建了能够产生递归可枚举语言的SNPS,设计了加法模块和减法模块。模拟注册机证明,使用最小串行策略的SNPS能够刻画递归可枚举语言,验证了SNPS在最小串行策略下仍具有与图灵机等价的计算能力。

短语结构语法──“信息处理用语言理论讲话”第一讲

短语结构语法──“信息处理用语言理论讲话”第一讲林杏光编者按本刊这一期开始连载“信息处理用语言理论讲话”。信息处理用语言理论是指计算机常用的一些语言流派，诸如短语结构语法、语言串理论、扩充转移网络、词汇功能语法、功能合一语法、广义短语结构语法、限定子...

基于量子逻辑的图灵机及其通用性

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.

Max-Lukasiewicz复合推理下的模糊图灵机

研究max-Lukasiewicz复合推理下的模糊图灵机。形式化定义了模糊图灵机——确定型模糊图灵机、非确定型模糊图灵机、带部分转移函数的非确定型模糊图灵机和多带模糊图灵机,研究了这几类模糊图灵机的关系。进而定义模糊图灵机上的模糊递归可枚举语言和模糊递归语言。得出结论:当接受模糊递归可枚举语言时,非确定型模糊图灵机和确定型模糊图灵机不等价;而接受模糊递归语言时,它们等价。

模糊图灵机的逼近性与通用性

模糊图灵机是模糊算法或模糊计算的形式模型.文中研究了模糊图灵机的几种变形,这包括基于max-★复合运算的非确定型模糊图灵机(简写为NFTM★,其中★为t-模),非确定型模糊图灵机(简写为NFTM),确定型模糊图灵机(简写为DFTM),以及这些变形的多带版本.得到了以下一些结论:第1,若t-模★不满足有限生成条件,则NFTM★,NFTM和DFTM一般不等价,这里等价指的是识别相同的模糊语言.但在逼近意义下等价,也即,NFTM★可以被NFTM以任意精度逼近,并给出了相关的构造.引入了模糊递归可枚举语言与模糊递归语言的概念,并利用递归可枚举语言与递归语言对其进行层次刻画.第2,如果限制NFTM★的模糊隶属函数的取值域为单位区间[0,1]的一个固定的有限子集D,则存在通用模糊图灵机,用该通用模糊图灵机可以模拟上述类型的限制型模糊图灵机.一般地,通用模糊图灵机在逼近意义下存在,该通用模糊图灵机可以以给定精度模拟任意类型的模糊图灵机.