archives

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