基于量子逻辑的图灵机及其通用性

摘要：

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.

关键词：量子逻辑、量子计算、量子图灵机、量子递归可枚举语言、量子递归语言

所属期刊栏目：35

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60873119;教育部高等学校博士点基金200807180005

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：1407-1420