Computable Topology for Reliable Computations

Computable Topology for Reliable Computations Full article

Journal

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Output data

Year: 2019, Volume: 11964 LNCS, Pages: 185-198 Pages count : 14 DOI: 10.1007/978-3-030-37487-7_15

Tags

Computable analysis; Computable topology; Lifted domain presentation; Reliable computation

Authors

Korovina M. ¹ , Kudinov O. ^2,3

Affiliations

1	A.P. Ershov Institute of Informatics Systems, SbRAS, Novosibirsk, Russian Federation
2	Sobolev Institute of Mathematics
3	Novosibirsk State University, Novosibirsk, Russian Federation

Using the framework of computable topology we investigate computable minimality of lifted domain presentations of computable Polish spaces, in particular the real numbers, the Cantor and Baire spaces, the continuous functions on a compact interval, which are widely used in theoretical computer science, e.g., automata theory, computable analysis and reliable computations. We prove that all lifted domain presentations for computable Polish spaces are computably and topologically minimal. Then we show that a naive adaptation of the notion of stability from computable model theory does not work in this framework. Instead of stability we propose another approach based on principal translators and prove that in the case of the real numbers we can effectively construct a principal computable translator from the lifted domain presentation to any other effective domain presentation. © Springer Nature Switzerland AG 2019.

Korovina M. , Kudinov O.
Computable Topology for Reliable Computations
Lecture Notes in Computer Science. 2019. V.11964 LNCS. P.185-198. DOI: 10.1007/978-3-030-37487-7_15 Scopus OpenAlex

Scopus:	2-s2.0-85077496870
OpenAlex:	W2996082684

Пока нет цитирований