43

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

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Manu
  • 7,659
  • 3
  • 37
  • 42
  • 1
    This is a textbook exercise and inappropriate on this site. – Tsuyoshi Ito Feb 14 '11 at 23:37
  • 8
    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
  • 4
    @Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise... – Jukka Suomela Feb 15 '11 at 00:11
  • 3
    @Tsuyoshi, I think you misunderstood the question. – Suresh Venkat Feb 15 '11 at 00:31
  • 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 Feb 15 '11 at 00:38
  • 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 Feb 15 '11 at 00:56
  • @Suresh: Yes, I misunderstood the question. Sorry, Emanuele. – Tsuyoshi Ito Feb 15 '11 at 01:30
  • 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 Feb 15 '11 at 01:42
  • 4
    @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 Feb 15 '11 at 06:37
  • 1
    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 Feb 16 '11 at 04:09
  • 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. – Joshua Grochow Feb 16 '11 at 05:43
  • @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 Feb 16 '11 at 05:51
  • @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 Feb 16 '11 at 21:34
  • @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 Feb 17 '11 at 03:47
  • 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 Feb 19 '11 at 22:05
  • 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. – Kaveh Aug 17 '12 at 16:14
  • 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 Feb 14 '17 at 10:52
  • Suppose integers are encoded as their prime factorization. Then factoring is easy. In this sense, the encoding of the input is "everything". – Manu Mar 01 '24 at 22:42

2 Answers2

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)

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 1
    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 Feb 19 '11 at 05: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. – Marzio De Biasi Feb 19 '11 at 13:39
  • 1
    @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 Feb 19 '11 at 16:35
  • @Jukka, I am not sure but it seems to me that the theorem also hold for promise problems. – Kaveh Feb 20 '11 at 22:55
  • 1
    @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 Feb 20 '11 at 23:04
  • @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 Feb 20 '11 at 23:13
  • 1
    @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 Feb 20 '11 at 23:19
  • @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 Feb 20 '11 at 23:26
-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.

Raphael
  • 4,565
  • 28
  • 48
  • 3
    Until you convince me why this is supposed to be the case, I shall keep that downvote. – Andrej Bauer Feb 15 '11 at 13:33
  • Which part of the statement? – Raphael Feb 15 '11 at 15:47
  • 1
    I would like to hear some evidence for your claim. All of it, it's just one claim. – Andrej Bauer Feb 15 '11 at 18:44
  • 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 Feb 16 '11 at 02:01
  • 2
    Oh, I see what you are referring to. Ok, sorry. However, the question is not about that. It's a slight variation. – Andrej Bauer Feb 16 '11 at 06:15
  • 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 Feb 16 '11 at 09:43
  • Let's see how deep I have to dig until I stop writing nonsense. – Raphael Feb 16 '11 at 14:28
  • 6
    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 Feb 16 '11 at 21:38
  • 3
    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 Feb 17 '11 at 08:26