0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ If you delete last 3 digits and it is ok for divisible by 8 number, then the last 3 digits should be .... $\endgroup$
    – Evil
    Commented Jul 1, 2017 at 17:58
  • $\begingroup$ 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 $\endgroup$
    – Hans Christian
    Commented Jul 1, 2017 at 18:00
  • 1
    $\begingroup$ @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 $\endgroup$
    – Hans Christian
    Commented Jul 1, 2017 at 18:06
  • $\begingroup$ 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. $\endgroup$
    – Nescio
    Commented Jul 1, 2017 at 18:19

1 Answer 1

Reset to default
0
$\begingroup$

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.

In fact a finite automaton is enough to recognize numbers divisible by 8. The following transitions are for a DFA which can be easily rewritten as TM instructions.

$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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.