Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Ho, Kejia

Contributors dc:contributor

• Jockusch, Carl G., Jr.

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI9990023

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/87001