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

Question

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?

Answer 1

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$.