Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Paraconsistent Machines and their Relation to Quantum Computing
Author: Agudelo, JC
Carnielli, W
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.
Subject: Paraconsistent Turing machines
paraconsistent computation
quantum computation
Deutsch's problem
Deutsch-Jozsa problem
entangled states
Country: Inglaterra
Editor: Oxford Univ Press
Rights: fechado
Identifier DOI: 10.1093/logcom/exp072
Date Issue: 2010
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000276843800008.pdf335.06 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.