Universal recursively enumerable sets of strings

DOI10.1016/j.tcs.2011.01.002zbMath1217.68115OpenAlexW2016785920WikidataQ57001541 ScholiaQ57001541MaRDI QIDQ533863

Frank Stephan, Ludwig Staiger, Cristian S. Calude, André Nies

Publication date: 10 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.002

zbMATH Keywords

recursively enumerable setsdomains of universal machinesuniversal machines

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (4)

What Percentage of Programs Halt? ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Searching for shortest and least programs ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Not every domain of a plain decompressor contains the domain of a prefix-free one
• Randomness and universal machines
• Classical recursion theory. The theory of functions and sets of natural numbers
• Information-theoretic characterizations of recursive infinite strings
• Randomness and reducibility
• Process complexity and effective random tests
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Randomness and Recursive Enumerability
• Kolmogorov complexity and the Recursion Theorem
• Universal Recursively Enumerable Sets of Strings
• On universal computably enumerable prefix codes
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• The definition of random sequences
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Universal recursively enumerable sets of strings