Universal Recursively Enumerable Sets of Strings

DOI10.1007/978-3-540-85780-8_13MaRDI QIDQ3533008zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• Universal recursively enumerable sets of strings
• Completely recursively enumerable sets
• Enumerating the strings of regular languages
• A class of recursively enumerable sets
• scientific article; zbMATH DE number 3974323
• Recursively EnumerableL-Sets
• scientific article; zbMATH DE number 3954889
• On a Class of Recursively Enumerable Sets
• On recursively enumerable structures
• scientific article; zbMATH DE number 4210127

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computability and Randomness
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• Information-theoretic characterizations of recursive infinite strings
• On universal computably enumerable prefix codes
• Process complexity and effective random tests
• Randomness and recursive enumerability
• Randomness and reducibility
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The definition of random sequences

Cited in

(10)

• Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets
• A computation model with automatic functions and relations as primitive operations
• Universality probability of a prefix-free machine
• On universal computably enumerable prefix codes
• scientific article; zbMATH DE number 3974323 (Why is no real title available?)
• Embedding recursive functions in universal algorithms
• scientific article; zbMATH DE number 19776 (Why is no real title available?)
• Universal recursively enumerable sets of strings
• Simplicity via provability for universal prefix-free Turing machines
• Not every domain of a plain decompressor contains the domain of a prefix-free one

This page was built for publication: Universal Recursively Enumerable Sets of Strings

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