# Constructing Turing Machine for division with 8

Can someone help me to construct a Turing Machine for this function:

$f(n) = \frac{n}{8}$. If $n \mod 8 = 0$, then $f(n)$ is undefined.

So the machine should somehow first prove if the number (which is represented in binary) is divisible by $8$ . That means for numbers like $1000$, $10000$, $11000$ and so on. But I don't know how can I check this.

## EDIT:

The result from the division is when we delete the last 3 digits in the binary representation of the number. I think this is not so hard. But I still have a problem with the first part. How can I prove if the number is divisible?

• If you delete last 3 digits and it is ok for divisible by 8 number, then the last 3 digits should be .... – Evil Jul 1 '17 at 17:58
• example for the number 1000 which is 8 and the result is 1 which is the correct answer . 11000 which is 24 and divided by 8 is 3 and the answer is 11 which is 3 in binary. But I'm missing the first part where I should prove if I can make the division – Hans Christian Jul 1 '17 at 18:00
• @Evil Oh , now I got what you are saying . So my turing machine should go to the end then prove if the last 3 digits are all 0s if they are then go to a state which replace them with blanks , otherwise go to a state and stop there – Hans Christian Jul 1 '17 at 18:06
• Usually when the requirement of the function is undefined it means that whatever you do is ok. That is, if you just divide by 8 the way you normally would, then in the case of $n \equiv 0 \mod 8$ would work, and all other case would still bring an undefined result. – Nescio Jul 1 '17 at 18:19

A number (in binary) is divisible by 8 if it ends at least by 3 0's. Remember that an integer is divisible by 2 (without remainder) if it ends with 0 and since $8=2^3$ its binary representation must end with at least 3 zeros.
$q_1$ - start state, $q_4$ - accept state.
$\delta(q_1, 0) = q_2, \delta(q_1, 1) = q_1$
$\delta(q_2, 0) = q_3, \delta(q_2, 1) = q_1$
$\delta(q_3, 0) = q_4, \delta(q_3, 1) = q_1$
$\delta(q_4, 0) = q_4, \delta(q_4, 1) = q_1$