I am reading this excerpt from Ullman's book:
I have following doubts:
- (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?
- (related to green underline) Whats the significance of "finite"? Due to 9 (or 11 if I was correct in point 1)?
- (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?