43
$\begingroup$

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

Improve this question
$\endgroup$
18
  • 8
    $\begingroup$ 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$. $\endgroup$
    – Manu
    Commented Feb 14, 2011 at 23:55
  • 4
    $\begingroup$ @Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise... $\endgroup$
    – Jukka Suomela
    Commented Feb 15, 2011 at 0:11
  • 3
    $\begingroup$ @Tsuyoshi, I think you misunderstood the question. $\endgroup$
    – Suresh Venkat
    Commented Feb 15, 2011 at 0:31
  • 4
    $\begingroup$ @Jukka: On a one-tape Turing machine, everything that can be computed in time $o(n \log n)$ are in fact regular languages. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Feb 15, 2011 at 6:37
  • 6
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented Feb 16, 2011 at 5:43

2 Answers 2

Reset to default
6
$\begingroup$

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)

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Kaveh
    Commented Feb 19, 2011 at 5:56
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Commented Feb 19, 2011 at 13:39
  • 1
    $\begingroup$ @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). $\endgroup$
    – Jukka Suomela
    Commented Feb 19, 2011 at 16:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jukka Suomela
    Commented Feb 20, 2011 at 23:04
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Jukka Suomela
    Commented Feb 20, 2011 at 23:19
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ Until you convince me why this is supposed to be the case, I shall keep that downvote. $\endgroup$
    – Andrej Bauer
    Commented Feb 15, 2011 at 13:33
  • 1
    $\begingroup$ I would like to hear some evidence for your claim. All of it, it's just one claim. $\endgroup$
    – Andrej Bauer
    Commented Feb 15, 2011 at 18:44
  • 2
    $\begingroup$ Oh, I see what you are referring to. Ok, sorry. However, the question is not about that. It's a slight variation. $\endgroup$
    – Andrej Bauer
    Commented Feb 16, 2011 at 6:15
  • 6
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 16, 2011 at 21:38
  • 3
    $\begingroup$ 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... $\endgroup$
    – Jukka Suomela
    Commented Feb 17, 2011 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.