0

I saw a problem of a Turing machine that seemed interesting to me, it is the following:

Construct a TM that decides if a given word has a even number of 0's and an odd number of 1's.

I wanted to give it a try and see if you guys could help me with the idea I have in mind. For example, if I want to check if a number $n$ is even I check if $n-2$ is, and if I want to check if it is odd I check if $n-2$ is. Well, with that order of ideas, for example, I want to verify if the word 0100100110 has an even number of zeros and an odd number of ones. For that, I delete the zeros two by two (in the Turing machine I mark them with some letter or blank space) and if I don't have any zero left to delete, the number of zeros is even and if I have any zero left, the amount is odd and goes to the state of rejecting the word. Likewise with the ones, if when I delete them I don't have any 1 left, the amount is even and it would go to the rejected state but if I have any one left then the amount is odd and I would accept the word. But how can I translate that idea into a Turing machine, if I can only give it one instruction I can't go erasing two by two zeros but by marking them one by one. Any idea to make the diagram of the machine.

asd asd
  • 533
  • 2
    I would try it with states. All you care about is the parity of the (number of) $0's$ and $1's$. You start in $(E,E)$. Now read the tape. If you see a $1$ move to $(E,O)$, if you see a $0$, move to $(O,E)$. Keep reading. You want to stop in $(E,O)$. – lulu Jan 19 '23 at 00:42
  • I don't understand states. What does (E,E) mean and when I move to (E,O) what direction does it move and do you change the 1 and 0 to something? @lulu – asd asd Jan 19 '23 at 01:10
  • $E$ stands for Even, $O$ stands for odd. The state $(E,E)$ means you have seen an even number of both $0's$ and $1's$. You start there because at the start you haven't seen any characters at all and zero is even. If the first character is $1$ you have seen one $1$ and one is odd so you move to $(E,O)$. If the next character is $0$ you would then move to $(O,O)$. The beauty is that the machine doesn't care how many times you have been in each state, it can forget that. It only cares which state you are currently in. If you stop in $(E,O)$ you win, if you stop anywhere else you lose. – lulu Jan 19 '23 at 10:59
  • Such a Turing Machine is called a Finite State Machine (or FSM for short). I only need four states to catch the possible pairs of parities (then we need Win and Lose as Terminal States if you want). – lulu Jan 19 '23 at 11:00
  • here is an article on FSM's. They give several examples, including one that accepts only binary strings with an even number of $0's$. Note that they don't bother creating separate Win and Lose terminal states, they just indicate which of the states are "accepting" and which are not. – lulu Jan 19 '23 at 11:07

0 Answers0