For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$
I believe that I can do this, however my method is very long and difficult to keep track of due to the many different states required for my Turing Machine.
Anyway, I proceeded as follows (exact details omitted): Given an input string look for the first 0. Upon finding a zero, check if 001 occurs there. If so, accept and if not move to the next 0 then do the same. If at some point we see a blank then it means no 001 was seen so do a carriage return whereby we plan to test if 0•0•1 appears (• is any element in the alphabet).
I did this step in generality: suppose we want 0•••...•••0•••...•••1 where there are n•s in each case. Then, upon seeing a zero move along n places in the tape by defining new states at each symbol that act as a counter (see attached image). I know that I need to include details here regarding if a blank is seen because then we have reached the end of string => carriage return.
I'm fairly sure this algorithm is correct (with a bit of polishing) and since there are a lot (finitely many however) of states, then I am ok, but is there an easier method? For this algorthim I have initial, accept, reject, carriage return, find-0, find-1, move-n spaces (2sets, before and after middle 0 in the string! They are distinct) for each value of n between 1 and the length of the string: this is a nightmare to write and keep track of!
Surely an easier method exists?!
The image is only rough work so please don't be too cruel. Also, $x$ is any element in the input alphabet, there are special cases if we get to a blank.
Hint: are there at least two $0$'s to the left of the rightmost $1$?