Weakly useful sequences

DOI10.1007/3-540-60084-1_91MaRDI QIDQ4645195zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz, Elvira Mayordomo, S. Fenner

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_91

zbMATH Keywords

logical depthoracle accessrecursive sequenceTuring degreeuniform reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Weakly useful sequences
• Computational depth and reducibility
• Computational depth and reducibility
• Recursive computational depth
• Recursive computational depth.

Cites work

• Almost everywhere high nonuniform complexity
• Computational depth and reducibility
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Degrees of members of \(\Pi_ 1^ 0\) classes
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 193560 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• Reachability is harder for directed than for undirected finite graphs
• Recursively enumerable sets of positive integers and their decision problems
• The definition of random sequences

Cited in

(4)

• Weakly useful sequences
• Recursive computational depth.
• Recursive computational depth
• Computational depth and reducibility

This page was built for publication: Weakly useful sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645195)