Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets
type: CreativeWork
description: 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.
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.
author: Ho, Kejia
language: eng
keywords: Computer Science
date published: 2015-09-28T15:20:33Z
date modified: 2026-07-22T22:26:28Z
provider: University of Illinois - Urbana-Champaign
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Illinois at Urbana-Champaign

PropertyValue
property ID: Handle
value: http://hdl.handle.net/2142/87001