Highlights of the rice-shapiro theorem in computable topology

Margarita Korovina, Oleg Kudinov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

Computable topological spaces naturally arise in computer science for continuous data type representations that have tools for effective reasoning about quite complex objects such as real numbers and functions, solutions of differential equations, functionals and operators. Algebraic and continuous domains, computable metric spaces, computable Polish spaces have been successfully used in the theoretical foundation of computer science. In this paper we consider generalisations of the famous Rice-Shapiro theorem in the framework of effectively enumerable topological spaces that contain the weakly-effective ω –continuous domains and computable metric spaces as proper subclasses. We start with the classical case when the spaces admit principal computable numberings of computable elements and one can investigate arithmetical complexity of index sets. We provide requirements on effectively enumerable topological spaces which guarantee that the Rice-Shapiro theorem holds for the computable elements of these spaces. It turns out that if we relax these requirements then the Rice-Shapiro theorem does not hold. Then we discuss the perspective of extensions of the Rice-Shapiro theorem to spaces that do not have computable numberings of computable elements, in particular to computable Polish spaces.

Язык оригиналаанглийский
Название основной публикацииPerspectives of System Informatics - 11th International Andrei P. Ershov Informatics Conference, PSI 2017, Revised Selected Papers
РедакторыAK Petrenko, A Voronkov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы241-255
Число страниц15
ISBN (печатное издание)9783319743127
DOI
СостояниеОпубликовано - 1 янв 2018
Событие11th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, PSI 2017 - Moscow, Российская Федерация
Продолжительность: 27 июн 201729 июн 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10742 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция11th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, PSI 2017
СтранаРоссийская Федерация
ГородMoscow
Период27.06.201729.06.2017

Fingerprint Подробные сведения о темах исследования «Highlights of the rice-shapiro theorem in computable topology». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Korovina, M., & Kudinov, O. (2018). Highlights of the rice-shapiro theorem in computable topology. В AK. Petrenko, & A. Voronkov (Ред.), Perspectives of System Informatics - 11th International Andrei P. Ershov Informatics Conference, PSI 2017, Revised Selected Papers (стр. 241-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10742 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-74313-4_18