Constructing Turing machines

Question

I get the main ideas of Turing machines. But I can't construct a Turing machine to solve a given question.

The question I'm trying to solve is "Construct a Turing machine that recognises the set of all strings that contain an even number of $1$s."

How can I think about all the cases? Is there a way to do it?

Answer 1

It is simpler than what you think. You don't even need a Turing machine that writes to the tape.

Here is a Turing machine whose final state would be $YES$ if the string (in tape) contains an even number of 1's, and in $NO$ if the string contains an odd number of 1's, assuming the string marks its end with a #, and it starts from left to right.

Let $ M = (Q, Γ, Σ, δ, s, B, F)$ be a Turing Machine with the definition

$$Q = \{read_0,read_1,YES,NO\}$$

$$Γ = \{1,0,\#\}$$

$$Σ = \{\}$$

$$F = \{YES,NO\}$$

$$s = read_0$$

$$B=\#$$

$δ$ is given by $δ_{q\ t} = ( move \,\ next\ stage)$ where $t$ is the tape symbol that it reads, and $q$ represents each state:

$$δ_{read_0\ 0} = (R,read_0)$$ $$δ_{read_0\ 1} = (R,read_1)$$ $$δ_{read_0\ \#} = (0,YES)$$ $$δ_{read_1\ 0} = (R,read_1)$$ $$δ_{read_1\ 1} = (R,read_0)$$ $$δ_{read_1\ \#} = (0,NO)$$

---

Basically what it does is that if it see $1$ it alters between $read_0$ and $read_1$ states. And if it is in $read_0$ state and sees $\#$, which means the string ended, it would go to the final state, $YES$. If it is in $read_1$ and sees $\#$ it would go to $NO$.

So if the string contains three $1$s, the states change in this way $$read_0 \rightarrow read_1 \rightarrow read_0 \rightarrow read_1 \rightarrow NO$$ implying that it doesn't contain an even number of 1s.

Answer 2

Do I understand correctly that you are looking for a formal definition of a TM (i.e. with transition function and such) and that you are working on the alphabet $\Sigma = \{0,1\}$?

Checking whether a string has an even number of 1s is equal to counting the number of 1s in it and testing it that number is 0 mod 2. So basically, you want to process the string and count between "sum is 0 mod 2" and "sum is 1 mod 2". Finite counting in TMs is easily done by using different states for each of the counting possibilites. In this case, you would have one state for "sum is 0 mod 2" and one for "sum is 1 mod 2".

Therefore, a TM that solves your problem could possibly work like this:

1. Start in state $q_0$
2. If the current state is $q_0$ and the current symbol is $1$, change to state $q_1$, else don't change state. Continue with step 4
3. If the current state is $q_1$ and the current symbol is $1$, change to state $q_0$, else don't change state. Continue with step 4
4. Move the head right
5. If the current symbol is Blank, go to step 6. Otherwise, go to step 2.
6. In state $q_i$, write $i$ and change to final state $\overline{q}$

Just a remark: To do infinite counting (e.g. you want the TM to output the number of 1s in the input string in binary), you would usually introduce a second tape on which you save the sum of the counted 1s so far.