Paraconsistent Machines and their Relation to Quantum Computing

DOI10.1093/LOGCOM/EXP072MaRDI QIDQ3553921zbMATH OpenOpenAlexFDO

Authors Juan C. Agudelo, Walter Carnielli

Publication date 21 April 2010

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.0150

zbMATH Keywords

Deutsch's problemDeutsch-Jozsa problementangled statesparaconsistent computationparaconsistent Turing machinesquantum computation

Mathematics Subject Classification ID

Paraconsistent logics (03B53) Turing machines and related notions (03D10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

Abstract: We describe a method to axiomatize computations in deterministic Turing machines. When applied to computations in non-deterministic Turing machines, 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 Turing machines is defined, which better approaches quantum computing features. Finally, we define complexity classes for such models, and establish some relationships with classical complexity classes.

Recommendations

• Paraconsistent computation and dialetheic machines
• Abstract quantum computing machines and quantum computational logics
• Paraconsistent ideas in quantum logic
• Theory of quanputers
• Proof theory of paraconsistent quantum logic
• scientific article; zbMATH DE number 1951198
• Quantum and Classical Structures in Nondeterminstic Computation
• scientific article; zbMATH DE number 1421018
• Reversible computation, quantum computation, and computer architectures in between

Cited in

(13)

• Multimodal incompleteness under weak negations
• Are the foundations of computer science logic-dependent?
• Unconventional Models of Computation Through Non-standard Logic Circuits
• On the logical relativity of quantum computability
• A Not So Impossible Machine Based on the GHZ Paradox
• Paraconsistent computation and dialetheic machines
• On the philosophy and mathematics of the logics of formal inconsistency
• scientific article; zbMATH DE number 2226385 (Why is no real title available?)
• Paraconsistent Transition Systems
• Paraconsistent relations as a variant of Kleene algebras
• Paraconsistent transition structures: compositional principles and a modal logic
• Where the truth lies: a paraconsistent approach to Bayesian epistemology
• A note on the strength of paraconsistent arithmetic

This page was built for publication: Paraconsistent Machines and their Relation to Quantum Computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3553921)