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

162 Views Asked by At

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/

1

There are 1 best solutions below

0
On

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$