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?


2 Answers 2


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$$


$δ$ 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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.