0
$\begingroup$

$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$

the answer says $L_1$ is recursive.

I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of to see if it takes at least 2016 steps I can use dovetailing idea and say yes for some inputs here string length doesn't matter right? for the complement of this language for $L_1$ COMPLEMENT, I will have encodings of that take less than 2016 steps on all inputs how will I check this? if strings of length &n& are taking less than 2016 steps then obviously all the $n+1$ will take less than 2016 to halt is it that way?

then what are the strings which i should check for? please help

Improve this question
$\endgroup$
6
  • $\begingroup$ See this very similar question: cs.stackexchange.com/questions/79255/…. $\endgroup$
    – Yuval Filmus
    Commented Nov 28, 2017 at 20:34
  • $\begingroup$ @YuvalFilmus sir I exactly asked the question which they asked this may be very trivial to u but please make me understand one thing if i check wheter the machine takes less than 2016 steps on all inputs of length atmost 2016 can i declare it takes less than 2016 steps on all the "inputs" $\endgroup$
    – venkat
    Commented Nov 28, 2017 at 20:57
  • 1
    $\begingroup$ If you're not sure about something, try to prove it! $\endgroup$
    – Yuval Filmus
    Commented Nov 28, 2017 at 20:58
  • $\begingroup$ @ Yuval Filmus sir in that case we need not even check for strings till length till 2016 as strings of length n will form prefixes of length n+1 right $\endgroup$
    – venkat
    Commented Nov 28, 2017 at 21:03
  • $\begingroup$ Hint: $L_1 = \{ M \mid |x| < 2016$ and $M(x)$ runs for at least 2016 steps $\} \cup$ $\{ M \mid |x| = 2016, y \in \Sigma^*$ and $M(xy)$ runs for at least 2016 steps $\}$. The first set is clearly recursive; in order to prove that the second set is also recursive the "difficult part" is to prove that if $|x|=2016$ then $M(x)$ runs for at least 2016 steps if and only if $\forall y \; M(xy)$ runs for at least 2016 steps .... $\endgroup$
    – Vor
    Commented Nov 29, 2017 at 13:28

0

Reset to default

Your Answer

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