Recursion and topology on 2⩽ω for possibly infinite computations

AbstractIn the context of possibly infinite computations yielding finite or infinite (binary) outputs, the space 2⩽ω=2∗∪2ω appears to be one of the most fundamental spaces in Computer Science. Though underconsidered, next to 2ω, this space can be viewed (Section 3.5.2) as the simplest compact space native to computer science.In this paper we study some of its properties involving topology and computability.Though 2⩽ω can be considered as a computable metric space in the sense of computable analysis, a direct and self-contained study, based on its peculiar properties related to words, is much illuminating.It is well known that computability for maps 2ω→2ω reduces to continuity with recursive modulus of continuity. With 2⩽ω, things get less simple. Maps 2ω→2⩽ω or 2⩽ω→2⩽ω induced by input/output behaviours of Turing machines on finite or infinite words—which we call semicomputable maps—are not necessarily continuous but merely lower semicontinuous with respect to the prefix partial ordering on 2⩽ω. Continuity asks for a stronger notion of computability.We prove for (semi)continuous and (semi)computable maps F:I→O with I,O∈{2ω,2⩽ω} a detailed representation theorem (Theorem 81) via functions f:2∗→2∗ following two approaches: bottom-up from f to F and top-down from F to f