基于图灵机的递归技术的实现 - 计算机工程与科学.pdf

CN43—1258／TP 计算机工程与科学 2008年第 30卷第 10期 ISSN 1007—130X COMPUTERENGINEERING ＆ SCIENCE V01．30，No．10，2008 文章编号：1007-130X(2008)10-0153—03 基于图灵机的递归技术的实现 RecursiveTechnologyBasedonTuringMachines 陈晓亮 ，卢朝辉 ，宋 文 CItEN Xiao-liang~，LU Zhao-hui2，SONG Wen1 (1．西华大学数学与计算机学院，四川 成都 610039；2．河北理工大学计算机与自动控制学院，河北 唐山063009} (LSchoolofMathematicsandComputerEngineering。XihuaUniversity，Chengdu610039； 2．SchoolofComputerandAutomaticControl，HebeiPolytechnicUniversity。Tnagshna 063009，China) 摘 要：图灵机是通用的计算机模型，一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析 了 递归的特征，利用多带图灵机作为计算模型，定义了递归技术转移函数形式，提 出了图灵机递归过程信息传递与保存的方 法 ，给 出了图灵机调用的实现 ，继而给 出了图灵机递归技术 的实现 ，同时证 明了图灵机 的调用与 图灵机 的递归调用是 图灵 可识别 的。 Abstract：A Turingmachineisthemodelofageneralcomputer．Thegeneralprogrammingandthecomputingwiththe modelofaTuringmachinesupportrecursion．Inthispaper，thecharacteristicsofrecursionareana lyzed．Byusingamulti— tapeTuringmachineasthecomputingmodel，theformofthetransitionfunctionisdefined，themethodofinformationtrans— fernadstoragebasedontherecursivetechnologyispresented．ThispaperalsoestablishesamethodtOimplementtheTur- ingma chineinvocation，givestherealizationoftheTuringmachinerecursivetechnology，andprovesthatTuringmachinein— vocationandTuringma chinerecursiveinvocationareTuring-recognizable． 关键词：图灵机；递归调用；模型；计算；算法 Keywords：Turingmachine；recursiveinvocation；model；computation；algorithm 中图分类号：TP301．6 文献标识码：A 器模型的计算也是支持递归的。HesselinkW H从串行语 1 引言 义学的角度给出了一般递归的前置谓词的语义，最后用 Hoare-triple证明了递归程序 的完全正确性和部分正确 1936年，阿兰图灵给出了图灵机的模型。他从这种简 性[2]。但是，在至今的文献中几乎没有关于基于图灵机的 单的数学机器出发来研究计算的概念 ，通过引入机器状态， 递归的实现。本文就是基于此 目的出发的。 使用了本质上具有指令特点的程序运算操作。十年过去 本文利