𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Degree Spectra of Relations on Computable Structures in the Presence of Δ02Isomorphisms

✍ Scribed by Denis R. Hirschfeldt

Book ID
124978615
Publisher
Association for Symbolic Logic
Year
2002
Tongue
English
Weight
505 KB
Volume
67
Category
Article
ISSN
0022-4812

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Degree spectra of relations on structure
Degree spectra of relations on structures of finite computable dimension
✍ Denis R. Hirschfeldt 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 415 KB

We show that for every computably enumerable (c.e.) degree a¿0 there is an intrinsically c.e. relation on the domain of a computable structure of computable dimension 2 whose degree spectrum is {0; a}, thus answering a question of Goncharov and Khoussainov (Dokl. Math. 55 (1997) 55-57). We also show

On the complexity of categoricity in com
On the complexity of categoricity in computable structures
✍ Walker M. White 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Π^1^~1~‐complete, while computable categoricity is Π^0^~4~‐hard. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)