# 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

## 1 Answer

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