Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 32 for “"computability theory"”.

  1. Computability Theory and Some Applications

    We explore various areas of computability theory, ranging from applications in computable structure theory primarily focused on problems about computing isomorphisms, to a number of new results regarding the degree-theoretic notion of the bounded Turing hierarchy. In Chapter 2 (joint with Csima, …

    waterloo Repository record for Computability Theory and Some Applications (opens in a new tab)

  2. Partition Theorems and Computability Theory

    "We also study Ramsey degrees, i.e. those Turing degrees which are able to compute homogeneous sets for every computable 2-coloring of pairs of natural numbers, in an attempt to further understand the effective content of Ramsey's Theorem for exponent 2. We establish some new results about these …

    uiuc Repository record for Partition Theorems and Computability Theory (opens in a new tab)

  3. Partial functions and recursion in univalent type theory

    We investigate partial functions and computability theory from within a constructive, univalent type theory. The focus is on placing computability into a larger mathematical context, rather than on a complete development of computability theory. We begin with a treatment of partial functions, using …

    birmingham Download PDF for Partial functions and recursion in univalent type theory (opens in a new tab)

  4. Notions of Semicomputability in Topological Algebras over the Reals

    Several results from classical computability theory (computability over discrete structures such as the natural numbers and strings over finite alphabets, due to Turing, Church, Kleene and others) have been shown to hold for a generalisation of computability theory over total abstract algebras, …

    mcmaster Repository record for Notions of Semicomputability in Topological Algebras over the Reals (opens in a new tab)

  5. Embedding Theorem for the automorphism group of the α-enumeration degrees

    It is a theorem of classical Computability Theory that the automorphism group of the enumeration degrees D_e embeds into the automorphism group of the Turing degrees D_T . This follows from the following three statements: 1. D_T embeds to D_e , 2. D_T is an automorphism base for D_e, 3. D_T is …

    whiterose Download PDF for Embedding Theorem for the automorphism group of the α-enumeration degrees (opens in a new tab)

  6. Computable Reducibility of Equivalence Relations

    … to those doing Borel equivalence relation theory, computability theory, and computable structure theory. In this thesis, we compare many naturally occurring equivalence relations with respect to computable reducibility. We will then define a jump operator on equivalence relations and study …

    boise Repository record for Computable Reducibility of Equivalence Relations (opens in a new tab)

  7. Notions and applications of algorithmic randomness

    Algorithmic randomness uses computability theory to define notions of randomness for infinite objects such as infinite binary sequences. The different possible definitions lead to a hierarchy of randomness notions. In this thesis we study this hierarchy, focussing in particular on Martin-Lof …

    whiterose Download PDF for Notions and applications of algorithmic randomness (opens in a new tab)

  8. Properties of difference inclusions with computable reachable set

    … instead of approximately safe or unsafe. The theory of computation (or computability theory) can be used to investigate whether computer algorithms can determine weather a dynamical system is provably safe. Computability theory, broadly speaking, is a field of computer science that studies …

    waterloo Repository record for Properties of difference inclusions with computable reachable set (opens in a new tab)

  9. A recursively controlled production system : an implementation of a theory

    … artificial intelligence research, and in formal computability theory. For practical purposes, a number of schemes have been proposed to effect the nondeterministic choice of productions. These control techniques are often domain dependent and imbedded in the interpreter; thus, reducing the …

    ubc Repository record for A recursively controlled production system : an implementation of a theory (opens in a new tab) Download PDF for A recursively controlled production system : an implementation of a theory (opens in a new tab)

  10. TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS

    … study Turing degrees in the context of classical computability theory (recursion Theory) and reverse recursion theory. In the first part, we prove that P + \Sigma_1 Induction proves the existence of isolated d.c.e. degrees and upper isolated d.c.e. degrees. We also prove that P + \Sigma_3 …

    nus Repository record for TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS (opens in a new tab) Download file for TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS (opens in a new tab)

  11. Formalizing Abstract Computability: Turing Categories in Coq

    … extensively studied using traditional tools of computability theory. However, with the development of category-theoretic methods it has become possible to study recursion in a more general (abstract) sense. The particular model this thesis is structured around is known as a Turing category. The …

    ottawa-retro Repository record for Formalizing Abstract Computability: Turing Categories in Coq (opens in a new tab)

  12. Some Results in Thermodynamic Formalism

    … at the intersection of dynamical systems, computability theory, and thermodynamic formalism. In the symbolic setting, we establish novel results regarding the statistical properties of equilibrium states, deriving bounds on probabilities of configurations and relating these bounds to the …

    denver Repository record for Some Results in Thermodynamic Formalism (opens in a new tab)

  13. On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree

    … connected together by the common thread of computability theory. First, we investigate a new notion of algorithmic dimension, the inescapable dimension, which lies between the effective Hausdorff and packing dimensions. We also study its generalizations, obtaining an embedding of the Turing …

    hawaii Repository record for On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree (opens in a new tab)

  14. Quantum Games, Graphs, and Gödel

    … computer science: the interplay between graph theory, computational complexity, and multiprover interactive proof systems. Specifically, we examine the connections between quantum graph properties, computability theory, and entangled nonlocal games.Building on prior work that defined quantum …

    maryland Repository record for Quantum Games, Graphs, and Gödel (opens in a new tab)

  15. Studies in Classical Behavioural Economics

    … are carried out from the perspective of Computability Theory and Computational Complexity Theory, which provide a coherent foundation for Herbert Simon's work on problem solving and for CBE in general. The second part of the thesis explores the game of Go from the perspective of problem …

    trento Repository record for Studies in Classical Behavioural Economics (opens in a new tab)

  16. The word problem and the ideal membership problem

    … unsolvable problem from outside of logic and computability theory. In terms of solvability, the word problem is equivalent to a restricted version of the membership problem.For ideals whose membership problem is solvable, computational techniques such as Grobner basis methods often can be used …

    unh-thes Repository record for The word problem and the ideal membership problem (opens in a new tab)

  17. Interpreting Gödel: Historical and Philosophical Perspectives

    … view towards logic, especially his no-class theory and the vicious circle principle. Chapter three turns attention to Gödel’s role in the development of computability theory, using it as a case study for conceptual analysis and tries to reconcile the apparent conflict concerning Gödel’s …

    kings Repository record for Interpreting Gödel: Historical and Philosophical Perspectives (opens in a new tab) Download PDF for Interpreting Gödel: Historical and Philosophical Perspectives (opens in a new tab)

  18. Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties

    In Recursion Theory (Computability Theory), we study Turing degrees in terms of their degree-theoretic properties and combinatorial properties. In this dissertation we present several results in terms of connections either between these two categories of properties or within each category. Our …

    cornell Repository record for Elements Of Classical Recursion Theory: Degree-Theoretic Properties And Combinatorial Properties (opens in a new tab)

  19. Computability and Tiling Problems

    … problems and mathematical logic, specifically computability theory. We focus on Wang prototiles, as defined in [32]. We begin by studying Domino Problems, and do not restrict ourselves to the usual problems concerning finite sets of prototiles. We first consider two domino problems: whether a …

    whiterose Download PDF for Computability and Tiling Problems (opens in a new tab)

  20. Metasemantics and fuzzy mathematics

    … against the epistemicist position, based on computability theory. Chapter 5 makes a different case for the adoption of degreed semantic frameworks, based on their (quasi-)superior treatments of the paradoxes of vagueness. Hence, the adoption of tools that allow for graded membership are …

    bristol Repository record for Metasemantics and fuzzy mathematics (opens in a new tab) Download PDF for Metasemantics and fuzzy mathematics (opens in a new tab)

Page 1 of 2