Show that $\overline{K}\leq_m Inf$

64 Views Asked by At

First the definitions: $K:=\{x:\phi_x(x)$ converges$\}$, so $\overline{K}=\{x:\phi_x(x)$ diverges$\}$. Also $Inf:=\{x:dom(\phi_x)$ is infinite$\}$. $\phi_x$ is recursive in all cases.

By Church turing thesis, let $P_x$ denote the turing program that simulates the recursive function $\phi_x$.

In order to show $\overline{K}\leq_m Inf$, i.e. $\overline{K}$ is many-one reducible to $Inf$, we just have to find a recursive function $f$ such that $x\in\overline{K}\iff f(x)\in Inf$.

$x\in\overline{K}\iff\phi_x(x)$ does not converge $\iff$ there does not exist $n$ such that $P_x$ halts on $x$ in $n$ steps.

On the other hand, $f(x)\in Inf\iff P_{f(x)}$ halts on infinitely many inputs.

How do I construct such a function $f$ so that the argument flows?

1

There are 1 best solutions below

0
On

Consider the program $ P$ such that $ P(x,n)=0$ if the computation of $\phi_x (x)$ doesn't stop in $n$ steps or less. Otherwise $ P(x,n)$ diverges. By s-n-m there is a recursive function $f$ such that for all $x$ and $n$, $\phi_{f(x)}(n)=P(x,n)$

Then $x\in\overline{K}$ iff $f(x)\in Inf$