Proving Blank-halt to be recursively enumerable through reduction to Halting problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-16T06:56:14Z https://cs.stackexchange.com/feeds/question/83719 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/83719 1 Proving Blank-halt to be recursively enumerable through reduction to Halting problem user79943 https://cs.stackexchange.com/users/0 2017-11-10T19:59:11Z 2017-11-10T20:25:18Z <p>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.</p> <p>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?</p> <p>I'm confused about the reduction flow.</p> https://cs.stackexchange.com/questions/83719/-/83721#83721 1 Answer by David Richerby for Proving Blank-halt to be recursively enumerable through reduction to Halting problem David Richerby https://cs.stackexchange.com/users/9550 2017-11-10T20:25:18Z 2017-11-10T20:25:18Z <p>If you reduce \$X\$ to&nbsp;\$Y\$, you're showing that \$X\$&nbsp;is no harder than&nbsp;\$Y\$ and that \$Y\$&nbsp;is at least as hard as&nbsp;\$X\$.</p> <p>So, by showing that some problem&nbsp;\$X\$ reduces to the halting problem, you're showing that \$X\$&nbsp;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\$&nbsp;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 <em>to</em> it, which shows it's at least as hard as the halting problem, as above.</p>