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

1 Answer 1

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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