# Prove that there are two non-computable functions whose product is a computable function

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/

• @spaceisdarkgreen added my thoughts. Please remove -1 Upd: thnx Sep 24 '20 at 17:00
• 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. Sep 24 '20 at 17:03
• @spaceisdarkgreen do you mean i can take characteristic function and modify it's dom ? But how, i don't understand a little bit. Sep 24 '20 at 17:04
• 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. Sep 24 '20 at 17:07
• 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? 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$$