Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations (Q1885034)

The authors consider the space \(2^{\leq \omega} = 2^* \cup 2^\omega\) in the context of possibly infinite computations, which can result in finite or infinite outputs. The paper is divided into 10 sections. The first one gives a review of the fundamental notions, recalls the known important results, and describes the main purpose of the article. The second section is about sets of words, especially a lot of space is devoted to the prefix ordering of words and properties of checkable and recursively enumerable sets of words. This material is introduced as useful to characterize the computable subsets of \(2^{\leq \omega}\). In the third section, the topological space \(2^{\leq \omega}\) is discussed: different types of topologies are presented, characteristics of open, closed and clopen sets for \(2^{\leq \omega}\) and \(2^{\omega}\) are given. Section 4 gives a self-contained direct approach of the computability notion for \(2^{\leq \omega}\) by elaborating from the classical theory for \(2^{\omega}\). However, it is pointed out that computability over \(2^{\omega}\) is not induced by computability over \(2^{\leq \omega}\). A characterization of computable subsets by clopen sets is proved. Moreover, the arithmetical hierarchy over \(2^{\leq \omega}\) is obtained as an effectivization of the finite levels of the Borel hierarchy, and logical expression of the arithmetical hierarchy is added. In the fifth section, semicomputability with possibly infinite computations is considered. For this purpose, monotone Turing machines are used. With this notion, the definition of computable and semicomputable total maps with domain among the sets \(2^*, 2^\omega\), \(2^{\leq \omega}\) and range in the set \(2^{\leq \omega}\) are given. The properties of such maps are listed, and the syntactical complexity of some predicates involving computable and semicomputable maps is established. The next section contains a detailed analysis of relations between continuity and computability as well as between lower semicontinuity and semicomputability for total maps, where domains and ranges vary in \(2^*,2^\omega\), \(2^{\leq \omega}\). Section 7 is a preparation for the representation of maps \(F\) of the above-mentioned types by maps \(f\) from \(2^*\) to \(2^*\) or \(2^{\leq \omega}\). Two approaches are formulated: bottom-up -- from \(f\) to \(F\), and top-down -- from \(F\) to \(f\). These tools are used in the eighth section, which can be considered to be the main part of the paper. Here the representation theorem is given. This theorem is a detailed characterization of maps into \(2^{\leq \omega}\) with respect to their (semi)computability, (semi)continuity and some additional notions introduced in the earlier sections. Section 9 adds a consideration of checkable maps and traces on \(2^*\) of continuous maps from \(2^{\leq \omega}\) to \(2^{\leq \omega}\). The last section presents some looks at the authors' forthcoming papers and directions of future work. In general, this paper can be regarded as an interesting and detailed study of the properties of the space \(2^{\leq \omega}\) involving topology and computability.