0

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
  • 1
  • 1
    I recommend reviewing and correcting these definitions. In particular, in Definition 1, "obtained " in what way? For example, division of one total function by another won't generally produce a total function. Also, since $S$ is allowed to be rather arbitrary in Definition 3 of "enumeration", the concept of "computable enumeration", presupposed in Definition 4, hasn't been defined. Make sure you get the relevant definitions (and the question) from the same source, because some of these terms may be used differently by different authors. – Andreas Blass May 16 '20 at 16:39
  • 1
    Also, are you sure you're supposed to prove (rather than disprove) the statement you asked about? – Andreas Blass May 16 '20 at 16:41
  • 1
    I deleted the tag "normal families" because that's a concept from complex analysis that has nothing to do with computability. – Andreas Blass May 16 '20 at 16:43
  • @Andreas Blass I have a task: "Prove that...", but if you know how to disprove this statement, I will be glad to know how to do it. – T uS May 17 '20 at 11:47
  • Definitions 3 and 4 I took from the literature of my teacher. Set enumeration and computably enumerable sets are two different things. – T uS May 17 '20 at 11:57
  • Under the usual definitions, the statement you want to prove is false. But I can't say anything about the situation under the definitions in your question because they's not coherent with each other. – Andreas Blass May 17 '20 at 15:11
  • @Andreas Blass Could you show a disproof of this statement using standard definitions? – T uS May 17 '20 at 15:30
  • What I had in mind was Rice's theorem. I expect that there are more direct disproofs, but I haven't really looked for one. – Andreas Blass May 17 '20 at 15:46
  • I'm not sure that Rice's theorem can be applied here. – T uS May 18 '20 at 10:04

0 Answers0