基于扩展通用图灵机的计算机病毒传染模型

在计算机基础理论模型———图灵机模型的基础上 ,提出了一种扩展的通用图灵机 (EUTM)模型 ,这种模型突出了计算机病毒的传染特性 ,极大地简化了计算机病毒传染的形式描述 ,并根据EUTM模型给出了计算机病毒的形式定义 ,形式化描述了计算机病毒在单机和多机环境下的传染 最后指出了FredCohen关于病毒检测不可判定性定理证明的不足 。

计算的模型:图灵机与Petri网

形式化的软件开发方法是建立在严格数学基础上的,其目标是通过严格的分析、验证发现软件设计及开发过程中的模糊性和不完备性,以达到对软件质量的有效控制。Petri网是形式化软件开发的一种很好的描述工具,它在描述异步并发的环境、模型验证等方面有着独到之处;图灵机是迄今为止计算能力最强的计算模型,在理论层面上有着其他模型不可替代的重要作用,它深刻地刻画了物理世界的可识别与可判定2个重要的概念。文章给出了这2种计算模型的一些基本概念、结论以及解决问题的主要方法。最后,用交通管理系统为例说明形式化方法的运用。

从中国“古算”到“图灵机”——看不同历史时期“计算思维”的演变

现代计算学科大家族中有许多分支,如并行计算、网格计算、高性能计算、情感计算、虚拟计算、移动计算、云计算、移动云计算……但追根寻源,提起＂计算＂,我们还是得从最古老的中国＂古算＂谈起。现代计算思维最集中体现和最典型特征之一,就是＂完备的计算系统必须是软硬件结合的系统＂,计算机如此,手机也如此。

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

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

图灵机扫描子串技术(英文)

某些语言中的所有句子必须包含有或者不能包含有特定的子串,或者需要将语言中句子所包含的子串进行替换。传统的方法是利用图灵机的存储技术处理该类语言。该文提出了一种图灵机扫描子串技术的新方法,即将特定子串当作一个整体,将扫描一个符号的图灵机的多个状态转换函数合并为一个,使得图灵机一次可以扫描多个符号,但图灵机的读/写头仅移动一个单元。该方法简便且有效,通过实例证明了扫描多个符号的图灵机与扫描一个符号的图灵机是等价的。

Pi演算对图灵机的表达

为了研究Pi演算的表达能力,我们试着用它来表达图灵机。研究结果表明,只要对Pi演算进行一定的的扩展,即引入某些函数符号,允许对发送的名字作一定的运算,就可以用Pi演算的规约来表达图灵机的运算过程。

算法、图灵机、哥德尔定理与知识的不确定性

知识论一直在寻求对知识的确定性作一般算法式的逻辑证明的辩护。然而 ,即使在处理抽象的数量概念的数学基础研究中 ,也不能达到最终逻辑证明的确定性。图灵对停机问题的算法步骤的否定回答、哥德尔定理对真理的“不可证明性”的确立 。

四则运算图灵机的构造

著名的丘奇(A.Church)命题指出,任何算法都可以用一个图灵机来描述.对自然数的四则运算给出了相应的图灵机.

图灵机和图灵测试

阿兰?图灵为人工智能学的诞生做出了重大的贡献,本文介绍了图灵机和图灵测试,图灵机对计算机的结构、可实现性和局限性都产生了深远的影响,而图灵测试为机器能否思考的争论双方找到了一种公认的判决准则。

基于图灵机的计算问题

详细介绍了图灵机计算问题,并对多带图灵机、确定图灵机等进行了论述,同时应用"回文"(Palindromes)语言的识别、对图灵机计算问题进行了说明,最后对图灵机的复杂度给出了求解。

图灵机计算实数函数的稳定性(英文)

定义在全体实数上的可计算函数是一个很重要的概念。在这以前定义可计算的实数函数有两个途径。第一个途径是首先要定义可计算实数的指标。想要确定实数函数y=f(x)是不是可以计算就要看是否存在一个自然数的(部分)递归函数将可计算实数x的指标对应到可计算实数y的指标。这样一来对实数函数的研究依赖于对自然数函数的研究。第二个定义可计算的实数函数的途径是以逼近为基础的。一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的。用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数。例如"<"和"="的命题函数就是不可以计算的因为它们是不连续的命题函数。本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义。我们的定义不需要用到自然数的(部分)递归函数。根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的。用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多。

