Orientador: Itala Maria Loffredo D'Ottaviano / Tese (doutorado) - Universidade Etsadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-07-27T20:17:27Z (GMT). No. of bitstreams: 1 ErtolaBiraben_RodolfoCristian_D.pdf: 6541731 bytes, checksum: 679633ee0bf6443f0e2e45097736869c (MD5) Previous issue date: 2001 / Resumo: Nesta Tese examinamos algumas questões relacionadas com o conceito de função computável. Entre as análises destacamos um estudo de uma objeção às definições habituais desse conceito, quanto ao caráter construtivo do mesmo. Desenvolvemos uma teoria de computabilidade onde são distinguidas as noções de auto-referência e automodificação. Além disso, estudamos uma reformulação da Tese de Turing-Church, devida a Yiannis Moschovakis / Abstract: In this Thesis we examine some problems related to the concept of computable function. In particular, we present an analysis of an objection to the usual definition as regards its constructive contentoWe also develop computability theory distinguishing selfreference and self-modification and we make an evaluation of a reformulation of Turing- Church Thesis by Yiannis Moschovakis / Doutorado / Doutor em Filosofia

Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-14T17:27:49Z (GMT). No. of bitstreams: 1 Agudelo_JuanCarlosAgudelo_D.pdf: 1223911 bytes, checksum: 92e4a3e06e1921aefd3476374d0726f2 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho levantamos, e investigamos do ponto de vista conceitual, evidências de que a complexidade algorítmica pode ser vista como relativa à lógica. Propomos, para tanto, novos modelos de computação fundados sobre lógicas não-clássicas, estudando suas características quanto à expressabilidade computacional e eficiência. A partir desta visão, sugerimos um novo caminho para estudar a eficiência dos modelos de computação quântica, enfatizando a análise de uma lógica subjacente a tais modelos. O conteúdo da tese está estruturado da seguinte maneira: no primeiro capítulo apresentamos uma análise conceitual da noção de 'computação', indicando como este conceito tem mudado desde os trabalhos fundacionais da década de 1930, e discutindo se o conceito deve ser considerado como puramente físico, puramente lógicomatemático ou uma combinação de ambos. O Capítulo 2 introduz duas versões de 'máquinas de Turing paraconsistentes', usando sistemas lógicos diferentes e obtendo modelos com diferentes poderes computacionais (quanto à eficiência); tal resultado constitui uma primeira evidência a favor da relatividade lógica da computação que queremos defender. Outra evidência na mesma direção é apresentada no Capitulo 3, através da generalização dos circuitos booleanos para lógicas não-clássicas, em particular para a lógica paraconsistente mbC e para a lógica modal S5, e da análise do poder computacional de tais generalizações. O Capítulo 4 consiste numa introdução à computação quântica, para logo (no Capítulo 5) estabelecer algumas relações entre modelos de computação quântica e modelos de computação paraconsistente, de maneira a propor uma interpretação lógica dos modelos quânticos. No capítulo final (Capítulo 6) descrevemos várias relações entre mecânica quântica e lógica paraix consistente, relações estas que sugerem potencialidades com alto grau de relevância a respeito da abordagem paraconsistente dos fenômenos computacionais quânticos e que incitam a continuar explorando esta alternativa. / 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. / Doutorado / Logica / Doutor em Filosofia

