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 9 of 9 for “"computably enumerable"”.
-
Computably enumerable boolean algebras
We study computably enumerable boolean algebras, focusing on Stone duality and universality phenomena. We show how classical Stone duality specializes to c.e. boolean algebras, giving a natural bijection between c.e. boolean algebras and $\Pi^0_1$ classes. We also give a new characterization of …
-
Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets
… between strong reducibilities and properties of computably enumerable sets such as simplicity. We call a class S of computably enumerable sets bounded if there is an m-incomplete computably enumerable set A such that every set in S is m-reducible to A. For example, we show that the class of …
-
Lachlan Non-Splitting Pairs and High Computably Enumerable Turing Degrees
A given c.e. degree a > 0 has a non-trivial splitting into c.e. degrees v and w if a is the join of v and w and v | w. A Lachlan Non-Splitting Pair is a pair of c.e. degrees <a,d> such that a > d and there is no non-trivial splitting of a into c.e. degrees w and v with w > d and v > d. Lachlan …
-
Degrees of Categoricity and the Isomorphism Problem
… it is known that every degree that is of a computably enumerable (c.e.) set\ in and above $\mathbf{0}^{(\alpha)}$, for $\alpha$ a successor ordinal, is a degree of categoricity. In this thesis, we include joint work with Csima, Deveau and Harrison-Trainor which shows that every degree c.e.\ …
-
TURNING DEGREES CONSTRUCTIONS AND THEIR INDUCTION STRENGTH IN REVERSE MATHEMATICS
… decomposition of R where R denotes the class of computably enumerable degrees. Ambos-Spies et al. (1984) proved that R = M \cup PS. We first define another subclass of R, STB, which consists of 0 together with all degrees for the base (set) in any Slaman triple. We will show R = STB \cup PS in …
-
Toward a molecular programming language for algorithmic self-assembly
… series of computations that characterize computably enumerable and decidable languages, and exhibit tools for algorithmically generating the necessary sets of tiles. In the next chapter, methods for generating tile sets which self-assemble into complicated shapes, namely a class of …
-
Computability Theory and Some Applications
… Mahmoud), the set of degrees that are computably enumerable in and above $\mathbf{0}^{(\alpha)}$ are shown to be degrees of categoricity of a structure, where $\alpha$ is a computable limit ordinal. We construct such structures in a particularly useful way: by restricting the …
-
Universality in algorithmic self-assembly
… first establish a novel characterization of the computably enumerable languages in terms of self-assembly--the proof of which is a novel proof of the Turing-universality of the Tile Assembly Model in which a particular Turing machine is simulated on all inputs in parallel in the two-dimensional …
-
Noncomputable Spectral Sets
… the jump operator. We show that in the world of computably enumerable sets, nondeterminism contributes nothing to immunity. In this respect, the jump operator outshines nondeterminism. Nonetheless, we can ascend naturally from the lowest level of the spectral hierarchy using nondeterminism. …