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

Recursive Technology Based on Turing Machines

图灵机是通用的计算机模型,一般程序设计和以图灵机为机器模型的计算也是支持递归的。本文首先分析了递归的特征,利用多带图灵机作为计算模型,定义了递归技术转移函数形式,提出了图灵机递归过程信息传递与保存的方法,给出了图灵机调用的实现,继而给出了图灵机递归技术的实现,同时证明了图灵机的调用与图灵机的递归调用是图灵可识别的。

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.