The translation theorem
The paper brings new proofs for some known results concerning orbits in the lattice of recursively enumerable sets, in particular Soare's result on maximal sets and Maass's result on hyperhypersimple sets. The author claims that the new proofs should be more understandable. He shows that it suffices to construct uniformly \(0\)-recursive enumerations rather than uniformly recursive enumerations; this is ensured by the Translation Theorem (showing translation of uniformly \(0\)-recursive enumerations into uniformly recursive ones). The Translation Theorem is also used to show a modified version of Soare's Extension Theorem. In the proof of the Translation Theorem, the author follows the techniques used in his dissertation on automorphisms of the lattice of recursively enumerable sets; in particular in building a \(\Delta_ 3\)- branching tree. The author also mentions that Downey and Stob's results on hemimaximal sets and on Friedberg splittings of hyperhypersimple sets can also be recast in the format of the new proofs.
- Definable properties of the computably enumerable sets
- Some orbits for \({\mathcal E}\)
- Translation invariance and Miller's weather example
- An application of the translational method
- The Complexity of Orbits of Computably Enumerable Sets
- Extension theorems, orbits, and automorphisms of the computably enumerable sets
- scientific article; zbMATH DE number 3101016 (Why is no real title available?)
This page was built for publication: The translation theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1325048)
