What is effectively continuous?

Question

In Soare's book Recursively Enumerable Sets and Degrees I saw a sentence:

$\Phi_e$ is an effectively continuous functional from the Cantor space $2^\omega$ to itself.

What does it mean for a function to be effectively continuous?

Answer 1

Cantor space, $2^{\omega}$, is equipped with the product topology; the set $2=\{0,1\}$ has the discrete topology. This topology is generated by the so-called cylinder sets $[\sigma]= \{x \in 2^\omega : x \succ \sigma\}$, where $\sigma$ is a finite binary string.

So a set is open if it is a union of cylinders. A set is called effectively open if it is a union of a c.e. set of cylinders.

A function $f:2^{\omega} \to 2^{\omega}$ is effectively continuous if $f^{-1}[\sigma]$ is effectively open for every finite string $\sigma$, and uniformly so; i.e. there is a single algorithm that when given $\sigma$, enumerates $f^{-1}[\sigma]$.

Let me know if you'd like more detail.

Answer 2

By Alex R.'s link the adapted definition is as follows. Let $F:\mathbb{R} \to \mathbb{R}$ be a real valued function. Let $A_F=\{(a,b,c,d) \in \mathbb{Q} : F([a,b]) \subseteq (c,d) \cap \mathbb{Q}\}$. Then $F$ is effectively continuous iff $A_F \in \Sigma_1$ (computably enumerable) and $\forall r \in \mathbb{R} \cap \Delta_0$ (computable real number) $\forall \epsilon > 0. \exists (a,b,c,d) \in A_F. a < x < b \land |d - c| \le \epsilon$.