Computing space-filling curves (Q692924)

The research of space-filling curves started with Jordan and Peano in the 1880s. Peano's construction of such curves motivated efforts to characterise continuous images of \([0,1]\) and to devise an appropriate definition of topological dimension. Such a characterisation was obtained independently by Hahn and by Mazurkiewicz, now called Hahn-Mazurkiewicz theorem. This theorem asserts that the following conditions are equivalent: 1. A topological space is a continuous image of \([0,1]\). 2. It is metrizable, compact, connected and locally connected. Recently, space-filling curves were applied to the design of parallel computers. In this paper, the authors prove an effective version of the Hahn-Mazurkiewicz theorem within the theory of type-two effectivity. First, they show that there is no guarantee for the existence of a computable space-filling curve under the assumption of computable compactness only. But they point out that this does not mean that there is no effective version of the Hahn-Mazurkiewicz theorem. They then investigate the appropriate definition for effective locally connectedness that guarantees the existence of the effective version of the Hahn-Mazurkiewicz theorem. Moreover, the authors show a counterexample to the effective converse of the Hahn-Mazurkiewicz theorem that there is a computable function from \([0,1]\) into \(\mathbb R^{2}\) whose range is not effectively locally connected. This paper provides new aspects of the Hahn-Mazurkiewicz theorem using the concept of effectiveness, and so contributes to computable mathematics.