Skip Navigation



Journal of Logic and Computation Advance Access published online on November 10, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp072
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Agudelo, J. C.
Right arrow Articles by Carnielli, W.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Paraconsistent Machines and their Relation to Quantum Computing

Juan C. Agudelo, Ph.D.

Program in Philosophy, area of Logic, IFCH and Group for Applied and Theoretical Logic–CLE, State University of Campinas–UNICAMP, Brazil. Logic and Computation Research Group, Eafit University, Colombia.
E-mail: juca.agudelo{at}gmail.com

Walter Carnielli

IFCH and Group for Applied and Theoretical Logic–CLE, State University of Campinas–UNICAMP, Brazil. Security and Quantum Information Group–IT, Lisbon, Portugal.
E-mail: walter.carnielli{at}gmail.com

Received 22 July 2008.


  Abstract

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.

Keywords: Paraconsistent Turing machines; paraconsistent computation; quantum computation; Deutsch's problem; Deutsch-Jozsa problem; entangled states


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.