Weakly useful sequences

DOI10.1007/3-540-60084-1_91zbMath1412.68092OpenAlexW1558033868MaRDI QIDQ4645195

Elvira Mayordomo, Jack H. Lutz, Stephen A. 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

recursive sequenceTuring degreelogical depthuniform reducibilityoracle access

Mathematics Subject Classification ID

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

Related Items (1)

Recursive computational depth.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost everywhere high nonuniform complexity
• Computational depth and reducibility
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Reachability is harder for directed than for undirected finite graphs
• Degrees in Which the Recursive Sets are Uniformly Recursive
• The definition of random sequences
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Weakly useful sequences