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

$\{ \langle M, x\rangle: M \text{ is a Turing machine and } M(x) \text{ halts in less than } |x|^2 \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, x\rangle$:

  1. $i:=1$;

    $n := |x|^2$

  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 ≥ n$ then $U$ rejects.

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

Because $U$ is a decider machine, $L$ is a decidable language.

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

  • $\begingroup$ Can't you just simulate $M$ for $|x|^2 - 1$ steps? Also, you might need to handle the case $|x| = 0$ separately. $\endgroup$ – theyaoster Apr 19 '18 at 1:36
  • 1
    $\begingroup$ Your solution seems correct. For more feedback, I suggest contacting your TA. $\endgroup$ – Yuval Filmus Apr 19 '18 at 7:33
  • 2
    $\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:09
  • $\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:09

If you want to prove that a language is decidable, it is sufficient to construct a Turing Machine that accepts if the input is in the language. It MUST reject if the input is not in the language.

Additionally, you are required to argue/prove that the Turing Machine constructed does that. Here's a hint: M must just halt on x, for it to be in L. Consider all possibilities of halting.


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