Given tape alphabet $\Gamma = \{\gamma_1 ,...,\gamma_n\}$ I wish to define a single-taped TM which given the input $\varepsilon$ writes the string $\gamma_1 \gamma_2...\gamma_n$ on the tape, and the number of states it (the TM) is using is independent of $n$.

My problem is that each time the head takes a right step and encounter a blank, It seems like the problem is just starting all over again, i.e in order to continue I need to define a new state which acts differently on blanks in order to write a new letter which wasn't written by the previous states.


The idea is to build the sequence in the following way:

$\_\ \_\ \_\ \gamma_1$

$\_\ \_\ \gamma_1 \gamma_2$

$\_\ \gamma_1 \gamma_2 \gamma_3$

$\gamma_1 \gamma_2 \gamma_3 \gamma_4$

Make $n$ following passes:

  1. Write $\gamma_1$, go to the right. While we see a non-blank symbol $\gamma_i$, replace it with $\gamma_{i+1}$ and go to the right.
  2. Go to the left until we encounter a blank symbol (to the left of $\gamma_1$).

The algorithm finishes when in stage 1) we encounter $\gamma_n$.

  • $\begingroup$ Thanks but I don't understand why this algorithms doesn't encounter a loop. We start with empty tape, thus $\gamma_1$ is written in cell[1], then we move right,see a blank, thus we move to stage2, we go left to see $\gamma_1$ in cell[1] and all over again. Thanks again. $\endgroup$ – user5721565 Jul 18 '20 at 5:17
  • $\begingroup$ @user5721565, I'm not sure I understand your question. TM is essentially one big loop. Why and how would you like to avoid loops? $\endgroup$ – Dmitry Jul 18 '20 at 5:36
  • $\begingroup$ I meant an infinite loop. $\endgroup$ – user5721565 Jul 18 '20 at 6:01
  • $\begingroup$ @user5721565, After $i$-th iteration our invariant is "the head points to the left of the sequence, which has form $\gamma_1 \ldots \gamma_i$". The algorithm terminates when $\gamma_n$ appears, which happens are $n$-th iteration. The first pass requires time $O(\text{length of current sequence})=O(n)$. The same for the second pass. Therefore, the total time is $O(n^2)$, i.e. the algorithm converges. $\endgroup$ – Dmitry Jul 18 '20 at 6:30

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.