1
$\begingroup$

Where $K = \{x | φ_x(x) \downarrow\}$, $φ_x$ is a $\mu$-recursive function computing $M_x$, $M_x$ is Turing machine with Godel's number $x$. Set $A$ is "1-reducible" to set $B$ ($A \leq_1 B$) when there exists invertible function $f = (\forall x \in N)[x \in A \Longleftrightarrow f(x) \in B]$.

I need that for part of my homework. Thank you for your help.

  • 0
    @BenedictEastaugh You're right. Presumably this is what the OP had in mind (otherwise the solution would be trivial).2012-12-10

1 Answers 1

2

Via the s-m-n theorem, define a 1-1 function $g(x)$ such that

$ \varphi_{g(x)}(n) = \begin{cases} 1 &\text{if } \varphi_{x}(x)\downarrow,\\ \uparrow &\text{otherwise}. \end{cases} $ Let $e$ be such that $\varphi_{e}(n) =1$ for each $n$. The function $f(x) = \langle e, g(x) \rangle$ is then computable and 1-1. Moreover, $x \in K \Longleftrightarrow f(x) \in \mathrm{EQ}.$