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.
Computational Depth and Reducibility
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.
Contact site administrator at: email@example.com