# Indexed family of all unary partial computable functions

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.

• The indexed family of all unary computable functions is not computable.
• You haven't specified how the input is represented – presumably as a Turing machine computing the input unary p.c. function. – Yuval Filmus May 14 '20 at 12:12
• Let $f$ be the unary partial computable function defined as follows: if the $n$'th Turing machine halts after $T$ steps then $f(n) = T$, and $f(n) = \bot$ otherwise. Note that $f$ cannot be extended to a computable function, since that would allow you to solve the halting problem. Now given a Turing machine $M$, let $f_M$ be the function that first runs $M$ on the empty input, and if $M$ halts, forwards execution to $f$. Then $f_M$ is a unary partial computable function, and $f_M$ can be extended to a total computable function iff $M$ doesn't halt on the empty input. – Yuval Filmus May 14 '20 at 12:17
• My comment disproves your statement. – Yuval Filmus May 14 '20 at 12:28
• Can you describe exactly which language you are claiming to be computable? I'm not sure what "the family of all unary partial computable functions that have a total computable extension" means, that is, what do elements of this family look like, and what would it mean for such a family to be computable. You mentioned computable numbering, but I'm not sure what this means. I understand Turing machines. – Yuval Filmus May 14 '20 at 12:31
• It seems that you want to show that your collection is recursively enumerable (the usual term). This doesn't really help, since it is known that the set of non-halting Turing machines is not recursively enumerable. – Yuval Filmus May 15 '20 at 11:18

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$$.

• Thank you very much for your answer! Could you explain in more details the part of the proof in the case of the collection C. I don't fully understand why c can be considered the computable numbering for C – T uS May 15 '20 at 17:56
• @TuS I've added the proof why $c$ is a computable numbering of $\mathcal{C}$. – Arno May 15 '20 at 18:13
• Is there another form of the definition of ι(n) and c(⟨e,n⟩) ? I haven't seen a recording form using a program before. I want to be sure that I understand everything correctly – T uS May 15 '20 at 18:35
• You can read "be the program" as "be a G\"odel number for the Turing machine that essentially does the following", if you are more comfortable with that. But in terms of conceptual simplicity, this is what you get. – Arno May 15 '20 at 19:15
• One more question. Is the term "collection" equivalent to indexed family? – T uS May 16 '20 at 3:05