Mathematical logic, algebra and number theory

On images of partial computable functions over computable Polish spaces

M. V. Korovina^a, O. V. Kudinov<sup>b

a</sup> A.P. Ershov Institute of Informatics Systems, pr. Acad. Lavrentjev, 6, 630090, Novosibirsk, Russia
^b Sobolev Institute of Mathematics, pr. Koptyug, 4, 630090, Novosibirsk, Russia

Abstract: This paper is a part of the ongoing program on analysing the complexity of various problems in computable analysis in terms of the effective Borel and Lusin hierarchies. We give an answer to the question by A. Morozov and K. Weihrauch that concerns a characterisation of image complexity of partial computable functions over computable Polish spaces.

Keywords: computable Polish space, partial computable function, computable analysis.

UDC: 510.2

MSC: 03D78, 03D65, 03F60

Received December 7, 2016, published May 4, 2017

Language: English

DOI: 10.17377/semi.2017.14.035

Bibliographic databases:

•