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

Turing Machines Based on Quantum Logic and Their Universality

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机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 recognizing quantum languages.Second,we introduce the notions of quantum recursively enumerable languages and quantum recursively languages,and the stratified characterization of them are also given.Moreover,we show that l-VTMs and l-VDTMs are not equivalent.However,they are equivalent when they accept quantum recursively languages.Which is an important differentia between quantum Turing machines and classical Turing machines.Finally,we study the existence of a universal quantum Turing machine and give a coding system.It is shown that the universal quantum Turing machine does not exist when the orthomodular lattice is infinite,and the universal quantum Turing machine exists when the orthomodular lattice is finite.