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"”.
-
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, …
-
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 …
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 2