Turing machine homework?
Can someone please help me with my homework? I don't know what to do 🙁
If someone could explain this to me that would be great.
"The input/output tape of a Turing machine can hold either a one (1), a zero (0), or a space (B) in each cell. A Turing program must be specified that supplements any number of inputs (i.e., character strings on the tape consisting of zeros and ones) by an "even-parity" bit to an even number of ones. It can be assumed that at the beginning of the Turing machine's operation, the read/write head is on the first bit of the input and that the tape contains only spaces apart from the inputs.
Example:
Input: 0110B.. Output: 01100B..
Input: 111B.. Output: 1111B.. "
Thanks 🙂
(1 votes)
Loading...
Your Turing machine needs only two states besides the final state F : G Even and Odd . Read the digits from right to left and set the next state based on the input: The parity (G or U) only changes if it is 1. You start in state G . If the input is 0, the following rule applies:
That is, the state remains G , the 0 stays, and you go right . The other three rules (G 1 / P 0 / P 1) work in the same way, in principle.
As soon as a blank appears, you write a 0 or 1 there depending on the state and you are done (state F ):
These 6 rules are the program of the Turing machine.
You should specify the program of a TM that determines the parity.
The program of the TM is the transition function, so for each state and each input you write down what the next state and output is and that's it.