通用图灵机的计算机仿真设计

将图灵机转移函数δ(qi,aj)=(qk,al)编码为(i,Unicode(aj),k,Unicode(al)),并将此编码方案应用于所设计的通用图灵机模型.模型的存储装置由两个带组成:一个一维的单向带,用来存储输入数据ω;一个二维带,用来存储图灵机描述"M".在PC机上仿真了上述模型,控制器算法的时间复杂度为O(|K|2),优于传统编码方案的通用图灵机模型.

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

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

图灵机及其构造研究

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

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

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

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

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

K带实时图灵机计算能力与图灵机带数的关系

本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。

图灵机模拟系统的设计与实现

图灵机模型是现代计算机科学的理论基础,学习图灵机理论对于研究计算机软件理论有重要意义。文章分析了在Von Neumann机上仿真图灵机存在的两个问题,并针对单带图灵机模型设计了一个完整的图灵机模拟系统。该模拟系统能够编译并执行图灵机程序,为基于图灵机模型或其扩展模型的理论研究提供实验平台,对构造基于中间语言解释执行的虚拟机提供实践指导。

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

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

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

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

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

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

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

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

Pi演算对图灵机的表达

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

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

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

四则运算图灵机的构造

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

图灵机和图灵测试

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

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

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

基于图灵机的计算问题

详细介绍了图灵机计算问题,并对多带图灵机、确定图灵机等进行了论述,同时应用"回文"(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)智能中文搜索引擎系统,简要介绍了非确定图灵机的基本知识,详细叙述了该搜索引擎的系统架构,系统实现的基本原理和算法.实验数据结果表明,基于非确定图灵机智能中文搜索系统在查询结果的准确性和智能性明显高于现有的搜索系统.