<p>A partial answer if TM runs in $o( |x| \log |x|)$</p>

<p>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|))$</p>

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

<ul>
<li>Hennie proved (1) that $REG = 1DLIN$</li>
<li>Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$</li>
</ul>

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

<p>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 <strong>using the same unpadded input of the original TM4</strong>.</p>

<p>... you cannot build it directly from TM4, but TM3 exists.</p>

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

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

<hr>

<p>(1) Hennie, <em>One-tape, off-line Turing machine computations</em> (1965)</p>

<p>(2) Kobayashi, <em>On the structure of one-tape nondeterministic Turing machine time hierarchy</em> (1985)</p>

CC BY-SA 2.5
2011-02-19T05:56:29.730Z
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)$.
Kaveh
CC BY-SA 2.5
2011-02-19T13:39:19.483Z
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.
Marzio De Biasi
CC BY-SA 2.5
2011-02-19T16:35:17.203Z
@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).
Jukka Suomela
CC BY-SA 2.5
2011-02-20T22:55:51.120Z
@Jukka, I am not sure but it seems to me that the theorem also hold for promise problems.
Kaveh
CC BY-SA 2.5
2011-02-20T23:04:16.130Z
@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.
Jukka Suomela
CC BY-SA 2.5
2011-02-20T23:13:02.567Z
@Jukka, you may be right, I see what you are trying to do, as I said I am not sure, but I think there might be a problem with showing that this language is $Time(O(n))$ time solvable by this specific machine model. I should admit that I am not very good with promise problems, my intuitive argument for what I said is the following: if a promise problem is solvable by a deterministic machine, then there is a non-promise problem extending that problem which is solvable by the same machine.
Kaveh
CC BY-SA 2.5
2011-02-20T23:19:37.417Z
@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.)
Jukka Suomela
CC BY-SA 2.5
2011-02-20T23:26:38.587Z
@Jukka, I thought that we can have a clock to finish in $Time(O(n))$ but now I start to think that probably the usual time constructibility theorems don't hold for this model.
Kaveh
CC BY-SA 2.5
2011-02-19T04:19:07.783Z
2011-03-05T21:11:53.810Z
2011-03-05T21:11:53.810Z
Marzio De Biasi
<p><strike>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 &gt; 1$.</p>

<p>Elaboration:</strike> 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.</p>

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

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

<p>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.</p>

CC BY-SA 2.5
2011-02-15T13:33:34.870Z
Until you convince me why this is supposed to be the case, I shall keep that downvote.
Andrej Bauer
CC BY-SA 2.5
2011-02-15T15:47:09.830Z
Which part of the statement?
Raphael
CC BY-SA 2.5
2011-02-15T18:44:15.207Z
I would like to hear some evidence for your claim. All of it, it's just one claim.
Andrej Bauer
CC BY-SA 2.5
2011-02-16T02:01:16.753Z
Sorry, (asymptotic) equivalence of non-unary encodings was taught to me in my very first algorithms course so I did not think this was really an issue. Hope the elaborations helps (and I did not mess it up at this late hour).
Raphael
CC BY-SA 2.5
2011-02-16T06:15:26.887Z
Oh, I see what you are referring to. Ok, sorry. However, the question is not about *that*. It's a slight variation.
Andrej Bauer
CC BY-SA 2.5
2011-02-16T09:43:06.567Z
I think I answered the right question, but wrongly. At least now I know what the guys are referring to when talking about shifting stuff.
Raphael
CC BY-SA 2.5
2011-02-16T14:28:58.730Z
Let's see how deep I have to dig until I stop writing nonsense.
Raphael
CC BY-SA 2.5
2011-02-16T21:38:56.603Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-17T08:26:12.430Z
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...
Jukka Suomela
CC BY-SA 2.5
2011-02-14T23:43:40.570Z
2011-02-16T14:28:19.993Z
2011-02-16T14:28:19.993Z
Raphael
<p>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)?</p>

