1
$\begingroup$

To prove the blank-halt problem is undecidable (does a given Turing machine halt on the empty input), it's a case of reducing the halting problem to the blank-halt problem and since the halting problem is undecidable, the blank-halt problem is undecidable.

However to prove the blank-halt problem is recursively enumerable just like the Halting problem, isn't the reduction then the other way around? In order to prove this part does the blank-halt problem get reduced to the halting problem and so if the halting problem is recursively enumerable then the blank halt problem is also recursively enumerable?

I'm confused about the reduction flow.

$\endgroup$

1 Answer 1

1
$\begingroup$

If you reduce $X$ to $Y$, you're showing that $X$ is no harder than $Y$ and that $Y$ is at least as hard as $X$.

So, by showing that some problem $X$ reduces to the halting problem, you're showing that $X$ is no harder than the halting problem, i.e., that it's recursively enumerable. Remember that we normally define problem classes to include all lower classes, so showing that $X$ is RE doesn't necessarily imply that it's not recursive, for example. In this case, we can separately prove that the blank halting problem isn't recursive, by reducing the halting problem to it, which shows it's at least as hard as the halting problem, as above.

$\endgroup$

Your Answer

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