No label defined (Q4428702)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1984268
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1984268 |
Statements
22 September 2003
0 references
computable structures
0 references
presentation
0 references
degree spectra
0 references
computable dimension
0 references
categoricity
0 references
survey
0 references
0 references
0 references
0.87539303
0 references
0.87406677
0 references
0 references
0.8725366
0 references
0 references
In this survey paper the author considers the question of whether computability properties of structures depend on the choice of a presentation and if so, then how? Let \(R\) be a relation not included in the language of a computable structure \({\mathcal A}\). The author describes some classic results giving conditions on \({\mathcal A}\) or \(R\) that restrict the possible variations in the computable dimension of \({\mathcal A}\) and the computational complexity of \(R\). Further, in the absence of such conditions, the author discusses the possible computable dimensions of \({\mathcal A}\) and, in terms of Turing degrees, variations of \(R\) in different presentations. The author also discusses recent results of the author, Khoussainov, Hirschfeldt and others about the possible degree spectra of computable relations on computable structures and the connections with computable dimension and categoricity both in a general model-theoretic setting and in some restricted classes of structures (graphs, linear and partial orderings, lattices, Abelian and nilpotent groups, rings etc.). For the entire collection see [Zbl 1017.00016].
0 references