Prove or disprove: The following language $L$ is decidable:

$\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$

So for proving I need to construct a TM $U$. If it accepts $L$, so L is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, t\rangle$:

  1. $i:=1$;
  2. Simulate one step of $M$ on $w$.
  3. If $M$ accepted $w$ then $U$ accepts.

    If $M$ rejected $w$ then $U$ rejects.

    If $i ≥ t$ then $U$ rejects.

  4. Else $i:=i+1$; goto step 2."

Because $U$ is the decider machine (finite number of steps) $\longrightarrow$ $L$ is the decidable language.

Is this solution correct? Or I should do it in another way?

  • 2
    $\begingroup$ The text of the exercise is slightly malformed, I assume from context that you actually meant "$M(w)$ halts (...)" instead of "$M(x)$ halts (...)". In that case, your proof doesn't work, because the machine you describe would yield the answer for a single input out of infinitely many. Technically, you have only proven that $L$ is co-recursively enumerable. Hint: do you really need to check infinitely many inputs? $\endgroup$ – quicksort Apr 19 '18 at 0:50
  • 1
    $\begingroup$ @quicksort Turn into a full-fledged answer? $\endgroup$ – Yuval Filmus Apr 19 '18 at 7:32
  • 1
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. $\endgroup$ – Raphael Apr 19 '18 at 9:08
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 19 '18 at 9:08
  • $\begingroup$ Also, why post basically the same thing twice? Feedback on one should tell you all you need to know about the other. $\endgroup$ – Raphael Apr 19 '18 at 9:10

Your Answer

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

Browse other questions tagged or ask your own question.