Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Paraconsistent Machines and their Relation to Quantum Computing

Full text
Agudelo, Juan C. [1, 2, 3] ; Carnielli, Walter [2, 4]
Total Authors: 2
[1] Eafit Univ, Log & Computat Res Grp, Medellin - Colombia
[2] Univ Estadual Campinas, Grp Appl & Theoret Log CLE, Campinas, SP - Brazil
[3] Univ Estadual Campinas, Program Philosophy, Area Log, IFCH, Campinas, SP - Brazil
[4] Secur & Quantum Informat Grp IT, Lisbon - Portugal
Total Affiliations: 4
Document type: Journal article
Source: JOURNAL OF LOGIC AND COMPUTATION; v. 20, n. 2, p. 573-595, APR 2010.
Web of Science Citations: 6

We describe a method to axiomatize computations in deterministic Turing machines (TMs). When applied to computations in non-deterministic TMs, this method may produce contradictory (and therefore trivial) theories, considering classical logic as the underlying logic. By substituting in such theories the underlying logic by a paraconsistent logic we define a new computation model, the paraconsistent Turing machine. This model allows a partial simulation of superposed states of quantum computing. Such a feature allows the definition of paraconsistent algorithms which solve (with some restrictions) the well-known Deutsch's and Deutsch-Jozsa problems. This first model of computation, however, does not adequately represent the notions of entangled states and relative phase, which are key features in quantum computing. In this way, a more sharpened model of paraconsistent TMs is defined, which better approaches quantum computing features. Finally, we define complexity classes for such models, and establish some relationships with classical complexity classes. (AU)

FAPESP's process: 04/14107-2 - Logical consequence and combinations of logics: fundaments and efficient applications
Grantee:Walter Alexandre Carnielli
Support type: Research Projects - Thematic Grants