Strong noncomputability of random strings

DOI10.1080/00207168208803297zbMath0486.03026OpenAlexW1973060803MaRDI QIDQ3946158

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)

Related Items (3)

Anytime Algorithms for Non-Ending Computations ⋮ Embedding recursive functions in universal algorithms ⋮ A relation between correctness and randomness in the computation of probabilistic algorithms

Cites Work

• The definition of random sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item

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