密码学与非确定型图灵机

密码学是信息和网络安全的主要基础,计算机科学是密码学的主要基础,"P对NP"问题又是理论计算机科学的基础问题。首先介绍确定型图灵机DTM、非确定型图灵机NDTM的基本概念,接着介绍"P对NP"问题的基本含义。然后介绍计算机科学家Stephen Cook在2003年的观点:如果证明了P等于NP,那么依据计算复杂性的密码术就是没有用途的;如果证明了P不等于NP,那么证明RSA、DES等密码术的安全性比解决"P对NP"问题还困难。

基于非确定图灵机的中文搜索引擎研究

随着Internet用户对Web信息资源需求的增加,搜索引擎技术得到迅猛的发展.针对目前中文搜索引擎大多采用基于关键词精确匹配(Accurately matched)的低智能性问题,提出一种基于非确定图灵机NTM(Nondetermin-istic Turing Machine)智能中文搜索引擎系统,简要介绍了非确定图灵机的基本知识,详细叙述了该搜索引擎的系统架构,系统实现的基本原理和算法.实验数据结果表明,基于非确定图灵机智能中文搜索系统在查询结果的准确性和智能性明显高于现有的搜索系统.

基于持久图灵机和细胞自动机的病毒Agent及其动力学建模

计算机病毒是这样一种程序,当它在一台计算机上执行时,能够利用该机器的资源生成自身的可能进化了的副本,每个副本可以通过某种方式传播到其他计算机中,并有机会得到执行.一个具体的病毒实例被称为病毒Agent,因为它在执行过程中能够在无用户干预的情况下自主进行动作选择,从而具有了基本的自治性.持久图灵机是一种描述顺序交互的正则模型,基于持久图灵机建立了一种病毒Agent的计算模型.该模型展现了计算机病毒的传染性本质,并且克服了传统图灵机病毒模型在表现交互性上的固有缺陷.在该模型的基础上,推导出一些与病毒Agent相关的有用定理.还讨论了利用细胞自动机进行病毒Agent动力学建模的问题,并得到了一些启发性的结论.

从现代计算机视角看嵌入式系统(2)——从图灵机到现代计算机

现代计算机的源头是微处理器，微处理器的体系结构的源头是20世纪30年代图灵学者们的思想体系。1936年，图灵提出了人工智能的图灵机模型后，现代计算机经历了一个曲折的演变过程。冯·诺依曼沿着图灵机的思路，参与创建了世界上第一台电子计算机ENIAC。

基于图灵机的递归技术的实现

图灵机是通用的计算机模型,一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征,利用多带图灵机作为计算模型,定义了递归技术转移函数形式,提出了图灵机递归过程信息传递与保存的方法,给出了图灵机调用的实现,继而给出了图灵机递归技术的实现,同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。

虚拟的孪生图灵机——以双语信息处理为例

本文阐述一种虚拟的孪生图灵机,即:由两个图灵机组成的孪生并行计算机,其特征是其受限模式与派生模式分别由汉语的言即单音节字的基本符号对象和语即双音节多音节字组的符号组合解释为例加以说明。其作用在于基于它可建构理想的双语信息处理系统,即:协同智能计算系统;应用它可形成并行计算、分布计算、网格计算、虚拟计算和云计算乃至超级计算。其意义在于借助它蕴含的协同智能计算本质——虚拟与现实的关系,可把图灵可计算性、计算复杂性(其中揭示了一个基本原理——NP=P当且仅当N可有可无)和图灵测试连贯起来。

图灵机及其构造研究

图灵机模型是现代计算机科学的理论基础,学习图灵机理论对于研究计算机理论有着重要的意义。本文介绍了图灵机的产生和用途,分析其基本模型以及扩展模型,并通过举例对图灵机的构造进行了探讨。

有限制的通用模糊图灵机研究

给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间[0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,而且这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.

离线图灵机与单带图灵机的计算效率分析

研究离线图灵机与单带图灵机的计算效率的差别，证明了一个在离线图灵机上计算时间复杂度为Ｏ（ｎ）的判断问题，在单带图灵机上的计算时间复杂度为Ｏ（ｎ￣２），从而证明这两类计算模型在计算速度上存在非线性差别。