Turing Machine divisibility by 6

Question

I need to design a TM to check if a binary number can be dividied by 6. I don't know how to design it.

Thanks

Answer 1

As mentioned in a comment to your question, a finite automaton should do:

• There are $6$ states altogether
• State "$0$" is the initial state
• State "$0$" is also the accept state
• All other states are reject states
• The input should be injected MSB first / LSB last
• Please note that in essence NextState = (2 x CurrState + InputBit) % 6

---

Answer 2

Hint

A number is divisible by 6 if and only if it is divisible by both 2 and 3.

1. Binary number is divisible by 2 iff its last digit is 0.
2. A number base-10 is divisible by 3 iff the sum of its digits is divisible by 3.

Can you finish this?

Answer 3

To check for divisibility by $3$ first right-shift until the last digit is a $1$. Remove this digit along with another $1$ in the positions $2,8,32,128,\dots$ or two from positions $4,16,64,\dots$, divide by $2$'s again and repeat. If this can't be done, the number isn't divisible by $3$.