Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas / Made available in DSpace on 2018-08-17T17:02:46Z (GMT). No. of bitstreams: 1 Araujo_Anderson_D.pdf: 1286485 bytes, checksum: 1e51db7a5721f4affeaf8f512d23269e (MD5) Previous issue date: 2011 / Resumo: Esta tese propõe uma nova abordagem da computabilidade de Turing clássica, denominada abordagem modelo-teórica. De acordo com essa abordagem, estruturas e teorias são associadas às máquinas de Turing a fim de investigar as características de suas computações. Uma abordagem modelo-teórica da computabilidade de Turing através da lógica de primeira ordem é desenvolvida, e resultados de correspondência, correção, representação e completude entre máquinas, estruturas e teorias de Turing são demonstrados. Nessa direção, os resultados obtidos a respeito de propriedades tais como estabilidade, absoluticidade, universalidade e logicidade enfatizam as potencialidades da computabilidade modelo-teórica de primeira ordem. Demonstra-se que a lógica subjacente às teorias de Turing é uma lógica minimal intuicio-nista, sendo capaz, inclusive, de internalizar um operador de negação clássico. As técnicas formuladas nesta tese permitem, sobretudo, investigar a computabilidade de Turing em modelos não-padrão da aritmética. Nesse contexto, uma nova perspectiva acerca do fenômeno de Tennenbaum e uma avaliação crítica da abordagem de Dershowitz e Gurevich da tese de Church-Turing sào apresentadas. Como conseqüência, postula-se um princípio de interna-lidade aritmética na computabilidade, segundo o qual o próprio conceito de computação é relativo ao modelo aritmético em que as máquinas de Turing operam. Assim, a tese unifica as caracterizações modelo-aritméticas do problema P versus NP existentes na literatura, revelando, por fim, uma barreira modelo-aritmética para a possibilidade de solução desse problema central em complexidade computacional no que diz respeito a certos métodos. Em sua totalidade, a tese sustenta que características cruciais do conceito de computação podem ser vislumbradas a partir da dualidade entre finitude e infinitude presente na distinção entre números naturais padrão e não-padrão / Abstract: This PhD thesis proposes a new approach to classical Turing computability, called a model-theoretic approach. In that approach, structures and theories are associated to Turing machines in order to study the characteristics of their computations. A model-theoretic approach to Turing computability through first-order logic is developed, and first results about correspondence, soundness, representation and completeness among Turing machines, structures and theories are proved. In this line, the results about properties as stability, absoluteness, universality and logicality emphasize the importance of the model-theoretic standpoint. It is shown that the underlying logic of Turing theories is a minimal intuicionistic logic, being able to internalize a classical negation operator. The techniques obtained in the present dissertation permit us to examine the Turing computability over nonstandard models of arithmetic as well. In this context, a new perspective about Tennenbaum's phenomenon and a critical evaluation of Dershowitz and Gurevich's account on Church-Turing's thesis are given. As a consequence, an arithmetic internality principle is postulated, according to which the concept of computation itself is relative to the arithmetic model that Turing machines operate. In this way, the dissertation unifies the existing model-arithmetic characterizations of the P versus NP problem, leading, as a by-product, to a model-arithmetic barrier to the solvability of that central problem in computational complexity with respect to certain techniques. As a whole, the dissertation sustains that crucial characteristics of the concept of computation may be understood from the duality between finiteness and infiniteness inherent within the distinction between standard and nonstandard natural numbers / Doutorado / Filosofia / Doutor em Filosofia

Orientador: Itala Maria Loffredo D'Ottaviano / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas / Made available in DSpace on 2018-08-24T01:21:05Z (GMT). No. of bitstreams: 1 Suguitani_LeandroOliva_D.pdf: 1496205 bytes, checksum: 6197787056972a0020750fa2c72c9cd6 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The complete abstract is available with the full electronic document. / Doutorado / Filosofia / Doutor em Filosofia

Orientador: Walter Alexandre Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas / Made available in DSpace on 2018-08-25T21:09:00Z (GMT). No. of bitstreams: 1 Almeida_HenriqueAntunes_M.pdf: 1516387 bytes, checksum: 2608439ba585a23431d2aa295b1b8876 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, abordamos o Teorema de Frege sob uma perspectiva exclusivamente técnica. Primeiramente, propomos uma caracterização geral de linguagens de segunda ordem que sejam adequadas para formalizar quaisquer teorias fregeanas ¿ teorias que resultam da introdução de um ou mais princípios de abstração a um sistema dedutivo de lógica de segunda ordem; fornecemos uma semântica e um sistema dedutivo para essas linguagens e elaboramos alguns resultados metateóricos acerca desse sistema. Em segundo lugar, apresentamos uma exposicão detalhada da prova do Teorema de Frege, enunciado como uma relação entre a Aritmética de Frege e a Aritmética de Dedekind-Peano. Por fim, provamos a equiconsistência entre essas teorias e a Aritmética de Peano de Segunda Ordem / Abstract: In this work, we discuss Frege¿s Theorem under an exclusively technical perspective. First, we propose a general caracterization of second-order languages suitable to formalize all Fregean theories ¿ theories that result from the introduction of one or more abstraction principles to a deductive system of second-order logic; we also furnish a semantics and a deductive system for these languages and establish a few metatheorical results about the system. Second, we present a detailed proof of Frege¿s Theorem, formulated as a relation between Frege¿s Arithmetic and Dedekind-Peano Arithemtic. Finally, we prove the equiconsistency between these theories and Peano Second-Order Arithmetic / Mestrado / Filosofia / Mestre em Filosofia

Mechanisation of Mathematics refers to use of computers to generate or check proofs in Mathematics. It involves translation of relevant mathematical theories from one system of logic to another, to render these theories implementable in a computer. This process is termed formalisation of mathematics. Two among the many ways of mechanising are: 1 Generating results using automated theorem provers. 2 Interactive theorem proving in a proof assistant which involves a combination of user intervention and automation. In the first part of this thesis, we reformulate the question of equivalence of two Links in first order logic using braid groups. This is achieved by developing a set of axioms whose canonical model is the braid group on infinite strands B∞. This renders the problem of distinguishing knots and links, amenable to implementation in first order logic based automated theorem provers. We further state and prove results pertaining to models of braid axioms. The second part of the thesis deals with formalising knot Theory in Higher Order Logic using the interactive proof assistant -Isabelle. We formulate equivalence of links in higher order logic. We obtain a construction of Kauffman bracket in the interactive proof assistant called Isabelle proof assistant. We further obtain a machine checked proof of invariance of Kauffman bracket.