0
$\begingroup$

I am reading this excerpt from Ullman's book:

enter image description here

I have following doubts:

  1. (related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9?
  2. (related to green underline) Whats the significance of "finite"? Due to 9 (or 11 if I was correct in point 1)?
  3. (related to blue underline) I am not able to understand the given proof. I tried it myself: I will run TM on all length 1 to 5 strings. If it makes 5+ moves on any of these strings, then "accept", else "reject". Hence decidable. Is my interpretation / approach correct? If correct then what was the significance of thinking about those nine cells?
$\endgroup$
1
$\begingroup$
  1. It's 9 because it doesn't matter what symbol we land on after move 5.

  2. It's finite because the number of cells is 9, yes. The significance is because otherwise the algorithm in point 3 wouldn't finish.

  3. All strings of length 9, with the starting point in the middle. "Five or fewer" is an error, I believe.

$\endgroup$
0
$\begingroup$

If the machine does exacly 5 moves, it reads at most 5 symbols. If after 5 moves it is still going, it does more than 5 moves on a tape starting with that string. So you have to check a finite set of possible inputs (strings of 5 symbols), each for a finite number of steps (5 in this case). So you can always answer "yes" or "no" in finite time, this is recursive.

$\endgroup$

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.