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

I have not fully understood the algorithm, as it didnt state what $w$ is.

Although, the language $L$ is decidable:

Build the TM for the following algorithm: (assuming input of form $<M,t>$)

  1. For every $w\in\Sigma^*$ with $|w|\le t$:
    1. Emulate $M$ on $w$ for $t$ steps. If $M$ did not halt in that time, reject.
  2. If for all such $w$, $M$ halted within $t$ steps - accept.

This algorithm always halts - as there are a finite number of $w$ with $|w|\le t$ (and it does not simulate $M$ for more than $t$ steps)

The algorithm is right:

  1. If $<M,t>\in L$ then $M$ will halt within $t$ steps on every $w$ we will check, therefore the algorithm will accept.
  2. If $<M,t>\notin L$, then there is some $w\in\Sigma^*$ where $M$ doesnt halt on him within $t$ steps. Notice, that if we define $\hat w=w_{1,...,t}$ to be the first $t$ letters of $w$, then also $M$ wouldnt halt on $\hat w$ within $t$ steps, as if it would have been - then $M$ didnt read move its head right more that $t$ times - and therefore for every $y\in\Sigma^*$, $M$ halts on $\hat wy$ within $t$ and specifically $w$ too. The algorithm can find the $\hat w$ (since $|\hat w|=t$) and will reject because of it.
| cite | improve this answer | |

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.