# Difficulty in reducing non halting problem to a given problem

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.

• 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. – chi Jan 10 '18 at 15:00
• @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\}$. – fade2black Jan 10 '18 at 15:31