Proving decidability of language

Question

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?

Answer 1

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$: 2. 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 $\langle M,t\rangle\in L$ then $M$ will halt within $t$ steps on every $w$ we will check, therefore the algorithm will accept.
2. If $\langle M,t\rangle\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.