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

• 作者: 李平 李永明
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 量子逻辑 量子计算 量子图灵机 量子递归可枚举语言 量子递归语言
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1407-1420
• 分类号: TP301
• 字数: 16653字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.01407

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李永明	陕西师范大学计算机科学学院	165	505	12.0	16.0
5	李平	陕西师范大学数学与信息科学学院	26	31	3.0	4.0