0
$\begingroup$

Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$.

  1. How can $f(K)$ be a finite set?
  2. Why if‌ $B$ is recursive, is $f^{-1}(B)$ also recursive?
$\endgroup$
1
  • $\begingroup$ There are no restrictions on the type of reduction? $\endgroup$
    – Raphael
    Mar 19, 2015 at 10:55

1 Answer 1

4
$\begingroup$

As the name suggests, a many-one reduction can map many instances of $K$ onto a single instance of $A$. If there are no restrictions on the power of $f$, then you can pick some $a\in A$ and $b\notin A$ and then define $$f(x)=\begin{cases} a &\text{ if }x\in K\\ b &\text{ if }x\notin K\,. \end{cases}$$

However, if $f$ is restricted to be computable then the image of $f$ is necessarily infinite. This is because every finite set is computable so, if the image of $f$ were finite, you'd have a computable reduction from the halting set to a computable set, which is impossible because that would mean the halting set would be computable too.

If $B$ is recursive and $f$ is computable then you can decide whether $x\in f^{-1}(B)$ just by checking whether $f(x)\in B$. If $B$ isn't recursive or $f$ isn't computable, all the bets are off.

$\endgroup$
7
  • $\begingroup$ @PålGD $K$ is standard notation? Maybe if everybody teaches from the same book. $\endgroup$
    – Raphael
    Mar 19, 2015 at 10:56
  • 2
    $\begingroup$ @Raphael $K$ has been used to denote the halting set since the days of Gödel and Post. Every text book on recursion theory (e.g. Soare, Rogers, Odifreddi), all use $K$ to denote this set. Post called Gödel's diagonal set, $K = \{e \mid e \in W_e\}$ the complete set because every c.e. set $W_e$ is computable in $K$ [Soare, 2009]. I think cs.sx should accept $K$ as standard notation here. $\endgroup$
    – Pål GD
    Mar 19, 2015 at 11:27
  • $\begingroup$ @PålGD I know at least $H$ (for "Halteproblem"). $\endgroup$
    – Raphael
    Mar 19, 2015 at 12:30
  • $\begingroup$ There is a main problem. $f(K)$ is an infinite set is false. how do you say " the image of f is necessarily infinite" $\endgroup$
    – Homan
    Mar 21, 2015 at 9:57
  • $\begingroup$ @PålGD, would you please help me about my last comment? $\endgroup$
    – Homan
    Mar 21, 2015 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.