Closed left-r.e. sets

DOI10.3233/COM-160054zbMath1420.03093OpenAlexW2301081474MaRDI QIDQ2964277

Sanjay Jain, Jason Teutsch, Frank Stephan

Publication date: 23 February 2017

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-160054

zbMATH Keywords

Kolmogorov complexitycohesive setsreducibilitiesleft-r.e. setsweakly 1-generic sets

Mathematics Subject Classification ID

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

Related Items

Reducibility by means of almost polynomial functions

Cites Work

• Incompleteness theorems for random reals
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Things that can be made into themselves
• Cohesive sets and recursively enumerable Dedekind cuts
• Algorithmic Randomness and Complexity
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• On the Lattice of Recursively Enumerable Sets
• Computability and Randomness
• Semirecursive Sets and Positive Reducibility
• Simplicity of recursively enumerable sets
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Recursively enumerable sets of positive integers and their decision problems
• Solution of a problem of Tarski
• An introduction to Kolmogorov complexity and its applications