Computation of recursive functionals using minimal initial segments

DOI10.1016/0304-3975(83)90036-1zbMath0531.03022OpenAlexW2052114327MaRDI QIDQ787965

Eliahu Shamir, Dan Gordon

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90036-1

zbMATH Keywords

algorithmic information theoryMartin-Löf testamount of informationrecursive functional

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Information theory (general) (94A15)

Related Items

How much partiality is needed for a theory of computability? ⋮ Minimal determining sets of locally finitely-determined functionals ⋮ Type 2 computational complexity of functions on Cantor's space

Cites Work

• Minimal determining sets of locally finitely-determined functionals
• On the sequential nature of functions
• On degrees of unsolvability
• A Machine-Independent Theory of the Complexity of Recursive Functions
• An Overview of the Theory of Computational Complexity
• The definition of random sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item