# Recognizability of machines which halt in $n$ steps on some input

We define the following language:

$$L = \{M \mid \text{M is a TM and there exists an input x on which M halts in at most |x| steps}\}.$$

Following this question I understand that $$L$$ is not decidable, but I know that it is recognizable, and therefore I'm looking for a reduction from the HALTING problem to $$L$$.

I thought of the following reduction:

On input $$M$$ for $$L$$, create a Turing machine $$M'$$ that for input $$y$$ for the HALTING problem runs $$M$$.

If $$M$$ halts, then $$M'$$ halts too, but I'm having problems proving the reduction.

Another way of proving this problem in my opinion is by building an $$M'$$ that recognizes the language by running $$M$$ all inputs for their length.

If $$M'$$ halts on some input it accepts, otherwise it keeps going.

Does this solution work?

• Doesn't the post, to which you give the link in your post, reduce the Halting problem to $L$? – fade2black Dec 16 '17 at 9:50
• It does, and that proves that $L$ is not decidable, I want to prove that it's recognizable. – user3636583 Dec 16 '17 at 10:09
• This could be proven without reduction. The proof is straightforward: given $M$ run through all strings, say over $0$ and $1$, in canonical order and for each string $x$ simulate $M(x)$ for $|x|$ steps. If there is such $x$, then you will eventually find this $x$ and so accept $x$. – fade2black Dec 16 '17 at 10:27
• Sounds good, do you want to post it as the answer? – user3636583 Dec 16 '17 at 11:22

This could be proven without reduction. The proof is straightforward: given $M$ run through all strings, say over $0$ and $1$, in canonical order and for each string $x$ simulate $M(x)$ for $|x|$ steps and check if it halts. If there is such $x$, then you will eventually find this $x$ and so accept $x$.