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

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

图灵机设计问题解法的优化

图灵机设计问题的常规解法一般有多个状态和较复杂的δ映像函数．给出了三种优化的解题方法，与常规方法相比用较少的状态数优化了图灵机的设计，达到减少状态的冗余和简化δ映像函数的目的．     

一种图灵机识别语言算法的进一步描述

图灵机是作为一种可计算性的数学模型提出的，为计算机的发展奠定了理论基础。该文针对计算理论导引教材中一个图灵机算法实例的描述中不够完善的地方加以改进，从而保证了该图灵机描述的严谨性与可靠性。     

一种三状态图灵机的设计

给出了接受语言L={0n1n|n≥0}的仅有3个状态的图灵机的一种设计,其方法是通过对带符号的配合使用来控制图灵机带头移动的方向,达到精减图灵机状态数的目的,并采用C语言编程实现.     

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

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

书籍

<正>图灵的秘密作者:Charles Petzold图灵机是英国数学家阿兰·图灵提出的一种抽象计算模型,佩措尔德编著的《图灵的秘密:他的生平、思想及论文解读》深入剖析了图灵描述图灵机和可计算性的论文《论可计算数及其在判定性问题上的应用》。《图灵的秘密:他的生平、思想及论文解读》中在详解论文的同时,附带了大量的历史背景资料、图灵的个人经历,以及图灵机对人们理解计算机、人类意识和宇宙所产生的影响。     

一类递归函数的符号计算

针对有限状态自动机只能识别正规集合和计算一些相对简单函数的问题，给出了一类递归函数的符号计算方法。该方法把递归函数和图灵机结合起来，通过符号处理可以用接受自变量的图灵机来模拟后继函数的计算过程，对计算机病毒程序及自复制／自传播的研究具有一定的参考价值。     

实函数的归约性

本文才巴 Ker-IKO 文中实数归约性推广到实函数,讨论了推广后各种归约之间的关系。证明了两种递归实函数定义的等价性。引入了算子图灵机的概念,利用算子图灵机给出了 C[1,0]上的一个分层(不可解度的分层)。证明了该分层有一个子结构与(?)同构。     

“计算思维”的传承与发展

本文以我国古算具算盘算筹和20世纪30年代问世的图灵机为例,通过详细分析中国古算的算法化思想和图灵机理论后提出：计算思维不是计算机思维,它不是计算机的产物,更不是一个新概念,而是千百年来计算学科在发展过程中一直遵循传承的一种科学思维。     

Petri网在复杂系统建模中的意义

图灵机模型是计算机的理论模型,它能实现模型相互之间的模拟,但应用于通信系统等异步、并行的复杂系统却很难模拟,从而引入了一种建模工具--Petri网.通过介绍自动机和图灵机的原理.分析Petri网.给出一个具体的基于Petri网建模方式的实例,并对实例模型和现有的建模工具进行比较,从而证明Petri网在复杂系统建模中是处于优势的.     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

Some variants of SAT and their properties

A new model for the well-known problem, the satisfiablility problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their properties are presented. Denote by NP the class of all languages which can be decided by a non-deterministic polynomial Turing machine and by P the class of all languages which can be decided by a deterministic polynomial-time Turing machine. This model also allows us to give another candidate for the natural problems in ((NP-NPC)-P), denoted as NPI, under the assumption P≠NP, where NPC represents NP-complete. It is proven that this candidate is not in NPC under P≠NP. While, it is indeed in NPI under some stronger but reasonable assumption, specifically, under the Exponential-Time Hypothesis (ETH). Thus we can partially solve this long standing important open problem.     

普特南的身心学说初探

普特南 ( Hilary Putnam,192 6- )是美国当代著名哲学家。 60年代他发表了一系列的文章来论证心理状态的图林机模拟的合理性 ,认为任何心理状态都可以与特殊的图林机功能相对应。这是普特南早期关于心理阐释的“功能主义”。 80年代末以后 ,普特南的思想发生了很大的转变 ,对“功能主义”予以激烈的批判 ,着重阐述了心理现象的社会文化相关性和哲学阐释的必要性。前后期思想形成了互补的两极 ;功能模拟的方法合理性以及哲学阐释的本性合理性     

可计算函数的基本指令研究

Davis曾提出由三条Fortran语言形的基本指令组成的与Turing机等价的计算模型。本文提供与之等价的另外三条Fortran形的基本指令,并论述了Davis的三条指令是必不可少的,另外还论证了它们与由Shepherdson & Sturgis在1963年提出的URM的等价性。     

Programmable and autonomous computing machine made of biomolecules.

Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is the universal Turing machine, which stimulated work leading to the development of modern computers. The Turing machine and its special cases, including finite automata, operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for molecular DNA computers. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated, but the realization of computing devices operating autonomously on the molecular scale remains rare. Here we describe a programmable finite automaton comprising DNA and DNA-manipulating enzymes that solves computational problems autonomously. The automaton's hardware consists of a restriction nuclease and ligase, the software and input are encoded by double-stranded DNA, and programming amounts to choosing appropriate software molecules. Upon mixing solutions containing these components, the automaton processes the input molecule via a cascade of restriction, hybridization and ligation cycles, producing a detectable output molecule that encodes the automaton's final state, and thus the computational result. In our implementation 1012 automata sharing the same software run independently and in parallel on inputs (which could, in principle, be distinct) in 120 microl solution at room temperature at a combined rate of 109 transitions per second with a transition fidelity greater than 99.8%, consuming less than 10-10 W.     

耦合诱导Turing斑图的形成

通过数值模拟的方法研究了耦合的CDIMA反应模型。结果显示:处于不能形成图林斑图区域的系统与另一个处于图林斑图区域的系统进行耦合,两系统都能形成图林斑图。