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|
|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|
|Editor:||Oxford Univ Press|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.