# How to prove that language is decidable? [duplicate]

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?

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