Computational Depth and Reducibility
|
Home About Browse Search Register Subscriptions Deposit Papers Help |
Juedes, David W., Lathrop, James I. and Lutz, Jack H. (1992) Computational Depth and Reducibility. Technical Report TR92-33, Department of Computer Science, Iowa State University.
| Full text available as: | Postscript Adobe PDF |
Abstract
Computational Depth and Reducibility by David W. Juedes, James I. Lathrop, and Jack H. Lutz This paper investigates Bennett's notions of strong and weak computational depth (also called logical depth) for infinite binary sequences. Roughly, an infinite binary sequence x is defined to be weakly useful if every element of a non-negligible set of decidable sequences is reducible to x in recursively bounded time. It is shown that every weakly useful sequence is strongly deep. This result (which generalizes Bennett's observation that the halting problem is strongly deep) implies that every high Turing degree contains strongly deep sequences. It is also shown that, in the sense of Baire category, almost every infinite binary sequence is weakly deep, but not strongly deep.
| Subjects: | All uncategorized technical reports |
| ID code: | 00000036 |
| Deposited by: | Staff Account on 16 November 1992 |
Contact site administrator at: ssg@cs.iastate.edu