Computation of recursive functionals using minimal initial segments

DOI10.1016/0304-3975(83)90036-1zbMATH Open0531.03022OpenAlexW2052114327MaRDI QIDQ787965FDOQ787965

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

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

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)

Cites Work

• Title not available (Why is that?)
• The definition of random sequences
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On degrees of unsolvability
• Title not available (Why is that?)
• An Overview of the Theory of Computational Complexity
• Minimal determining sets of locally finitely-determined functionals
• On the sequential nature of functions
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• How much partiality is needed for a theory of computability?
• Title not available (Why is that?)
• Minimal determining sets of locally finitely-determined functionals
• Type 2 computational complexity of functions on Cantor's space

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)