Return to Question

The one-point compactification $\mathbb{N}_\infty$ of $\mathbb{N}$ is obtained from the discrete space $\mathbb{N}$ by adjoining a limit point $\infty$. It may be identified with the subspace of Cantor space $$ \mathbb{N}_\infty = \{ \alpha \in \{0,1\}^\mathbb{N} \mid \forall n \,.\, \alpha_n \geq \alpha_{n+1} \}. $$ Indeed, we may embed $\mathbb{N} \to \mathbb{N}_\infty$ by mapping $n$ to the sequence $$\overline{n} = \underbrace{1 \cdots 1}_n 0 0 \cdots,$$ and taking $\infty = 1 1 1 \cdots$.

Classically of course adjoining a single point to a countable set has no effect on countability. How about the computable version? If we adjoin the new point as an isolated one then of course we again obtain a countable set. This question is about adjoining $\infty$ as a limit point.

Let $\varphi$ be a standard enumeration of partial computable maps.

Question: Do there exist a total computable map $q$ and a partial computable map $s$ such that:

1. $\varphi_{q(n)} \in \mathbb{N}_\infty$ for all $n \in \mathbb{N}$
2. For all $k \in \mathbb{N}$, if $\varphi_k \in \mathbb{N}_\infty$ then $s(k)$ is defined and $\varphi_{q(s(k))} = \varphi_k$.

The map $q$ realizes an enumeration $\mathbb{N} \to \mathbb{N}_\infty$, and $s$ the fact that $q$ is surjective.

The one-point compactification $\mathbb{N}_\infty$ of $\mathbb{N}$ is obtained from the discrete space $\mathbb{N}$ by adjoining a limit point $\infty$. It may be identified with the subspace of Cantor space $$ \mathbb{N}_\infty = \{ \alpha \in \{0,1\}^\mathbb{N} \mid \forall n \,.\, \alpha_n \geq \alpha_{n+1} \}. $$ Indeed, we may embed $\mathbb{N} \to \mathbb{N}_\infty$ by mapping $n$ to the sequence $$\overline{n} = \underbrace{1 \cdots 1}_n 0 0 \cdots,$$ and taking $\infty = 1 1 1 \cdots$.

Classically of course adjoining a single point to a countable set has no effect on countability. How about the computable version? If we adjoin the new point as an isolated one then of course we again obtain a countable set. This question is about adjoining $\infty$ as a limit point in the sense of metric spaces.

Let $\varphi$ be a standard enumeration of partial computable maps.

Question: Do there exist a total computable map $q$ and a partial computable map $s$ such that:

1. $\varphi_{q(n)} \in \mathbb{N}_\infty$ for all $n \in \mathbb{N}$
2. For all $k \in \mathbb{N}$, if $\varphi_k \in \mathbb{N}_\infty$ then $s(k)$ is defined and $\varphi_{q(s(k))} = \varphi_k$.

The map $q$ realizes an enumeration $\mathbb{N} \to \mathbb{N}_\infty$, and $s$ the fact that $q$ is surjective.

Clarification: The following map $q : \mathbb{N} \to \mathbb{N}_\infty$ comes to mind: $$q(n)(k) = \begin{cases} 1 & \text{if $T_n$ has not terminated within $k$ steps of execution}\\ 0 & \text{if $T_n$ has terminated within $k$ steps of execution} \end{cases} $$ However, it seems hard to get the corresponding map $s$ witnessing surjectivity of $q$.

(I should say that $q$ works as a computable enumeration for yet a third way of adjoining a point to $\mathbb{N}$, namely $$\mathbb{N}_\bot = \{ S \subseteq \mathbb{N} \mid \forall i, j \in S \,.\, i = j \}.$$ We embed $n \in \mathbb{N}$ into $\mathbb{N}_\bot$ as a singleton $\{n\}$, while the extra point is $\emptyset$. Think of $\mathbb{N}_\bot$ as the set of enumerable subsets of $\mathbb{N}$ with at most one element.