1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Doesn't the post, to which you give the link in your post, reduce the Halting problem to $L$? $\endgroup$ – fade2black Dec 16 '17 at 9:50
  • $\begingroup$ It does, and that proves that $L$ is not decidable, I want to prove that it's recognizable. $\endgroup$ – user3636583 Dec 16 '17 at 10:09
  • $\begingroup$ 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$. $\endgroup$ – fade2black Dec 16 '17 at 10:27
  • $\begingroup$ Sounds good, do you want to post it as the answer? $\endgroup$ – user3636583 Dec 16 '17 at 11:22
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.