Recursively enumerable generic sets

Summary

This work shows that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes, and leads to a new class of recursively enumerable sets: r.e. generic sets.

Keywords

Recursively enumerable set, Recursively enumerable language, Maximal set, Simple (philosophy), Class (philosophy)

References

Automorphisms of the lattice of recursively enumerable setsRobert I. Soare — 1974
d-simple sets, small sets, and degree classesManuel Lerman, Robert I. Soare — 1980
Computational complexity, speedable and levelable setsRobert I. Soare — 1977
Automorphisms of the Lattice of Recursively Enumerable Sets Part I: Maximal SetsRobert I. Soare — 1974
Theory of Recursive Functions and Effective Computability.Solomon Feferman, Hartley Rogers — 1969
Theory of Recursive Functions and Effective ComputabilityR. L. Goodstein — 1969
Theory of Recursive Functions and Effective ComputabilityJr. Hartley Rogers — 1987

Cited by

The Δ₃⁰-automorphism method and noninvariant classes of degreesLeo Harrington, Robert I. Soare — 1996
Computability and randomnessAndré Nies — 2009
Subsets of hypersimple sets.Rodney G. Downey — 1987
The role of true finiteness in the admissible recursively enumerable degreesNoam Greenberg — 2006
A minimal pair joining to a plus cupping Turing degreeDengfeng Li, Angsheng Li — 2003
An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degreesKlaus Ambos‐Spies, Carl G. Jockusch, Richard A. Shore — 1984
Definable Properties of the Computably Enumerable SetsLeo Harrington, Robert I. Soare — 1998
Permutations and presentationsPeter Cholak, Rod Downey — 1994
On orbits, of prompt and low computably enumerable setsKevin Wald — 2002
Automorphisms of the lattice of recursively enumerable sets. Part II: Low setsRobert I. Soare — 1982
Diagonalizations over Polynomial Time Computable SetsKlaus Ambos‐Spies, Hans Fleischhack, Hagen Huwig — 1987
The quotient semilattice of the recursively enumerable degrees modulo the cappable degreesSteven Schwarz — 1984
Some orbits for EPeter Cholak, Rod Downey, Eberhard Herrmann — 2001
Variations on promptly simple setsWolfgang Maass — 1985
On a conjecture of LemppAngsheng Li — 2000
Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable setsWolfgang Maass — 1983
Computational Complexity of Recursively Enumerable SetsRobert I. Soare — 1982
Presentations of computably enumerable realsRodney G. Downey, Geoffrey Laforte — 2002
Bounding computably enumerable degrees in the Ershov hierarchyAngsheng Li, Guohua Wu, Yue Yang — 2006
Splitting Theorems in Recursion TheoryRod Downey, Michael Stob — 1993

Related papers

A Non-Splitting Theorem for d.r.e. SetsXiaoding Yi — 1996
The Density of Infima in the Recursively Enumerable DegreesTheodore A. Slaman — 1991
On sQ-completeness of recursively enumerable setsR. Sh. Omanadze — 1992
The class of recursively enumerable subsets of a recursively enumerable setLouise Hay — 1973
On recursive enumerability with finite repetitionsStephan Wehner — 1999
Complexity properties of recursively enumerable sets andsQ-completenessR. Sh. Omanadze — 1997
A simple set which is not effectively simpleGerald E. Sacks — 1964
The Structures Inside Turing Degrees of Recursively Enumerable Generic Sets丁德成 — 1993
Variants of P Colonies with Very Simple Cell StructureLucie Ciencialová, Erzsébet Csuhaj-Varjú, Alica Kelemenová — 2009