# Constructing a deterministic one way infinite single tape Turing machine

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

## 1 Answer

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.

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