Universal Recursively Enumerable Sets of Strings
From MaRDI portal
Publication:3533008
DOI10.1007/978-3-540-85780-8_13zbMath1159.68011DBLPconf/dlt/CaludeNSS08OpenAlexW1953530293WikidataQ57001614 ScholiaQ57001614MaRDI QIDQ3533008
André Nies, Ludwig Staiger, Cristian S. Calude, Frank Stephan
Publication date: 30 October 2008
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_13
Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)
Related Items (4)
A computation model with automatic functions and relations as primitive operations ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ Not every domain of a plain decompressor contains the domain of a prefix-free one ⋮ Universal recursively enumerable sets of strings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Randomness and Recursive Enumerability
- Kolmogorov complexity and the Recursion Theorem
- On universal computably enumerable prefix codes
- A Theory of Program Size Formally Identical to Information Theory
- Algorithmic Information Theory
- Computability and Randomness
- The definition of random sequences
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
This page was built for publication: Universal Recursively Enumerable Sets of Strings
