prove that there are exists two partial non-computable functions $g(x)$ and $f(x)$ whose product is a computable function $h(x)$ = $f(x) * g(x)$ for $\forall$ $x \in N$

I thought that we can just take two undecidable sets in $f$ and $g$ will be their characteristic functions, but characteristic functions are total, when we need to find partial functions/

  • $\begingroup$ @spaceisdarkgreen added my thoughts. Please remove -1 Upd: thnx $\endgroup$ Sep 24 '20 at 17:00
  • $\begingroup$ A total function is a (special case of a) partial function. And if you really need it to not be total for some reason, can always modify it ad hoc. $\endgroup$ Sep 24 '20 at 17:03
  • $\begingroup$ @spaceisdarkgreen do you mean i can take characteristic function and modify it's dom ? But how, i don't understand a little bit. $\endgroup$ Sep 24 '20 at 17:04
  • $\begingroup$ If $f$ is a total function, let $f^*(x)=f(x)$ if $x$ is not zero and undefined if it is zero. Then $f^*$ is partial, and probably close enough to $f$ that it's still usable. Or if you want to keep all the information from $f$, let $f^*(x+1)=f(x)$ and $f^*(0)$ undefined. Anyhow, I don't think this is important for this problem. I think the most common answer to this problem will have $f$ and $g$ total functions, and I don't think that's wrong since a total function is a partial function. $\endgroup$ Sep 24 '20 at 17:07
  • $\begingroup$ If $f,g$ are properly partial, then $h$ is also only partial, isn't it? Or is "zero times undefined" considered zero in the context? $\endgroup$ Sep 24 '20 at 17:12

So we take undecidable set $A$. $\neg A$ is undecifable too.

$f$ returns $0$ if $x \in A$ else returns $1$

$g$ returns $0$ if $x \in \not A$ else returns $1$

So $h = g * f$ is a total computable function which always returns $0$


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.