Orientador: Walter Alexandre Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-06T09:39:40Z (GMT). No. of bitstreams: 1 Agudelo_JuanCarlosAgudelo_M.pdf: 2515941 bytes, checksum: 58c117425f8731bb67cf3fc0e1181ad4 (MD5) Previous issue date: 2006 / Resumo: As diferentes interpretações da mecânica quântica levanta sérios problemas filosóficos a respeito da natureza do mundo físico e do estatuto das teorias físicas. Tais interpretações desempenham um papel importante na compreensão dos modelos de computação quântica, e por sua vez os modelos de computação quântica abrem a possibilidade de se confrontar as teses filosóficas que se atrevem a responder a tais problemas. Apesar das relevantes e surpreendentes promessas de uso pragmático e tecnológico da computação quântica, não é por essa vereda que caminha este trabalho: o que aqui se oferece é um novo paradigma de computação (um modelo de computação baseado no paradigma paraconsistente), e se propõe uma nova interpretação da computação quântica através desse novo paradigma, dessa forma colaborando simultaneamente na discussão filosófica a respeito da noção de computabilidade e da mecânica quântica. O presente trabalho introduz a definição do que será chamado de modelo de máquinas de Turing paraconsistentes (MTPs). Tal modelo de computação é uma generalização do modelo clássico de máquinas de Turing. No modelo de máquinas de Turing paraconsistentes, diferentemente do modelo clássico, permite-se a execução de múltiplas instruções de mancha simultânea, dando lugar a multiplicidade de símbolos em diferentes casas da fita, multiplicidade de estados e multiplicidade dc posições da máquina. Considerando que tal multiplicidade de configurações, embora essencial nas MTPs pode ser interpretado como incoerências com respeito às máquinas de Turing clássicas, permite-se acrescentar condições de consistência e inconsistência na execução das instruções nas MTPs. o que servirá então para controlar o estado dc incoerência do sistema. Depois de apresentar o modelo de MTPs, são descritos os modelo de máquinas de Turing quânticas (MTQs) e o modelo dc circuitos quânticos (CQs), ambos introduzidos inicialmente por David Dcutsch. os quais são, respectivamente, generalizações do modelo de máquinas dc Turing clássicas e de circuitos boolcanos clássicos usando as leis da mecânica quântica. Finalmente, estabelecem-se relações entre o modelo de MTPs e os modelos de computação quântica, simulando algoritmos quânticos simples (um CQ que soluciona o chamado problema de Dcutsch e um CQ que soluciona o chamado problema de Deutsch-Josza) e mostrando que o paralelismo quântico, uma característica essencial da computação quântica., pode em alguns casos ser simulado por meio de MTPs. Dessa forma, apesar de o particular modelo de MTPs aqui apresentado ter algumas restrições na simulação de certas características da computação quântica, abre-se a possibilidade de se definir outros modelos de MTPs de maneira a simular tais características. Em resumo, o presente trabalho, na medida cm que oferece um novo paradigma de computação (a saber, a computação paraconsistente) e uma nova interpretação dos modelos de computação quântica (a saber, a interpretação da computação quântica através da computação paraconsistente) contribui para a discussão filosófica a respeito da interpretação dos modelos de computação quântica, e possivelmente da interpretação da própria mecânica quântica. Contudo, não menos importante é o fato de que, apesar de o presente trabalho não pretender se dedicar a questões puramente técnicas da computabilidade, ele de fato abre um imenso campo de investigação a respeito da computação relativizada à lógica e suas implicações - no caso presente, relativizada à lógica paraconsistente / Abstract: The interpretations of quantum mechanics open serious philosophical questions about the nature of the physical world and about the status of physical theories. Such interpretations play an important role in the understanding of models of quantum computing, and models of quantum computing, by their turn, open possibilities to confront and test philosophical theses that dare to address such problems. Although the promising pragmatic and technological applications of quantum computing, this work goes in another way: what is here offered is a new paradigm of computation based upon the pa-raconsistency paradigm, and a new interpretation of quantum computing through this model, in this way simultaneously collaborating in the philosophical discussion about the concepts of computability and of quantum mechanics. This work introduces the definition of what will be called the model of paraconsistent Turing machines (PTMs). Such computational model is a generalization of the classical model of Turing machines. In the PTMs model, differently from the classical Turing machines model, simultaneous execution of multiple instructions is allowed, giving rise to a multiplicity of symbols on different cells of the tape, multiplicity of machine states and multiplicity of machine positions. Such multiplicity of configurations, though essential in the PTMs. can be seen as incoherencies with respect to classical Turing machines: to compensate this, the PTMs permit to operate with consistency and inconsistency conditions to control the global state of incoherence of the system. After introducing the PTMs, the model of quantum Turing machines (QTMs) and the model of quantum circuits (QCs) arc presented. This models arc due to David Dcutsch and arc. respectively, generalizations of the model of classical Turing machines and the model of classical boolean circuits, using the laws of quantum mechanics. Finally, relations between the model of PTMs and models of quantum computing arc established, which permits to simulate simple quantum algorithms (a QC to solve the so called Dcutsch problem and a QC to solve the so called Dcutsch-Jozsa. problem) by PTMs. It is also shown that quantum parallelism, an essential characteristic of quantum computation, may be simulated in some cases by PTMs. Although the particular model of PTMs here presented has some restrictions in the capacity to simulate certain quantum computing characteristics, our work opens the possibility to define other PTM models which could simulate such characteristics. To sum up, the present work, while offering a new paradigm of computation (namely, parconsistent computation) and a new interpretation of quantum computing (namely, interpretation of quantum computation by means of paraconsistent computation) contributes to the philosophical discussion about the interpretation of quantum computation and of the quantum mechanics itself. However, not less important is the fact that, besides its lack of explicit intention towards tccnical questions of computability theory, opens a new line of research about the possibilities of logic-relativized computation and its implications- in the present case, relativized to paraconsistent logics / Mestrado / Logica / Mestre em Filosofia