The classification problem for compact computable metric spaces
| dc.citation.volume | 7921 | |
| dc.contributor.author | Melnikov A | |
| dc.contributor.author | Nies A | |
| dc.coverage.spatial | Milan, Italy | |
| dc.date.available | 2013 | |
| dc.date.finish-date | 2013-07-05 | |
| dc.date.issued | 2013 | |
| dc.date.start-date | 2013-07-01 | |
| dc.description.abstract | We adjust methods of computable model theory to effective analysis. We use index sets and infinitary logic to obtain classification-type results for compact computable metric spaces. We show that every compact computable metric space can be uniquely described, up to isometry, by a computable Π3 formula, and that orbits of elements are uniformly given by computable Π2 formulas. We show that deciding if two compact computable metric spaces are isometric is a Π02Π20 complete problem within the class of compact computable spaces, which in itself is Π03Π30 . On the other hand, if there is an isometry, then ∅ ′′ can compute one. In fact, there is a set low relative to ∅ ′ which can compute an isometry. We show that the result can not be improved to ∅ ′. We also give further results for special classes of compact spaces, and for other related classes of Polish spaces. | |
| dc.description.confidential | false | |
| dc.format.extent | 320 - 328 | |
| dc.identifier.citation | Lecture Notes in Computer Science, 2013, 7921 pp. 320 - 328 | |
| dc.identifier.doi | 10.1007/978-3-642-39053-1_37 | |
| dc.identifier.elements-id | 239104 | |
| dc.identifier.harvested | Massey_Dark | |
| dc.identifier.isbn | 9783642390524 | |
| dc.identifier.issn | 1611-3349 | |
| dc.publisher | Springer, Berlin, Heidelberg | |
| dc.relation.isPartOf | Lecture Notes in Computer Science | |
| dc.relation.uri | http://www.newton.ac.uk/files/preprints/ni13004_0.pdf | |
| dc.source | Conference on Computability in Europe CiE 2013: The Nature of Computation. Logic, Algorithms, Applications | |
| dc.title | The classification problem for compact computable metric spaces | |
| dc.type | conference | |
| pubs.notes | Not known | |
| pubs.organisational-group | /Massey University | |
| pubs.organisational-group | /Massey University/College of Sciences | |
| pubs.organisational-group | /Massey University/College of Sciences/School of Natural and Computational Sciences |