Paraconsistent Machines and their Relation to Quantum Computing

Autor(es)

Agudelo, Juan C. ^{[1, 2, 3]} ; Carnielli, Walter ^{[2, 4]}

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF LOGIC AND COMPUTATION; v. 20, n. 2, p. 573-595, APR 2010.
• Citações Web of Science: 6

Resumo

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)

• Processo FAPESP: 04/14107-2 - Logical consequence and combinations of logics: fundaments and efficient applications
• Beneficiário: Walter Alexandre Carnielli
• Modalidade de apoio: Auxílio à Pesquisa - Temático