Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Paraconsistent Machines and their Relation to Quantum Computing

Texto completo
Autor(es):
Agudelo, Juan C. [1, 2, 3] ; Carnielli, Walter [2, 4]
Número total de Autores: 2
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
Número total de Afiliações: 4
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
Linha de fomento: Auxílio à Pesquisa - Temático