Computational depth and reducibility
- 26 September 1994
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 132 (1-2) , 37-70
- https://doi.org/10.1016/0304-3975(94)00014-x
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- On Languages Reducible to Algorithmically Random LanguagesSIAM Journal on Computing, 1994
- An observation on probability versus randomness with applications to complexity classesTheory of Computing Systems, 1994
- Incompleteness theorems for random realsAdvances in Applied Mathematics, 1987
- Every sequence is reducible to a random oneInformation and Control, 1986
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Families of recursive predicates of measure zeroJournal of Mathematical Sciences, 1976
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1969
- Logical basis for information theory and probability theoryIEEE Transactions on Information Theory, 1968
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966