1
$\begingroup$

I am having difficulty in reducing non halting problem to the given problem to prove that language is non R.E

For eg Completeness problem of TM .

In the above problem, we accept $\Sigma^*$ if H does not halt on w . For doing that, we give an input $x$ and simulate H on w for $|x|$ steps. I don't understand how can we deduce that H does not halt on w by just simulating H on w for $|x|$ steps.

Suppose H halts on w after $k+2$ steps and $|x| = k$. Now if we simulate H on w only for $k$ steps, how can we say that H will never halt or does not halt on w? It does not halt after $k$ steps but halts after $k+2$ steps.

I think that non halting problem is whether H does not halt on w and not whether H does not halt on w in k steps.

Can someone please help me in understanding the reduction?

Improve this question
$\endgroup$
  • $\begingroup$ Reducing $A$ to $B$ does not involve deciding $A$, nor deciding $B$. In the linked question, non-halting is reduced to a language $L$, without deciding non-halting, and without deciding $L$. The reduction exploits that "halts in k steps" is decidable, but that's not used to decide non-halting, or deciding $L$. It is exploited only to make it an m-reduction. $\endgroup$ – chi Jan 10 '18 at 15:00
  • 1
    $\begingroup$ @RajeshR I was busy, so couldn't reply. What language do you want to reduce to what language? Please define them (both!) in your post using set theoretic notation. In particular, what do you mean by "non-halting language"? Is it complement of the language of the Halting problem? The language of the Halting problem is defined as $A_{TM} = \{\langle M,w \rangle \mid M \text{ halts on } w\}$. $\endgroup$ – fade2black Jan 10 '18 at 15:31
  • $\begingroup$ @fade2black, In my question I have said "non halting problem". I want to reduce non halting problem to completeness problem of TM. Non halting problem is, given Turing machine H and input w, we have to decide whether H does not halt on w. $\endgroup$ – Rajesh R Jan 10 '18 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.