1
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ You haven't specified how the input is represented – presumably as a Turing machine computing the input unary p.c. function. $\endgroup$ – Yuval Filmus May 14 at 12:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 14 at 12:17
  • 1
    $\begingroup$ My comment disproves your statement. $\endgroup$ – Yuval Filmus May 14 at 12:28
  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 14 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 15 at 11:18
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – T uS May 15 at 17:56
  • $\begingroup$ @TuS I've added the proof why $c$ is a computable numbering of $\mathcal{C}$. $\endgroup$ – Arno May 15 at 18:13
  • $\begingroup$ 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 $\endgroup$ – T uS May 15 at 18:35
  • $\begingroup$ 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. $\endgroup$ – Arno May 15 at 19:15
  • $\begingroup$ One more question. Is the term "collection" equivalent to indexed family? $\endgroup$ – T uS May 16 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.