Relationship between existence and computable function

51 Views Asked by At

Let $A$ be a set, $K$ a non recursive set, and a total computable function $g$ such that $\forall x\exists n.x\in K \Leftrightarrow g(x, n)\in A$.

The question is if the function: $f(x)=a$ such that $x\in K \Leftrightarrow g(x, a)\in A$ is total computable.

Hence, can I prove $K\leq _m A$ with $g(x,f(x))$ as reduction function?

1

There are 1 best solutions below

1
On

This is false in general: let $K$ be the halting set (i.e. $K=\{x:\varphi_x(x)~ \mathrm{halts}\}$) and let $A=\{1\}$. Clearly $A$ is recursive. Define $g$ as $g(x,n)=1$ if $\varphi_x(x)$ halts in $n$ steps and $0$ otherwise. We have

$$ \forall x \quad x\in K \iff (\exists n)( g(x,n)\in A) $$

But $K\not\le_m A$. In particular there is no computable $f$ that chooses an $n$ s.t. $x\in K \iff g(x,n)\in A$ (that would be equivalent to computably producing the number of steps a machine needs to halt).