So my homework is on Turing Machines and one of the questions that I've no idea how to start is: Design a TM that if given an unbroken string of 1s on an otherwise blank tape, will halt and the read/write head will be scanning a square on which a 1 is written if there were an odd number of 1s originally, or a blank space if the original string was even in length. Alphabet contains only 1 and blank.
I'm very stuck on this problem as I have no idea how to begin. My initial thoughts were to keep going to the right of the tape as we encounter 1s and the moment we encounter a blank space, we check to the right of it if there are other blanks or 1s and go from there, but I'm not sure about it.
Any hints would be greatly appreciated. Thank you.
You need two main states: "I've seen an even number of 1s, not including the square I'm on", and "Ive seen an odd number of 1s, not including the square I'm on". You start off in the "even" on.
You read the current square. If it's a 1, you flip the state and move right. If it's a blank, you quit if you're in "even", and you move left one and quit if you're in "odd". You may need to create a new state to handle that move left.