基于量子逻辑的图灵机及其通用性 - 计算机学报.pdf

第卷第期 计 算 机 学 报 ３５ ７ 　 　　　　　　　　 Ｖｏｌ．３５Ｎｏ．７ 年月 ２０１２７ Ｊｕｌ２０１２ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｙ 　 基于量子逻辑的图灵机及其通用性 ），） ） １２ ２ 李永明 李平 　　　 ） １（ ） 陕西师范大学计算机科学学院西安７１００６２ 　 　 ） ２（陕西师范大学数学与信息科学学院西安 ） ７１００６２ 　 　 摘要基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向该文研究了基于量子逻辑的图灵机 ． 　　 （简称量子图灵机）及其一些变形，给出了包括非确定型量子图灵机 ，确定型量子图灵机 以及相应 犾ＶＴＭ 犾ＶＤＴＭ 类型的多带量子图灵机，并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式，证明了这两 种定义方式在量子逻辑意义下是不等价的进一步证明了 、 与相应类型的多带量子图灵机之间的 ． 犾ＶＴＭ犾ＶＤＴＭ ， ， ， 等价性其次给出了量子递归可枚举语言及量子递归语言的定义并给出了二者的层次刻画证明了 与 ． 犾ＶＴＭ 不等价，但两者作为量子递归语言的识别器是等价的最后，文中讨论了基于量子逻辑的通用图灵机的存 犾ＶＤＴＭ ． 在性问题，给出了一套合理编码系统，证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在，而 在其所取值的正交模格有限时是存在的 ． 关键词量子逻辑；量子计算；量子图灵机；量子递归可枚举语言；量子递归语言 　 中图法分类号 号： ／ ＴＰ３０１ 犇犗犐１０．３７２４ＳＰ．Ｊ．１０１６．２０１２．０１４０７ 　　　 犜狌狉犻狀犕犪犮犺犻狀犲狊犅犪狊犲犱狅狀狌犪狀狋狌犿犔狅犻犮犪狀犱犜犺犲犻狉犝狀犻狏犲狉狊犪犾犻狋 犵 犙 犵