Academic Journals Database
Disseminating quality controlled scientific knowledge

Turing machines based on unsharp quantum logic

Author(s): Yun Shang | Xian Lu | Ruqian Lu

Journal: Electronic Proceedings in Theoretical Computer Science
ISSN 2075-2180

Volume: 95;
Issue: Proc. QPL 2011;
Start page: 251;
Date: 2012;
Original page

In this paper, we consider Turing machines based on unsharp quantum logic. For a lattice-ordered quantum multiple-valued (MV) algebra E, we introduce E-valued non-deterministic Turing machines (ENTMs) and E-valued deterministic Turing machines (EDTMs). We discuss different E-valued recursively enumerable languages from width-first and depth-first recognition. We find that width-first recognition is equal to or less than depth-first recognition in general. The equivalence requires an underlying E value lattice to degenerate into an MV algebra. We also study variants of ENTMs. ENTMs with a classical initial state and ENTMs with a classical final state have the same power as ENTMs with quantum initial and final states. In particular, the latter can be simulated by ENTMs with classical transitions under a certain condition. Using these findings, we prove that ENTMs are not equivalent to EDTMs and that ENTMs are more powerful than EDTMs. This is a notable difference from the classical Turing machines.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Rapperswil
Tango Rapperswil