1
$\begingroup$

If I have an input string that is only composed of $a$'s and $b$'s, how can I construct a Turing machine that only accepts strings where the number of $b$'s divides the number of $a$'s?

For example:

$aaaabb$ is accepted

$baaab$ is rejected

$\endgroup$
1
$\begingroup$

Here is a rather reasonable way to implement this in Turing machines:

  1. Sort the bs and the as so that the input tape is composed of bs followed by as.
  2. Repeatedly perform the following operation: remove $B$ as from the end of the input tape, where $B$ is the number of bs.
  3. Accept if you never got stuck perform an iteration of the previous step.

The second step can be implemented without explicitly counting $B$. For the first step, you can implement the simplest algorithm you can think of, say bubble sort.

$\endgroup$
  • $\begingroup$ Within the limitations of a TM, I've found that gnome sort is easier to implement. $\endgroup$ – SuperJedi224 May 5 '15 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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