0
$\begingroup$

$$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$

Is this language decidable?

I will write my way of understanding it. Please answer it in the way I understand & tell if my understanding is wrong.

It means L1 is a language, which includes all such Turing machines, which takes at least 2016 steps on all inputs. So we need to say it is decidable or not...

We are talking about which machine? We are talking about that machine whose language is L1. Other TMs are input to the new turing machine as encoding of 0 &1. We need to say for all inputs (for all Turing machine encodings) the new turing machine halts or not. When it will halt? When the new turing machine can either say..."Yes, the turing machine I am considering took at least 2016 steps but still it is on progress"...it also can say "No, the turing machine you gave me went to final state before 2016 steps" If it will say either of this, then the new turing machine, language L1 is decidable.

When it will be undecidable? When the new turing machine is still on progress unable to say yes or no. So solution is run new Turing machine for 2016 steps only. If it is saying "yes, the other turing machine halted...or the other turing machine did not halt."... then for both answer our new turing machine will halt... It is simple to understand that the new turing machine will always halt... bcz it's task is just to check the other turing machine halted or not within 2016 steps.

|cite|improve this question
$\endgroup$
9
$\begingroup$

A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This gives an algorithm for deciding $L_1$: run the input machine $M$ on all inputs of length at most 2015, and check whether any of them stops within 2015 steps. If so, reject. Otherwise, accept.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ sir Thank you Please say is the answer written by me correct? I want to know if my understanding is correct or I am confused. $\endgroup$ – Ahwan Mishra Jul 24 '17 at 13:50
  • $\begingroup$ Unfortunately I am unable to understand your solution. $\endgroup$ – Yuval Filmus Jul 24 '17 at 14:02
  • $\begingroup$ @YuvalFilmus:- We can generate all the string of length 2015 instead of generating smaller length strings(at most 2015).Because if smaller length string is getting rejected then it will always be prefix of some string of 2015 length.Am i missing something here ? $\endgroup$ – rahul sharma Aug 5 '17 at 0:32
  • $\begingroup$ @rahulsharma There's no big difference. $\endgroup$ – Yuval Filmus Aug 5 '17 at 7:14
  • $\begingroup$ @YuvalFilmus:- I have some confusion here. Now suppose if i check only say 1 or 2 length string and see if these are taking 2016 steps.If yes,then every input of 3 or more always consist of these 1 or 2 length string as prefix and it should also take more than 2016 steps.If 1 or 2 bit string are taking less than 2016 steps then we can say "No" as the answer to the decision problem.This might sound awful ,but please help in understanding this point. $\endgroup$ – rahul sharma Aug 7 '17 at 18:22

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.