algorithmcomputer-scienceturing-machinesreductiondecidable

Cannot create algorithm for decidable language

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w}

Hi. I am creating an algorithm to show above L2 is decidable. And the hint is given as following:

To show L2 is decidable, test given TM M on all input strings of length at most 10, each for 10 steps. Note that there are finitely many such strings to test, so this algorithm will always terminate. If M halts on any input string w within 10 steps then let w' be the prefix of w of length 10. M will also halt on input w' within 10 steps, so the decision algorithm described above will find it.

I just can't understand this hint.

M(w)
 let w be w1,w2,... such that w=w1,w2,...,wn
 for i=1,2,...,10
  run m on wi for 10 steps
  if it accepts
   let w' be prefix of w of length 10 and w' be w1,w2,... such that w'=w'1,w'2,...,w'n
   for t=1,2,...,10
    run m on w't for 10 steps
   end for
  end if
 end for
end M(W)

As you see above algorithm I made, I have no idea to make proper algorithm from those L2 defnition and hint above.

I need help on writing it correctly (please use your style of writing an algorithm. I don't think the style doesn't matter if the main idea is correct. What I do not get is its idea.)

Thank you very much if you can help me.

Solution

  • Here's a really helpful observation for solving this problem. Suppose you take a TM M and run it on a really, really long string w and want to know whether it halts within ten steps. If you think about it, the only part of w that will matter is the first ten characters, since in ten steps the TM can't read any more than that. In other words, if you want to determine whether a TM halts within ten steps when run on a string w, you just need to inspect the first ten characters of w.

    So now suppose you want to decide whether a TM will halt on some string within ten steps. Because of the observation we just made, you can determine the answer to this question without having to look at all strings. Namely, just run the TM for ten steps on all strings of length ten or less. If the TM halts within ten steps on any of those strings, then you're done - you've witnessed the TM halt within ten steps on some input string. On the other hand, suppose that the TM doesn't halt within ten steps on any of those strings. The claim to prove is that the TM therefore doesn't halt on any string within ten steps, since if it did, it would have to halt when given just the first ten characters of that string (given the above reasoning), but we know that it didn't.

    So the algorithm would look something like this: