View Related Documents

Abstract

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can’t be recognized by a deterministic real - time Turing machine, is shown.
Research supported by contract IST-1999-11234 (QAIP) from the European Commision, and grant no. 01.0354 from the Latvian Council of Science.

Fulltext Preview

Image of the first page of the fulltext document