<p>(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$.</p>

CC BY-SA 3.0
2012-08-17T16:14:52.113Z
@Joshua, the time hierarchy theorem holds for single-tape machines with arbitrary alphabet size. However the poof in the Hartmanis 1968 considers the case where $t \in o(n^2)$ separately and gives a direct proof that doesn't seem to based on simulation.
Kaveh
CC BY-SA 3.0
2017-02-14T10:52:37.940Z
What is a bit puzzling in this kind of problems is if you may expect to receive the input in the way you desire. If the input is already sufficiently "sparse" you have no actual need to move it around.
Andrea Asperti
CC BY-SA 4.0
2024-03-01T22:42:47.663Z
Suppose integers are encoded as their prime factorization.  Then factoring is easy.  In this sense, the encoding of the input is "everything".
Manu
CC BY-SA 2.5
2011-02-14T23:37:48.950Z
This is a textbook exercise and inappropriate on this site.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-14T23:55:27.617Z
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
CC BY-SA 2.5
2011-02-15T00:11:25.963Z
@Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise...
Jukka Suomela
CC BY-SA 2.5
2011-02-15T00:31:40.250Z
@Tsuyoshi, I think you misunderstood the question.
Suresh Venkat
CC BY-SA 2.5
2011-02-15T00:38:31.563Z
Based on Emanuele's comment, it seems to me that overwriting the input is the *only* bottleneck, and only for $t = o(n^2)$, because if we restrict to TMs with read-only access to the input, then I think the usual technique gives a positive answer to the question. If I have understood, then the following question is essentially equivalent: given a bijection between an alphabet $A$ of size $k$ and $B^{\log_3(k)}$ where $|B|=3$, can one convert a string over $A$ into a string over $B$ according to the bijection, on a one-tape TM, in linear time? To which the answer is almost surely no...
Joshua Grochow
CC BY-SA 2.5
2011-02-15T00:56:43.150Z
Odifreddi does not discuss it. Peter van Emde Boas's article "Machine Models and Simulation" in TCS handbook states the above simulation result only works for $n^2 \leq t$. It doesn't say if it is possible or not through other methods.
Kaveh
CC BY-SA 2.5
2011-02-15T01:30:56.557Z
@Suresh: Yes, I misunderstood the question.  Sorry, Emanuele.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-15T01:42:09.473Z
It might help if we came up with examples of problems that have a simple linear-time algorithm *if* we can overwrite the input.
Jukka Suomela
CC BY-SA 2.5
2011-02-15T06:37:14.510Z
@Jukka: On a one-tape Turing machine, everything that can be computed in time $o(n \log n)$ are in fact regular languages.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-02-16T04:09:14.247Z
Claim 1.8 in the online draft of Arora and Barak (http://www.cs.princeton.edu/theory/complexity/modelchap.pdf) seems related. It is actually not clear to me right now how does the proof there avoid this issue (maybe determining it can shed some light on the question here)
Abel Molina
CC BY-SA 2.5
2011-02-16T05:43:01.873Z
@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.
Joshua Grochow
CC BY-SA 2.5
2011-02-16T05:51:15.797Z
@Kristoffer: I guess one way to get around that limitation would be to focus on promise problems, which makes it possible to use padding.
Jukka Suomela
CC BY-SA 2.5
2011-02-16T21:34:50.697Z
@Joshua: I agree that the task you stated (in your comment at 0:38 on Feb. 15 UTC) looks like impossible, but is that the only way to convert a single-tape TM on the alphabet of size k for a language f to a single-tape TM on the binary alphabet?  I am not sure.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-17T03:47:25.063Z
@Tsuyoshi: I am not sure either. In fact, the more I think about it, the less likely it seems that this is the only way.
Joshua Grochow
CC BY-SA 2.5
2011-02-19T22:05:25.027Z
I deleted my answer, since it provided no insight into the problem. However, I am still very interested in this problem. I would like @Emanuele Viola to give us more details, if possible. I would specifically would like to know more details about the input encoding, since I believe it is crucial to the problem.
chazisop
<computability><turing-machines>
Alphabet of single-tape Turing machine
Manu
# Alphabet of single-tape Turing machine

(Asked by: username_0 on 2011-02-14)

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

**Tags:** computability, turing-machines

> **Comments:**
> **username_3**: This is a textbook exercise and inappropriate on this site.  
> **username_0**: 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$.  
> **username_4**: @Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise...  
> **username_5**: @Tsuyoshi, I think you misunderstood the question.  
> **username_6**: Based on Emanuele's comment, it seems to me that overwriting the input is the *only* bottleneck, and only for $t = o(n^2)$, because if we restrict to TMs with read-only access to the input, then I think the usual technique gives a positive answer to the question. If I have understood, then the following question is essentially equivalent: given a bijection between an alphabet $A$ of size $k$ and $B^{\log_3(k)}$ where $|B|=3$, can one convert a string over $A$ into a string over $B$ according to the bijection, on a one-tape TM, in linear time? To which the answer is almost surely no...  
> **username_1**: Odifreddi does not discuss it. Peter van Emde Boas's article "Machine Models and Simulation" in TCS handbook states the above simulation result only works for $n^2 \leq t$. It doesn't say if it is possible or not through other methods.  
> **username_3**: @Suresh: Yes, I misunderstood the question.  Sorry, Emanuele.  
> **username_4**: It might help if we came up with examples of problems that have a simple linear-time algorithm *if* we can overwrite the input.  
> **username_7**: @Jukka: On a one-tape Turing machine, everything that can be computed in time $o(n \log n)$ are in fact regular languages.  
> **username_8**: Claim 1.8 in the online draft of Arora and Barak (http://www.cs.princeton.edu/theory/complexity/modelchap.pdf) seems related. It is actually not clear to me right now how does the proof there avoid this issue (maybe determining it can shed some light on the question here)  
> **username_6**: @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.  
> **username_4**: @Kristoffer: I guess one way to get around that limitation would be to focus on promise problems, which makes it possible to use padding.  
> **username_3**: @Joshua: I agree that the task you stated (in your comment at 0:38 on Feb. 15 UTC) looks like impossible, but is that the only way to convert a single-tape TM on the alphabet of size k for a language f to a single-tape TM on the binary alphabet?  I am not sure.  
> **username_6**: @Tsuyoshi: I am not sure either. In fact, the more I think about it, the less likely it seems that this is the only way.  
> **username_9**: I deleted my answer, since it provided no insight into the problem. However, I am still very interested in this problem. I would like @Emanuele Viola to give us more details, if possible. I would specifically would like to know more details about the input encoding, since I believe it is crucial to the problem.  
> **username_1**: @Joshua, the time hierarchy theorem holds for single-tape machines with arbitrary alphabet size. However the poof in the Hartmanis 1968 considers the case where $t \in o(n^2)$ separately and gives a direct proof that doesn't seem to based on simulation.  
> **username_2**: What is a bit puzzling in this kind of problems is if you may expect to receive the input in the way you desire. If the input is already sufficiently "sparse" you have no actual need to move it around.  
> **username_0**: Suppose integers are encoded as their prime factorization.  Then factoring is easy.  In this sense, the encoding of the input is "everything".  

---

## 2 answers

### Answer by username_10 on 2011-02-19. Score: 6

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)

> **Comments:**
> **username_1**: The point about $o(n\log n)$ is already noted by username_7 in the comments below the question. The really interesting case is $\Omega(n\log n) \cap o(n^2)$.  
> **username_10**: 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.  
> **username_4**: @username_1: 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).  
> **username_1**: @Jukka, I am not sure but it seems to me that the theorem also hold for promise problems.  
> **username_4**: @username_1: 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.  
> **username_1**: @Jukka, you may be right, I see what you are trying to do, as I said I am not sure, but I think there might be a problem with showing that this language is $Time(O(n))$ time solvable by this specific machine model. I should admit that I am not very good with promise problems, my intuitive argument for what I said is the following: if a promise problem is solvable by a deterministic machine, then there is a non-promise problem extending that problem which is solvable by the same machine.  
> **username_4**: @username_1: 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.)  
> **username_1**: @Jukka, I thought that we can have a clock to finish in $Time(O(n))$ but now I start to think that probably the usual time constructibility theorems don't hold for this model.  

---

### Answer by username_11 on 2011-02-14. Score: -3

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.

> **Comments:**
> **username_12**: Until you convince me why this is supposed to be the case, I shall keep that downvote.  
> **username_11**: Which part of the statement?  
> **username_12**: I would like to hear some evidence for your claim. All of it, it's just one claim.  
> **username_11**: Sorry, (asymptotic) equivalence of non-unary encodings was taught to me in my very first algorithms course so I did not think this was really an issue. Hope the elaborations helps (and I did not mess it up at this late hour).  
> **username_12**: Oh, I see what you are referring to. Ok, sorry. However, the question is not about *that*. It's a slight variation.  
> **username_11**: I think I answered the right question, but wrongly. At least now I know what the guys are referring to when talking about shifting stuff.  
> **username_11**: Let's see how deep I have to dig until I stop writing nonsense.  
> **username_3**: 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.  
> **username_4**: 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...  

---

