Turing machines based on unsharp quantum logic

Yun Shang
Xian Lu
Ruqian Lu

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.

In Bart Jacobs, Peter Selinger and Bas Spitters: Proceedings 8th International Workshop on Quantum Physics and Logic (QPL 2011), Nijmegen, Netherlands, October 27-29, 2011, Electronic Proceedings in Theoretical Computer Science 95, pp. 251–261.
Published: 1st October 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.95.17 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org