Files in this item



application/pdf9990023.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets
Author(s):Ho, Kejia
Doctoral Committee Chair(s):Jockusch, Carl G., Jr.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:We also study connections 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 effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded if and only if B is low2. For r = bwtt, tt, wtt, and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists.
Issue Date:2000
Description:114 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2000.
Other Identifier(s):(MiAaPQ)AAI9990023
Date Available in IDEALS:2015-09-28
Date Deposited:2000

This item appears in the following Collection(s)

Item Statistics