1
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ The question you should ask yourself is: why? $\endgroup$ Feb 17 '13 at 15:10
  • $\begingroup$ Well for atmost i steps, only first i cells are relevant. Hence evaluating the string of length i should suffice. $\endgroup$ Feb 17 '13 at 15:12
  • 1
    $\begingroup$ 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 ..." $\endgroup$
    – Vor
    Feb 17 '13 at 17:15
  • $\begingroup$ @Vor Turn comment into answer? $\endgroup$
    – Pål GD
    Feb 18 '13 at 0:27
5
$\begingroup$

This language is decidable.

Hint: If you are allowed to run for only $i$ steps, what can you do with input of size $j>i$?

$\endgroup$
0
1
$\begingroup$

The solution in the question is correct.

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.

$\endgroup$

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.