Indexed family of all unary partial computable functions

Question

Please help prove the following statement:

The indexed family of all unary partial computable functions that have total computable extension is computable.

Definitions:

1. Total function - a function which is defined for all inputs of the right type, that is, for all of a domain.

2. A function $g$ is called an extension of the partial function $f$ if $\operatorname{Dom}(f) ⊆ \operatorname{Dom}(g)$ and $g(x) = f(x)$ for any $x \in \operatorname{Dom}(f)$, where $\operatorname{Dom}(f)$ is the domain of the function.

3. Let $S$ be nonempty countable set (possibly finite). Any surjective map $\nu\colon \omega \twoheadrightarrow S$ from the set $\omega$ of natural numbers onto the set $S$ is called an enumeration .

4. An indexed family of functions is called computable if it has at least one computable enumeration.

Additional information:

• The indexed family of all unary computable functions is not computable.

Answer 1

Recall that a collection $\mathcal{F}$ of computable partial functions admits a computable numbering if there is a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $\mathcal{F} = \{\varphi_{f(e)} \mid e \in \mathbb{N}\}$, where $(\varphi_e)_{e \in \mathbb{N}}$ is a standard enumeration of the computable partial functions.

Let $\mathcal{I}$ be the collection of computable partial functions whose domain is either $\mathbb{N}$ or some $\{0,\ldots,n\}$.

Claim: $\mathcal{I}$ admits a computable numbering.

Proof: Let $\iota(n)$ denote the program:

1. Input $k \in \mathbb{N}$
2. For each $0 \leq i < k$ simulate $\phi_n(i)$.
3. Simulate $\varphi_n(k)$ and output its output

Clearly, if $\varphi_n$ is total, then $\varphi_{\iota(n)} = \varphi_n$. Otherwise $\varphi_{\iota(n)}$ is defined in some initial segment of $\mathbb{N}$. Thus, $\iota$ is a computable numbering of $\mathcal{I}$.

Let $\mathcal{C}$ be the collection of partial computable functions admit a computable total continuation. It is easy to see that $\mathcal{C}$ is also the class of partial computable function admitting an extension in $\mathcal{I}$. As the domain of a partial computable function is c.e., we can then show:

Claim: $\mathcal{C}$ admits a computable numbering.

Proof: Let $\langle \ , \ \rangle$ be a standard pairing function. We define $c : \mathbb{N} \to \mathbb{N}$ by letting $c(\langle e, n \rangle)$ be the program:

1. Input $k \in \mathbb{N}$
2. Simulate $\varphi_n(k)$
3. Simulate $\varphi_{\iota(e)}(k)$ and output its result.

Now $c$ is a computable numbering for $\mathcal{C}$. To see this, we first note that $\varphi_{c(\langle e,n\rangle)}$ is the restriction of $\varphi_{\iota(e)}$ to the set $\operatorname{dom}(\varphi_n)$. This establishes $\varphi_{c(\langle e,n\rangle)} \in \mathcal{C}$ for any $e, n$. Conversely, assume that $f$ is a partial computable function with a total computable continuation $g$. Let $f = \varphi_n$ and $g = \varphi_e$. Then $f = \varphi_{c(\langle e, n\rangle)}$, so we do get indeed each member of $\mathcal{C}$ in the range of $c$.