The extent and density of sequences within the minimal-program complexity hierarchies

摘要

In this paper we examine the minimal-program complexity (i.e., the length of a shortest program for computing the initial segments) of recursively enumerable and Δ2 sequences. We determine bounds on the upper and lower extent of these sequences within the complexity hierarchy. Many of these bounds are the best which can be effectively specified. Also the density of these sequences within the hierarchies is investigated. Of particular interest is the construction of nonrecursive sequences which are, in a complexity sense, extremely simple and easy to compute.