期刊论文

Turing Machines Based on Quantum Logic and Their Universality

Li, Y.-M.(liyongm@snnu.edu.cn)

中文

计算机学报

Chinese Journal of Computers

0254-4164

2012

35

7

1407-1420

10.3724/SP.J.1016.2012.01407

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

本校为其他机构

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

Automata theory based on quantum logic is an important aspect of the quantum computing models. First we study Turing machines based on quantum logic (quantum Turing machines, for short) and their variants, the notions including nondeterministic quantum Turing machines l-VTM, deterministic quantum Turing machines l-VDTM and multi-tape quantum Turing machines are introduced. Two methods to recognize quantum languages by quantum Turings machines are given, which are based on depth-first technique and on width-first technique, respectively, it is shown that these two methods are not equivalent in ...