✦ LIBER ✦

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

✍ Scribed by R.P. Daley

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 622 KB
Volume: 9
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(74)80004-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 A S 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.