Universal recursively enumerable sets of strings

DOI10.1016/J.TCS.2011.01.002MaRDI QIDQ533863zbMATH OpenOpenAlexWikidataFDO

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

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)

Recommendations

• Universal Recursively Enumerable Sets of Strings
• Universality probability of a prefix-free machine
• Randomness and universal machines
• On universal computably enumerable prefix codes
• RELATIVIZING CHAITIN'S HALTING PROBABILITY

Cites work

• 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?)
• 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
• Information-theoretic characterizations of recursive infinite strings
• Not every domain of a plain decompressor contains the domain of a prefix-free one
• On universal computably enumerable prefix codes
• Process complexity and effective random tests
• Randomness and recursive enumerability
• Randomness and reducibility
• Randomness and universal machines
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The definition of random sequences
• Universal Recursively Enumerable Sets of Strings
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(9)

• Embedding recursive functions in universal algorithms
• Not every domain of a plain decompressor contains the domain of a prefix-free one
• What percentage of programs halt?
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS
• scientific article; zbMATH DE number 19776 (Why is no real title available?)
• A computation model with automatic functions and relations as primitive operations
• Searching for shortest and least programs
• Universal Recursively Enumerable Sets of Strings
• scientific article; zbMATH DE number 3974323 (Why is no real title available?)

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 Q533863)