Draw a Turing machine that recognizes $\{w \in\{0,1\}^*\,|\,w\text{ contains even number of 1's}\}$

Question

Draw a Turing machine that recognizes the language $\{w \in \{0,1\}^*|w \text{ contains even number of 1's}\}$

This is where I am at:

Answer 1

You don't need a full blown Turing machine for this. A finite machine (equivalent to a Turing machine that just reads its tape once in one direction) will do.

The required language is given by the regular expression

$$0^* \left( 10^*10^* \right)^*$$

The minimal finite machine that recognises this has two states:

• an initial accepting state, say $A$;
• another non-accepting state, say $B$.

The states behave symmetrically:

• An input of $0$ leaves the machine in the same state, $A$ or $B$.
• An input of $1$ takes the machine to the other state: $A$ to $B$ or $B$ to $A$.