Autor(es)

Verónica Becher and Serge Grigorieff

URL Pública

Abstract

In 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 …