Universal recursively enumerable sets of strings

DOI10.1016/J.TCS.2011.01.002zbMATH Open1217.68115OpenAlexW2016785920WikidataQ57001541 ScholiaQ57001541MaRDI QIDQ533863FDOQ533863

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

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

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)

Cites Work

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

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
• A computation model with automatic functions and relations as primitive operations
• Searching for shortest and least programs
• Title not available (Why is that?)
• Universal Recursively Enumerable Sets of Strings
• Title not available (Why is that?)

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)