Strong noncomputability of random strings

DOI10.1080/00207168208803297MaRDI QIDQ3946158zbMATH OpenOpenAlexFDO

Authors Ion Chiţescu, Cristian S. Calude

Publication date 1982

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

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

zbMATH Keywords

Kolmogorov complexityrecursively enumerable setpartial functioninfinite set of random stringspartial recursive extension

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35)

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• The definition of random sequences

Cited in

(3)

• Embedding recursive functions in universal algorithms
• Anytime algorithms for non-ending computations
• A relation between correctness and randomness in the computation of probabilistic algorithms

This page was built for publication: Strong noncomputability of random strings

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