Pi演算对图灵机的表达  

Expression of Turing Machines by Pi Calculus

作　　者：郝克刚[1] 郭小群[1] 

机构地区：[1]西北大学信息科学与技术学院,陕西西安710069

出　　处：《计算机工程与科学》2009年第10期53-55,共3页Computer Engineering & Science

基　　金：国家863计划资助项目(2007AA010305)

摘　　要：为了研究Pi演算的表达能力,我们试着用它来表达图灵机。研究结果表明,只要对Pi演算进行一定的的扩展,即引入某些函数符号,允许对发送的名字作一定的运算,就可以用Pi演算的规约来表达图灵机的运算过程。In order to study the expressiveness of the Pi calculus, we try to use it to express Turing machines. The results show that as long as a certain extension is made, i. e. introducing some function symbols and allowing the names for certain operations, you can use the reductions of pi calculus to express the computing process of Turing machines.

关 键 词：PI演算 表达能力 图灵机 函数符号 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]