Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
7  
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$. –  Emanuele Viola 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 0:11
3  
@Tsuyoshi, I think you misunderstood the question. –  Suresh Venkat Feb 15 '11 at 0:31
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 6:37
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 5:43
show 11 more comments

2 Answers

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)

share|improve this answer
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 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. –  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
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
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
show 3 more comments

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.

share|improve this answer
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
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
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 6:15
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 8:26
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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