Automata theory based on quantum logic. I (Q1586380): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Ming Sheng Ying / rank | |||
Property / reviewed by | |||
Property / reviewed by: Q497546 / rank | |||
Property / author | |||
Property / author: Ming Sheng Ying / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Vladik Ya. Kreinovich / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 05:00, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Automata theory based on quantum logic. I |
scientific article |
Statements
Automata theory based on quantum logic. I (English)
0 references
25 February 2001
0 references
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.
0 references
quantum logic
0 references
finite automata
0 references
language recognition
0 references
quantum computing
0 references