# How to define a TM which writes all the tape alphabet, when the number of states is independent of the tape alphabet size?

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

• 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. – user5721565 Jul 18 '20 at 5:17
• @user5721565, I'm not sure I understand your question. TM is essentially one big loop. Why and how would you like to avoid loops? – Dmitry Jul 18 '20 at 5:36
• I meant an infinite loop. – user5721565 Jul 18 '20 at 6:01
• @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. – Dmitry Jul 18 '20 at 6:30