Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?

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

2 Answers 2

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$?

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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