Embedding recursive functions in universal algorithms

DOI10.1080/00207168808803648MaRDI QIDQ3803097zbMATH OpenOpenAlexFDO

Authors

Publication date 1988

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168808803648

zbMATH Keywords

Kolmogorov complexitysparse setsuniversal algorithm

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A note on arbitrarily complex recursive functions
• Universal Recursively Enumerable Sets of Strings
• scientific article; zbMATH DE number 4102487
• Universal recursively enumerable sets of strings
• Algorithmically random universal algebras

Cites work

• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Strong noncomputability of random strings
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(4)

• A note on arbitrarily complex recursive functions
• Non-recursive trade-offs are ``almost everywhere
• scientific article; zbMATH DE number 3900732 (Why is no real title available?)
• scientific article; zbMATH DE number 2114136 (Why is no real title available?)

This page was built for publication: Embedding recursive functions in universal algorithms

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