# Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)?

(From comments below by the OP) Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.

• Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.
– Manu
Feb 14 '11 at 23:55
• @Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise... Feb 15 '11 at 0:11
• @Tsuyoshi, I think you misunderstood the question. Feb 15 '11 at 0:31
• @Jukka: On a one-tape Turing machine, everything that can be computed in time $o(n \log n)$ are in fact regular languages. Feb 15 '11 at 6:37
• @Abel: The result you quote from Arora and Barak gets around the main issue here because in their model (which is fairly standard for multi-tape TMs), they have a separate, read-only input tape. Feb 16 '11 at 5:43

A partial answer if TM runs in $o( |x| \log |x|)$

If TM4 is a 4-symbols TM (with alphabet $\Sigma_4 = \{\epsilon,0,1,2 \}$ ) that computes $f:\{0,1\}^* \to \{0,1\}$, i.e. decides language $L = \{ x | f(x) = 1 \}$ in $(o( |x| \log |x|))$

One tape deterministic linear-time complexity is $1DLIN = 1DTime(O(n))$

• Hennie proved (1) that $REG = 1DLIN$
• Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$

So $L$ is regular, and is obviously still regular over alphabet $\Sigma_3 = \{\epsilon,0,1\}$

So there is a DFA that decide L and uses only symbols in $\Sigma_3$. A one-tape, 3-symbols TM3 can be built directly from the DFA and it decides L using the same unpadded input of the original TM4.

... you cannot build it directly from TM4, but TM3 exists.

If TM4 runs in $\Omega(n^2)$ then you can shift the input and make a direct conversion from TM4 to TM3.

As noticed in the comments the difficult case is when TM4 runs in $\Omega(n\log n) \cap o(n^2)$.

(1) Hennie, One-tape, off-line Turing machine computations (1965)

(2) Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy (1985)

• The point about $o(n\log n)$ is already noted by Kristoffer Arnsfelt Hansen in the comments below the question. The really interesting case is $\Omega(n\log n) \cap o(n^2)$. Feb 19 '11 at 5:56
• You're right I didn't noticed Kristoffer comment. I badly expressed the interesting case (I don't know how to prove it), so I updated the answer. Feb 19 '11 at 13:39
• @Kaveh: What about $o(n \log n)$-time machines for promise problems? Do we already know how to convert, e.g., any machine that solves a promise problem in $O(n)$ time? I don't see how to do it, and the connection to regular languages no longer holds (unless I'm badly mistaken). Feb 19 '11 at 16:35
• @Kaveh: Can't you simply take a problem $L$ that is not a regular language but can be solved with a Turing machine in, e.g., $O(n^2)$ rounds, and define a promise problem as follows: yes-instances consist of a string $x \in L$ followed by $|x|^2$ bits of padding; no-instances consist of a string $x \notin L$ followed by $|x|^2$ bits of padding. The promise problem is solvable in $O(n)$ time, and it is not solvable using a finite state machine. Feb 20 '11 at 23:04
• @Kaveh: I guess the intuitive argument fails because of the following reason: Yes, there is a non-promise problem that is solved by the same machine. However, the running time of the machine may be as high as $\Theta(n^2)$ for certain inputs. (Intuitively, the machine cannot verify that there is enough padding, and hence "to play safe" it must assume that there is enough padding after the prefix $x$. Then it wastes $\Theta(|x|^2)$ time to determine if $x \in L$, and this is too much if, e.g., we had only $\Theta(|x|)$ bits of padding.) Feb 20 '11 at 23:19

For all alphabet sizes greater than $1$, runtimes only change by a constant factor since $\log_k(x) \in \Theta(\log_l(x))$ for all $k, l > 1$.

Elaboration: In $t$ timesteps, the assumed Turing machine can process at most $t$ positions/bits. Bits are taken from a $k$-nary alphabet, wlog $\{0,1,\dots,k-1\}$. Create a new Turing machine by replacing every transition by $\lceil \log_2(k) \rceil$ transitions; every old bit is encoded by $\lceil \log_2(k) \rceil$ bits in $\{0,1\}$ (blanks are reserved to mark unused cells). Note this is essentially binary coded digits.

Obviously, the resulting Turing machine executes at most $\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$ steps.

Addition: Above argumentation breaks because operations that overwrite an input symbol with a bit not in $\{0,1\}$ can not be translated directly; the input has to be shifted. This can be amended by translating the original input before starting computation (essentially padding); this can be done in time $\mathcal{O}(n^2)$, resulting in a total runtime of $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$.

Consequently, using only two symbols for encoding intermediate results is of no asymptotic impact if $t(n) \in \Omega(n^2)$, but preprocessing dominates faster algorithms. Since most interesting functions are in $\Omega(n^2)$ (e.g. adding two numbers), one might consider the problem negligable.

• Until you convince me why this is supposed to be the case, I shall keep that downvote. Feb 15 '11 at 13:33
• I would like to hear some evidence for your claim. All of it, it's just one claim. Feb 15 '11 at 18:44
• Oh, I see what you are referring to. Ok, sorry. However, the question is not about that. It's a slight variation. Feb 16 '11 at 6:15
• I think that the case with t=Ω(n^2) is the easy case because you can afford the time to shift the input string. The essential case is when t=o(n^2). I do not know how important it is to consider single-tape TM with o(n^2) time, but the question is about that. Feb 16 '11 at 21:38
• The original question already implies that the case $\Omega(n^2)$ is easy; hence I do not really see how this answer adds anything new... Feb 17 '11 at 8:26