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