| Pi演算对图灵机的表达 |
| |
| 引用本文： | 郝克刚,郭小群. Pi演算对图灵机的表达[J]. 计算机工程与科学, 2009, 31(10). DOI: 10.3969/j.issn.1007-130X.2009.10.016 |
| |
| 作者姓名： | 郝克刚 郭小群 |
| |
| 作者单位： | 西北大学信息科学与技术学院,陕西,西安,710069;西北大学信息科学与技术学院,陕西,西安,710069 |
| |
| 基金项目： | 国家863计划资助项目 |
| |
| 摘 要： | 为了研究Pi演算的表达能力,我们试着用它来表达图灵机。研究结果表明,只要对Pi演算进行一定的的扩展,即引入某些函数符号,允许对发送的名字作一定的运算,就可以用Pi演算的规约来表达图灵机的运算过程。
|
| 关 键 词： | Pi演算 表达能力 图灵机 函数符号 |
Expression of Turing Machines by Pi Calculus |
| |
| HAO Ke-gang,GUO Xiao-qun. Expression of Turing Machines by Pi Calculus[J]. Computer Engineering & Science, 2009, 31(10). DOI: 10.3969/j.issn.1007-130X.2009.10.016 |
| |
| Authors: | HAO Ke-gang GUO Xiao-qun |
| |
| Abstract: | 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. |
| |
| Keywords: | Pi calculus expressiveness turing machine function symbols |
| 本文献已被 万方数据 等数据库收录！ |
|
