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

Recursive Technology Based on Turing Machines

作　　者：陈晓亮[1] 卢朝辉[2] 宋文[1] 

机构地区：[1]西华大学数学与计算机学院,四川成都610039 [2]河北理工大学计算机与自动控制学院,河北唐山063009

出　　处：《计算机工程与科学》2008年第10期153-155,F0003,共4页Computer Engineering & Science

摘　　要：图灵机是通用的计算机模型,一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征,利用多带图灵机作为计算模型,定义了递归技术转移函数形式,提出了图灵机递归过程信息传递与保存的方法,给出了图灵机调用的实现,继而给出了图灵机递归技术的实现,同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。A Turing machine is the model of a general computer. The general programming and the computing with the model of a Turing machine support recursion. In this paper, the characteristics of recursion are analyzed. By using a multitape Turing machine as the computing model, the form of the transition function is defined, the method of information transfer and storage based on the reeursive technology is presented. This paper also establishes a method to implement the Turing machine invocation,gives the realization of the Turing machine reeursive technology, and proves that Turing machine invocation and Turing machine recursive invocation are Turing-recognizable.

关 键 词：图灵机 递归调用 模型 计算 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]