𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Analogues of Chaitinʼs Omega in the computably enumerable sets

✍ Scribed by Barmpalias, G.; Hölzl, R.; Lewis, A.E.M.; Merkle, W.

Book ID
123568193
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
210 KB
Volume
113
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Undecidability and 1-types in intervals
Undecidability and 1-types in intervals of the computably enumerable degrees
✍ Klaus Ambos-Spies; Denis R. Hirschfeldt; Richard A. Shore 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 338 KB

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

Coding in the Partial Order of Enumerabl
Coding in the Partial Order of Enumerable Sets
✍ Leo Harrington; André Nies 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 489 KB

We develop methods for coding with first-order formulas into the partial order E of enumerable sets under inclusion. First we use them to reprove and generalize the (unpublished) result of the first author that the elementary theory of E has the same computational complexity as the theory of the nat