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"”.

  1. 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 …

    cornell Repository record for Computably enumerable boolean algebras (opens in a new tab)

  2. 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 …

    uiuc Repository record for Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets (opens in a new tab)

  3. 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 …

    whiterose Download PDF for Lachlan Non-Splitting Pairs and High Computably Enumerable Turing Degrees (opens in a new tab)

  4. 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.\ …

    waterloo Repository record for Degrees of Categoricity and the Isomorphism Problem (opens in a new tab)

  5. 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 …

    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)

  6. 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 …

    iastate Repository record for Toward a molecular programming language for algorithmic self-assembly (opens in a new tab)

  7. 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 …

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

  8. 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 …

    iastate Repository record for Universality in algorithmic self-assembly (opens in a new tab)

  9. 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. …

    iu Repository record for Noncomputable Spectral Sets (opens in a new tab)