Automata theory based on quantum logic. I (Q1586380)

The notion of a finite automaton, with finitely many states and a deterministic transition, is one of the basic notions in the theory of computing. It is well known which languages are recognizable by a finite automaton, i.e., for which language \(L\), there exists a finite automaton which, for every input word \(w\), ends up in a special ``yes'' state if and only if \(w\in L\). In quantum computing, there is a natural quantum analogue of the notion of a finite automaton. However, when researchers studying quantum computing analyze recognizability by quantum finite automata, they interpret ``there exists'' and ``for every'' in the above definition in the sense of the standard (classical) logic. Since we are talking about quantum phenomena, it seems more natural to interpret ``there exists'' (i.e., disjunction) as a quantum disjunction \(\vee\), and ``for all'' as a quantum conjunction \(\wedge\). The author uses the known fact -- that \(a\vee b\) can true in quantum mechanics without \(a\) or \(b\) being absolutely true -- to prove that the new definition is indeed different from the traditionally used one: there exists a (quantum) language which is recognizable in the new sense but not in the traditional one.