✦ LIBER ✦

On the complexity of categoricity in computable structures

✍ Scribed by Walker M. White

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 192 KB
Volume: 49
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.200310066

No coin nor oath required. For personal study only.

✦ Synopsis

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)

📜 SIMILAR VOLUMES

The complexity of countable categoricity

The complexity of countable categoricity in finite languages

✍ Aleksander Ivanov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract We study complexity of the index set of countably categorical theories and Ehrenfeucht theories in finite languages.

On the computation of complex equilibria

✍ Y. H. Ma; C. W. Shipman 📂 Article 📅 1972 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 577 KB

On Turing degrees of points in computabl

On Turing degrees of points in computable topology

✍ Iraj Kalantari; Larry Welch 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

## Abstract This paper continues our study of computable point‐free topological spaces and the metamathematical points in them. For us, a __point__ is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a __sharp filter__. A function __f~F~__

On the Computational Complexity of Best

On the Computational Complexity of Best L1-approximation

✍ Paulo Oliva 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 3 views

Categorization in everyday life: the eff

Categorization in everyday life: the effects of positive and negative categorizations on emotions and self-views

✍ Naomi Ellemers; Manuela Barreto 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

This study investigates how everyday categorization experiences affect people's emotional responses and self-views. A representative Dutch population sample (N ¼ 463) was asked to recount a situation in which they were categorized by others. This resulted in a range of categories that were spontaneo

On the convergence of Fourier series of

On the convergence of Fourier series of computable Lebesgue integrable functions

✍ Philippe Moser 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

This paper studies how well computable functions can be approximated by their Fourier series. To this end, we equip the space of L p -computable functions (computable Lebesgue integrable functions) with a size notion, by introducing L p -computable Baire categories. We show that L p -computable Bair