0
$\begingroup$

The following turing machine has the only accepting state $q_1$. Its initial state is $q_0$. The input consists of elements from $\{0,1\}$. My exercise says that I have to interpretate the input of the machine as a binary number. Which mathematical question does the machine answer then?

What I see: From the initial state the machine goes to the right end of the input, without changing something. Then it goes to the left site, replacing every character by a blank. In the end, the output is blank. Whether the machine accepts the input or not depends on the state, in which it reaches the left end. So the machine is actually just a state-to-state-maze. I drew an according graph of it. Allthough it seems that the structure of the machine is very simple, I can't find a very "simple" answer about what the machine answers.

Thanks in advance!

Transition table of the turing machine.

$\endgroup$
3
  • $\begingroup$ Have you tried a couple examples to see what sort of number this machine accepts/rejects when (their binary expansion is) fed as input? $\endgroup$
    – Noah Schweber
    Oct 3, 2016 at 18:17
  • $\begingroup$ I have. Using my graph, this is not complicated. Accepting: 11, 011, 10101, 110. Non-accepting: 10, 101, 0101, ... $\endgroup$
    – S. M. Roch
    Oct 3, 2016 at 18:21
  • 1
    $\begingroup$ OK, so - converting to decimal notation - the numbers it accepts include $3, 6, 21$, and it doesn't accept $2$ or $5$. There's a natural pattern to guess at now . . . $\endgroup$
    – Noah Schweber
    Oct 3, 2016 at 18:31

1 Answer 1

Reset to default
0
$\begingroup$

It seems that $a$ is for "add" and $s$ for subtract. In the "add" states, the input digit is added $\bmod 3$ to the index of the state name, in the "subtract" states it is subtracted $\bmod 3$. Also note that we switch between add and subtract each time. So for digit sequence $x_nx_{n-1}\ldots x_2x_1x_0$ we cacluclate $\sum x_k(-1)^k\bmod 3$ and accept if this is $0$. In simpler terms, we accept if the number represented by the binary string is a multiple of $3$. The reason why this works is that $2^k\equiv (-1)^k\pmod 3$.

The computation is similar to the decimal rulefor determining divisibilty by $11$ via the alternating digit sum.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .