Computation of recursive functionals using minimal initial segments

DOI10.1016/0304-3975(83)90036-1MaRDI QIDQ787965zbMATH OpenOpenAlexFDO

Authors Dan Gordon, Eliahu Shamir

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 theoryamount of informationrecursive functionalMartin-Löf test

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1222608
• Comparison between the complexity of a function and the complexity of its graph
• scientific article; zbMATH DE number 4102487
• On minimal-program complexity measures
• scientific article; zbMATH DE number 3557669

Cites work

• scientific article; zbMATH DE number 3480091 (Why is no real title available?)
• scientific article; zbMATH DE number 3557239 (Why is no real title available?)
• scientific article; zbMATH DE number 3433847 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• An Overview of the Theory of Computational Complexity
• Minimal determining sets of locally finitely-determined functionals
• On degrees of unsolvability
• On the sequential nature of functions
• The definition of random sequences

Cited in

(4)

• How much partiality is needed for a theory of computability?
• Type 2 computational complexity of functions on Cantor's space
• scientific article; zbMATH DE number 782018 (Why is no real title available?)
• Minimal determining sets of locally finitely-determined functionals

This page was built for publication: Computation of recursive functionals using minimal initial segments

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