# Is this a correct decider?

We are given the following language

B = {$<M,i>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps }

Is language B decidable ?

As per a hint from another fellow user, I decided to construct the following decider for B. Call it D.

D = On input

1. Enumerate all the strings in $\Sigma^*$ in lexicographical order (shortlex). Let the generated sequence be $s_1,s_2,...$ where each $s_k$ denotes all strings of lenght $k$
2. Simulate each string in $s_k$ on M for atmost i steps.
3. If any of them is accepted, ACCEPT.
4. When we have finished evaluating strings for length $s_i$, output REJECT.

Is this the correct decider for B ?

• The question you should ask yourself is: why? Feb 17, 2013 at 15:10
• Well for atmost i steps, only first i cells are relevant. Hence evaluating the string of length i should suffice. Feb 17, 2013 at 15:12
• The proof is correct; to be pedantic, the formalism can be improved a little bit. Usually sets are represented with uppercase letters. You can also "compact" 1. and 2. with: "Let $S$ be the finite set of all strings of length $\leq i$; for each $s_j \in S$ simulate M on input $s_j$ for at most $i$ steps ... Furthermore your comment should be part of the proof ("We can consider only strings of length at most $i$, because the Turing machine $M$ can read at most $i$ input symbols in $i$ steps ..."
– Vor
Feb 17, 2013 at 17:15
• @Vor Turn comment into answer? Feb 18, 2013 at 0:27

Hint: If you are allowed to run for only $i$ steps, what can you do with input of size $j>i$?
As the comments say, with $i$ steps any TM can check only inputs of length at most $i$ (the behaviour on longer inputs will be the same as the behaviour on their prefix of length $i$). There is a finite number of those, which can be checked one by one by running $i$ steps on each.