Paraconsisted computation: a logic approach to quantum

Author(s)

Juan Carlos Agudelo Agudelo

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Filosofia e Ciências Humanas
• Defense date: 2009-11-19

Examining board members

Walter Alexandre Carnielli; Marcelo Esteban Coniglio; Marcelo Finger; Marcos César de Oliveira; Osvaldo Pessoa Junior

• Advisor: Walter Alexandre Carnielli

Abstract

This work provides evidences to view computational complexity as logic-relative, by introducing new models of computation through non-classical logics and by studying their features with respect to computational expressivity and efficiency. From this point of view, we suggest a new way to study the efficiency of quantum computational models consisting in the analysis of an underlying logic. The contents of the thesis is structured in the following way: the first chapter presents a conceptual analysis of the notion of 'computation', showing how this concept evolved since the decade of 1930 and discussing whether it can be considered a pure physical or a pure logic-mathematical concept, or a combination of both paradigms. Chapter 2 introduces two versions of 'paraconsistent Turing machines', by considering different logic systems and obtaining models with different computational capabilities (with respect to efficiency); such a result constitute a first evidence in favor of the logical relativity of computation that we are defending here. Another evidence in the same direction is presented in Chapter 3 through a generalization of boolean circuits to non-classical logics, particularly for the paraconsistent logic mbC and for the modal logic S5, and by analyzing the computational power of such generalizations. Chapter 4 consists in an introduction to quantum computation. This is used in Chapter 5 to establish some relationships between quantum and paraconsistent models of computation, in order to propose a logic interpretation of quantum models. The final chapter (Chapter 6) describes several connections between quantum mechanics and paraconsistent logic; such relationship suggests highly relevant potentialities in favor of the paraconsistent approach to quantum computation phenomena encouraging to continue exploring this alternative. (AU)