3
$\begingroup$

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\}$.

Improve this question
$\endgroup$
0
$\begingroup$

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.

turing machine

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sir your answer is helpful but what if i want to generate string like 1) 111 2) 111111111 3) 11111111111111111111111111 $\endgroup$ – Hammad Maqbool Nov 11 '16 at 10:32
  • 4
    $\begingroup$ I'm not a Turing machine so I've no interest in counting the number of 1s in those strings. Nor do I have any interest in playing "guess what the next number in this sequence is." But, assuming you have a sensible specification of what numbers of 1s are acceptable, use the technique I've explained to count the 1s and then show that a Turing machine can tell the difference between a correct number and an incorrect number. $\endgroup$ – David Richerby Nov 11 '16 at 10:38

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.