2,463 views

1 Answer

1 votes
1 votes

The difference between an odd and even integer is simply the presence or absence of 1 in the LSB i.e. if the binary number contains 1 in LSB it is odd, else it is even.

observing this, the design of the Turing machine becomes pretty simple:
 

There will be 3 states q0, q1 and final state q2. the machine will remain in q0 state and the R/W head will continue to move right in each step, until a B(B=Blank) is encountered, i.e the R/W head reaches the end of the string, in which case the R/W head will move left one step and changes the state to q1. if the R/W head points to 1, then the string is accepted, else it isn't .

δ(q0,0)=δ(q0,0,R)

δ(q0,1)=δ(q0,1,R)

δ(q0,B)=δ(q1,B,L)

δ(q1,1)=δ(q2,1,R)

Related questions

3 votes
3 votes
2 answers
2
3 votes
3 votes
1 answer
3
3 votes
3 votes
2 answers
4