Skip to main content
6 of 6
deleted 28 characters in body
T uS
  • 19
  • 3

Indexed family of all unary partial computable functions

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.
T uS
  • 19
  • 3