Question

4. (15 points) Design a Turing machine that determines whether or not a given binary number (where the least significant digit is stored first) is a multiple of 2. If the binary number is a multiple of two, just have the Turning machine transition to the "accept” state. If the binary number is not a multiple of two, have the Turning machine transition to the "reject" state. For this type of Turning machines (recognizers), you do not need to transition to a halt state nor rewind the tape. Test it, step-by-step, on these two examples: n=4; n=5 This is how the tape looks like for n=5: <blank> 1 0 1 <blank> <blank> <blank>...

Please give answer like this [Start #] -> [move R]. I dont want an NFA with States

Answer 1

Format is
[current_state, symbol] -> [new_State, changed_symbol, move(L/R/S)]

Turing machine

[Start, <blank>] -> [A, <blank>, R]
[A, 0] -> [Accept, 0, R]
[A, 1] -> [Reject, 1, R]

Explanation

• If 0 is at the beginning that is the least significant bit, then it is even. So, accepting
• Otherwise rejecting it

Please up vote