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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ The question you should ask yourself is: why? $\endgroup$
    – Dave Clarke
    Feb 17, 2013 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$
    – rajaditya_m
    Feb 17, 2013 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, 2013 at 17:15
  • $\begingroup$ @Vor Turn comment into answer? $\endgroup$
    – Pål GD
    Feb 18, 2013 at 0:27

2 Answers 2

Reset to default
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$?

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.