2
$\begingroup$

Hey guys so I picked up Introduction to the Theory of Computation and started studying finite automata and Turing machines. I was given the following language as an exercise in class, in which I need to build a Turing machine with only one tape and no extra tape space that accepts the following language:

$$\{0^{3^k} 1^p, \text{ where $k > 0$ and $p$ is a multiple of $k$}\}$$

How can one build a single tape Turing machine that accepts this kind of language without using any extra tape space?

I found an example for $\{0^n 1^n\}$ in Introduction to the Theory of Computation but I cannot figure out how to build a machine for the language mentioned above.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Start by coming up with a Turing machine that uses linear space. You can convert it into an in-place Turing machine which simulates multiple tapes on a single tape by enlarging the alphabet. $\endgroup$
    – Yuval Filmus
    Commented Apr 17, 2021 at 10:41

2 Answers 2

Reset to default
4
$\begingroup$

This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an indicator that you performed one division (since after erasing the first triplet you will have the space to store this "1"). Then you have to bring all the new zeros together and repeat the procedure. The number of ones you have written will be equal to $k$ (and if at some point you cannot perform the division, that is you don't have a power of three - you reject the language).

Next, you begin erasing the ones that come after zeros. Each turn will consist of wiping out exactly $k$ ones - for example the $k$ ones that you have on the left can be replaced by zeros in order to indicate that a one on the right has been erased. At the end of the turn, you replace all the zeros by ones again. Again, if you cannot perform the whole round, you must reject the language.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This actually makes perfect sense, thank you so much! $\endgroup$
    – Mihai Chirculete
    Commented Apr 17, 2021 at 11:40
4
$\begingroup$

Just for fun, I've constructed the TM sketched by Rodion, you can simulate its behaviour here. Observe that I assume $p$ (or $m$, which is the same) strictly positive; moreover one actually has to use two cells outside the input, namely the cell immediately to the left of the first symbol of the input and the one immediately to the right of the last symbol of the input.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! This is amazing and helps a lot to visualize the whole process $\endgroup$
    – Mihai Chirculete
    Commented Apr 17, 2021 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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