The computing power of Turing machine based on quantum logic
Yun Shang, Xian Ping Lu, Ruqian Lu
Turing machines based on quantum logic can solve undecidable problems. In this paper we will give recursion-theoretical characterization of the computational power of this kind of quantum Turing machines. In detail, for the unsharp case, it is proved that Σ01 ∪Π01⊆ LTd(ε,Σ)(LTw(ε,Σ))⊆Π02 when the truth value lattice is locally finite and the operation ∧ is computable, where LTd(ε,Σ)(LTw(ε,Σ))denotes the class of quantum language accepted by these Turing machine in depth-first model (respectively, width-first model); for the sharp case, we can obtain similar results for usual orthomodular lattices.
EPiC series in computing•Jan 23, 2018•0 citations