Weakly useful sequences

DOI10.1016/j.ic.2005.01.001zbMath1075.68035DBLPjournals/iandc/FennerLMR05OpenAlexW2070930582WikidataQ60578978 ScholiaQ60578978MaRDI QIDQ1776400

Niranjan Chakravarthy

Publication date: 12 May 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.01.001

zbMATH Keywords

ComputabilityResource-bounded measureRandomnessComputable measureComputational depthLogical depthRandom sequenceUsefulWeakly useful

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

Recursive computational depth ⋮ Depth as randomness deficiency

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost everywhere high nonuniform complexity
• Computational depth and reducibility
• Recursive computational depth.
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Arithmetical Measure
• Weakly Hard Problems
• Degrees in Which the Recursive Sets are Uniformly Recursive
• The definition of random sequences
• On Suborderings of Degrees of Recursive Unsolvability
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Weakly useful sequences