Counters in Turing machines

Question

I know how a Turing machine works, how it accepts a language but in some.

In some scenarios we would like to use counters. For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$. How can I count the number of zeroes?

If some one of you could solve the following problem for me it would help my understanding of these matters:

Design a Turing machine for $L = \{1^{3^n} : n \geq 1\}$.

Answer 1

I know this question has quite a few months already, but I'd like to share here the Turing Machine for $\{0^{2^n} : n \geq 0\}$ found in Michael Sipser's Introduction to the Theory of Computation, 3rd edition (Example 3.7).

The idea behind this machine is as follows, everything after this line is a direct quote of the book:

“On input string w:

1. Sweep left to right across the tape, crossing off every other 0.
2. If in stage 1 the tape contained a single 0, accept .
3. If in stage 1 the tape contained more than a single 0 and the number of 0s was odd, reject .
4. Return the head to the left-hand end of the tape.
5. Go to stage 1.”

Each iteration of stage 1 cuts the number of 0s in half. As the machine sweeps across the tape in stage 1, it keeps track of whether the number of 0s seen is even or odd. If that number is odd and greater than 1, the original number of 0s in the input could not have been a power of 2. Therefore, the machine rejects in this instance. However, if the number of 0s seen is 1, the original number must have been a power of 2. So in this case, the machine accepts.

Answer 2

Well, you could just implement a counter. I'll assume that the tape alphabet is $\{0,1,\#\}$.

First, scan to the end of the input, and write $\#0$ to the tape after the last character. The string of zeroes and ones after the $\#$ will be a binary counter.

Second, convince yourself that a Turing machine can add one to a number in binary.

Third, peform the following until you run out of input. Scan back to the first $1$ on the tape, replace it with a $\#$, scan back to the counter and add one to it.

Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.