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

《基于图灵机的递归技术的实现(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CN43—1258／TP计算机工程与科学2008年第30卷第10期ISSN1007—130XCOMPUTERENGINEERING＆SCIENCEV01．30，No．10，2008文章编号：1007-130X(2008)10-0153—03基于图灵机的递归技术的实现RecursiveTechnologyBasedonTuringMachines陈晓亮，卢朝辉，宋文CItENXiao-liang~，LUZhao-hui2，SONGWen1(1．西华大学数学与计算机学院，四川成都610039；2．河北理工大学计算机与自动控制学院

2、，河北唐山063009}(LSchoolofMathematicsandComputerEngineering。XihuaUniversity，Chengdu610039；2．SchoolofComputerandAutomaticControl，HebeiPolytechnicUniversity。Tangshan063009，China)摘要：图灵机是通用的计算机模型，一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征，利用多带图灵机作为计算模型，定义了递归技术转移函数形式，提出了图灵机递归过

3、程信息传递与保存的方法，给出了图灵机调用的实现，继而给出了图灵机递归技术的实现，同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。Abstract：ATuringmachineisthemodelofageneralcomputer．ThegeneralprogrammingandthecomputingwiththemodelofaTruingmachinesupportrecursion．Inthispaper，thecharacteristicsofrecursionareanalyzed．Byusingamul

4、ti—tapeTuringmachineasthecomputingmodel，theformofthetransitionfunctionisdefined，themethodofinformationtrans—ferandstoragebasedontherecursivetechnologyispresented．ThispaperalsoestablishesamethodtOimplementtheTur-ingmachineinvocation，givestherealizationoftheTuringmac

5、hinerecursivetechnology，andprovesthatTuringmachinein—vocationandTuringmachinerecursiveinvocationareTuring-recognizable．关键词：图灵机；递归调用；模型；计算；算法Keywords：Turingmachine；recursiveinvocation；model；computation；algorithm中图分类号：TP301．6文献标识码：A器模型的计算也是支持递归的。HesselinkWH从串行语1引言义学的

6、角度给出了一般递归的前置谓词的语义，最后用Hoare-triple证明了递归程序的完全正确性和部分正确1936年，阿兰图灵给出了图灵机的模型。他从这种简性[2]。但是，在至今的文献中几乎没有关于基于图灵机的单的数学机器出发来研究计算的概念，通过引入机器状态，递归的实现。本文就是基于此目的出发的。使用了本质上具有指令特点的程序运算操作。十年过去本文利用多带图灵机作为机器模型，其上递归的实现后，人们意识到图灵机计算模型的巨大优越性。它不仅表类似于程序设计当中的递归调用，不同点在于调用的对象现在为存储程序式电子数字计算机提供了强大

7、的程序设计不同：在高级语言中递归调用的是函数，这里调用的是编码思想，又因其结构十分简单，操作运算相当基本，功能出乎化的图灵机。解决了递归过程信息传递与保存的问题，提意料地强大，以过程形式比较准确地刻画了计算这一基本出了一种基于图灵机递归实现的方法，最后给出了基于图的概念，从而被学术界广泛关注。而且，从图灵机出发可采灵机的递归算法。用相近的构造、定义方法设计，派生出一批计算能力强、使用方便、形式各异的自动计算机器，从不同的观察事物和处2基本概念理事物的角度为学科的发展奠定了重要的理论基础[1]。递归这一概念出现在计算数学以及程

8、序设计理论中，这里只给出本文所需要的一些基本定理，其它相关术几乎所有的高级语言都支持递归这一技术。以图灵机为机语可参考文献E3~5-1。收稿日期：2008-04—09；修订日期：2008-05-17作者简介：陈晓亮(1984一)，男，四川成都人，硕士生，CCF学生会员(E2o一001018